LCS란?
Longest Common Sequence(LCS)는 두 문자열 에서 공통적으로 나타나는 가장 긴 부분 순서를 의미한다.
A = acaykp
B = capcak
- A와 B의 LCS는 acak이다.
위의 예시를 보면 A에서도 acak가 순서대로 나타나고, B에서도 acak가 순서대로 나타난다. 이때 LCS인 acak가 A와 B에 연속적으로 나타날 필요는 없다. 그저 a 다음에 c가, c 다음에 a가, a다음에 k가 나타나면 되는 것이다. 이렇듯 두 문자열에 공통적으로 나타나는 부분 순서 중 가장 긴 부분 순서가 LCS가 된다.
어떻게 구할까?
LCS에는 최적 부분 구조가 존재한다.
LCS(n, m) : An까지의 문자열과 Bm까지의 문자열의 LCS 길이
1. An = Bm 이면, LCS(n,m) = LCS(n-1, m-1) + 1 이다.
2. An =/= Bm 이면, LCS(n, m) = max(LCS(n-1, m), LCS(n, m-1)) 이다.
만약 두 문자열의 마지막 문자가 같다면, 마지막 문자을 제외한 두 문자열의 LCS에 마지막 문자를 더한 것이 두 문자열의 LCS가 된다. 반면 마지막 문자가 다른 경우에는 A의 마지막 문자와 B의 마지막 문자가 LCS에 추가될 수 있는지 각각 검사 해야 한다.
LCS 길이 구하기
Cij = LCS(i, j) 라고 하면 점화식은 다음과 같다.
Cij
= 0 if i=0 or j=0
= Ci-1, j-1 + 1 if i,j > 0 and Ai = Bj
= max(Ci-1, j, Ci, j-1) if i,j > 0 and Ai =/= Bj
점화식을 사용하여 C[0][0]부터 C[N][M]까지 동적 프로그래밍을 이용해 C배열의 값을 채울 수 있다. 그 후 C[N][M] 값이 구하고자 했던 A와 B의 LCS 길이가 된다.
LCS 값 구하기
위에서 구한 C 배열을 사용하여 LCS 배열 result를 구할 수 있다.
- i = N, j = M에서 시작한다.
- C[i-1][j], C[i][j-1] 중 C[i][j]와 같은 값이 있는지 확인한다.
2-1. 같은 값이 있다면, i와 j를 해당 칸으로 이동한다.
2-2. 같은 값이 없다면, result에 Ai를 추가하고 C[i-1][j-1]로 이동한다.- 2로 돌아가 C[i][j] = 0이 될때까지 반복한다.
