Informatica Online Judge

  표절 검사 1 [0902 / 0386]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 5   Total Tried : 15


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[JKJeong 2013]

Background

최근 음악의 표절에 대한 시비가 많다.

경곽이는 현재 표절에 대한 기준에 대해서 알아보았다. 표절이란 두 곡의 각 코드열의 LCS의 길이가 K이상인 경우를 말한다고 한다.

LCS의 정의는 다음 링크를 참고한다.

https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

그리고 공개된 코드열 X가 있다. 이 코드열은 누구나 사용할 수 있도록 공개되었기 때문에 X를 sub-string으로 사용하는 건 문제되지 않는다.

sub-string의 정의는 다음 링크를 참고한다.

https://en.wikipedia.org/wiki/Substring

경곽이는 표절을 판단하는 프로그램을 의뢰받았다.

먼저 임의의 두 곡 A, B의 코드열이 주어진다. 이 두 곡이 표절인지 아닌지를 알고 싶다.

그리고 표절의 기준이 되는 LCS의 길이 K가 주어진다.

다음으로 누구나 활용할 수 있는 공개된 코드열 X가 주어진다.

경곽이는 이 값들을 이용하여 두 곡 A, B의 표절 여부를 구해야 한다.

만약 두 곡의 코드열 x를 sub string으로 포함하지 않는 LCS의 길이가 K미만이라면 표절이 아니다. 이 때는 두 곡의 LCS의 길이를 출력한다.

만약 코드열 X를 sub string로 포함하지 않는 LCS의 길이가 K이상이라면 이는 표절이다. 따라서 이 때는 표절이 되는 LCS열 자체를 출력한다.

당연히 이 LCS는 코드열 X를 sub string으로 표함하지 않아야 하며, 이러한 LCS가 여러 개 존재한다면 아무거나 출력해도 된다.

Input

첫 번째 줄에 첫 번째 곡의 코드열 A가 입력된다.
두 번째 줄에 두 번째 곡의 코드열 B가 입력된다.
세 번째 줄에 표절인지 판단하는 LCS의 길이 K가 입력된다.
네 번째 줄에 공개된 코드열 X가 입력된다.

[입력값의 정의역]
코드열을 구성하는 원소는 모두 알파벳 대문자
1 <= |A|, |B| <= 100 (단, |X|는 문자열 X의 길이)
1 <= K <= min(|A|, |B|)
1 <= |X| <= min(|A|, |B|)

Output

만약 두 곡의 A, B의 코드열의 LCS의 길이가 K이상으로 표절로 판단되면, 표절에 해당하는 LCS를 출력한다. 표절이 아니라면 LCS의 길이를 출력한다.

단, 표절일 때, LCS가 여러 가지의 경우가 있다면 아무거나 출력해도 된다.

IO Example

입력1
CCDEFABC
CDCDCD
5
CC

출력1
3

- 이 입력의 경우 K가 5 이고, LCS는 "CDC"로, 그 길이가 3이다. 따라서 표절이 아니므로 LCS의 길이인 3을 출력한다.

입력2
CCDEFABC
CDCDCD
3
CC

출력2
CDC

- 예 2의 경우는 K가 3이므로 단순 LCS인 "CCDC"는 표절 의심이 된다. 하지만 이 LCS에는 공개코드열 "CC"를 포함하므로, 공개코드열을 sub string으로 포함하지 않는 LCS가 대상이다. 따라서 이 조건에 따라 다시 LCS를 구하면 "CDC"가 하나의 예가 될 수 있으며, 이 값은 3이상이므로 "CDC"를 출력하면 된다.

입력3
AA
A
1
A

출력3
0

- 마지막 예에서는 "A"를 포함하지 않는 LCS는 구할 수 없으므로, LCS의 길이는 0이다. 따라서 표절이 아니므로 0을 출력한다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]