[알고리즘] 가장 긴 공통 부분 문자열 (LCS - Longest Common SubString)

LCS(Longest Common SubString)이란?

• LCS는 가장 긴 공통 부분 문자열을 뜻한다.
• 문자열은 끊어지지 않는 문자들의 연속을 뜻한다.

LCS 풀이 알고리즘

• 기본적으로 O(n^2) 풀이가 일반적이다.
• 기본적인 점화식은 아래와 같다.

  DP[i][j] : (i,j)를 끝으로 하는 가장 긴 부분 문자열의 길이
  DP[i][j] = DP[i-1][j-1] + 1 (A[i] == B[j])
  DP[i][j] = 0 (A[i] != B[j])

소스 코드

1. Bottom-UP 방식

int result = 0;
for (int i = 0; i < A.length(); i++) {
    for (int j = 0; j < B.length(); j++) {
        if (A.charAt(i) == B.charAt(j)) {
            if (i - 1 < 0 || j - 1 < 0) dp[i][j] = 1;
            else dp[i][j] = dp[i - 1][j - 1] + 1;
            result = Math.max(result, dp[i][j]);
        } else
            dp[i][j] = 0;
    }
}

2. Top-Down 방식

public static int solve(int i, int j) {
    if (i < 0 || j < 0) return 0;
    if (dp[i][j] != -1) return dp[i][j];

    if (A.charAt(i) == B.charAt(j)) dp[i][j] = solve(i-1, j-1) + 1;
    else dp[i][j] = 0;

    return dp[i][j];
}

public static void main(String[] args) throws IOException {
    int result = 0;
    for (int i = 0; i < A.length(); i++) {
        for (int j = 0; j < B.length(); j++) {
            result = Math.max(result, solve(i, j));
        }
    }
}