[알고리즘] 최장 공통 부분 수열 (Longest Common Subsequence LCS)

목차

LCS (Longest Common Subsequence) 최장 공통 부분 수열

LCS의 길이 찾기

$$
x_m = y_n 이면 LCS(X_m, Y_n) = LCS(X_{m-1}, Y_{n-1})+1
$$

$$
x_m \neq y_n 이면 LCS(X_m, Y_n) = max(LCS(X_{m-1}, Y_{n}), LCS(X_{m}, Y_{n-1}))
$$

 

 

https://velog.io/@emplam27/알고리즘-그림으로-알아보는-LCS-알고리즘-Longest-Common-Substring와-Longest-Common-Subsequence

문제 예시

9251번: LCS

C[i-1][j] = A의 i-1번째, B의 j번째까지의 LCS

Xi와 Yj가 같지 않다면 새로운 값을 추가할 수 없으니, 이전의 LCS값인 C[i-1][j]와 C[i][j-1] 중 큰 값을 LCS로 update한다.

모든 배열을 채우고 최대값이 LCS의 길이가 됨

String str1 = sc.next();
String str2 = sc.next();
int[][] dp = new int[str1.length() + 1][str2.length() + 1];

int ans = 0;
for (int i = 1; i <= str1.length(); i++)
    for (int j = 1; j <= str2.length(); j++) {
        if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
            dp[i][j] = dp[i - 1][j - 1] + 1;
            ans = Math.max(dp[i][j], ans);
            } else {
            dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
    }

LCS 찾기

1. LCS배열의 마지막 값에서 시작 → C[i][j]를 C[i-1][j]와 C[i][j-1] 비교
2. 둘 중 하나(또는 둘 다)와 같다면 X_i와 Y_j는 같지 않다는 의미이므로 LCS에 추가x, 해당 index로 이동
3. 둘 다 같지 않다면 X_i와 Y_j는 같다는 의미 → result에 해당하는 문자를 추가, C[i-1][j-1]로 이동
4. i와 j 둘 중 하나가 0이 될 때까지 1,2를 반복
5. result 배열을 역순으로 출력

char[] result = new char[ans];
int r = str1.length();
int c = str2.length();
int idx = 0;
while (r >= 1 && c >= 1) {
    if (dp[r][c] == dp[r - 1][c])
        r -= 1;
    else if (dp[r][c] == dp[r][c - 1])
        c -= 1;
    else {
        result[idx] = str1.charAt(r - 1);
        r -= 1;
        c -= 1;
        idx++;
    }
}