최장 공통 부분 수열 (LCS)

Longest Common Subsequence. 두 수열이 주어졌을 때, 모두의 부분 수열이 되는것 중에 가장 긴 것을 찾는 문제이다.

최장 공통 문자열의 개념에서 조금 확장시키면 어렵지 않게 구할 수 있다.

점화식을 사용하는 DP의 일종이다.

 

우선 최장 공통 문자열을 구하는 과정이다.

1. 두 문자열을 한글자씩 비교한다.
2. 두 문자가 다르면 LCS[i][j]에 0을 표시한다.
3. 두 문자가 같으면 LCS[i-1][j-1]에 1을 더한다.
4. 위의 과정을 반복한다.

 

// i, j는 1부터
if (str1[i-1] == str2[j-1])
    LCS[i][j] = LCS[i-1][j-1] + 1;
else
    LCS[i][j] = 0;

점화식을 코드로 작성하면 위와 같다.

 

 

이번에는 최장 공통 부분 수열을 구할 차례이다.

위의 과정에서 두 문자가 다를때의 식만 다르다.

 

if (str1[i-1] == str2[j-1])
    LCS[i][j] = LCS[i-1][j-1] + 1;
else
    LCS[i][j] = max(LCS[i][j-1], LCS[i-1][j]);

두 문자가 다를때의 식이 저렇게 나오는 이유는 부분 수열은 연속된 값이 아니기 때문이다.

LCS[i][j-1], LCS[i-1][j]가 현재 문자를 비교하는 과정의 이전 과정인 것이다.

길이만 구하는 경우라면 LCS[str1.size()][str2.size()]로 구할 수 있고 실제 문자열이 필요한 것이라면 LCS배열의 가장 끝에서부터 0을 만날때까지 역순으로 추적한 뒤에 문자열을 뒤집으면 된다.