5582 공통 부분 문자열 [LCS]

LCS란 Longest Common Subsequence 즉 최장 공통 부분문자열을 구하는 알고리즘입니다.

예를들면 'ABCD' 와 'CDEFG' 라는 문자열이 있을때 'CD'라는 부분 문자열이 최장 공통 부분 문자열이 됩니다.

문자열의 길이가 짧은 경우에는 두 문자열의 모든 부분문자열을 비교해 찾을수 있지만 문자열이 길어질경우 많은 시간이 걸리게 됩니다.

다음은 모든 문자열을 비교해 찾는 소스코드입니다. 아주간단합니다.

a = input()
b = input()
a_len = len(a)
b_len = len(a)
res = 0

for i in range(b_len):
    for j in range(i + 1, b_len + 1):
        if a.find(b[i:j]) != -1:
            res = max(res, len(b[i:j]))

print(res)

하지만 이런 간단한 코드로는 시간초과로 문제를 풀수가 없습니다. 즉 이문제도 DP를 사용하여야 합니다.

문자열 'ABCD'와 'CDEFG'의 LCS를 테이블로 표현하자면 다음과 같습니다.

	C	D (CD)	E (CDE)	F (CDEF)	G (CDEFG)
A	0	0	0	0	0
B (AB)	0	0	0	0	0
C (ABC)	1	1	1	1	1
D (ABCD)	1	2	2	2	2

즉 부분문자열 'C'는 부분문자열 'A' 'AB'  일경우 LCS는 0 'ABC'일경우는 1이 됩니다. 즉 이런식으로 한문자식 비교해나가면 최대길이값을 구할수 있씁니다.

소스코드는 다음과 같습니다.

a = '0' + input()
b = '0' + input()
a_len = len(a)
b_len = len(b)
lcs = [[0] * b_len for _ in range(a_len)]
res = 0

for i in range(1, a_len):
    for j in range(1, b_len):
        if a[i] == b[j]:
            lcs[i][j] = lcs[i-1][j-1] + 1
            res = max(res, lcs[i][j])

print(res)