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

 LCS의 정의

• 가장 긴 공통 부분 문자열 (Longest Common Substring)

두 문자열의 가장 긴 부분 문자열이다.

문자열이란 끊어지지 않는 문자들의 연속이다.

• 가장 긴 공통 부분 수열 (Longest Common Sequence)

두 문자열의 가장 긴 부분 수열이다.

부분 수열이란 원래 수열에서 임의의 원소를 0개 이상 지워서 만든 수열이다.

이 포스팅에서는 가장 긴 공통 부분 문자열을 다루며,

다루어지는 주제는 다음과 같다.

• N^2 풀이
• 경로 추적

 N^2 풀이

동적 계획법을 사용하여 문제를 풀어보자.

작은 문제부터 시작하여 큰 문제를 해결하는 것 이다!

int solve(int  i,  int  j)   // A[0...i]와  B[0...j]에서,  A[i]와 B[j]를 공통된 끝으로 갖는 최대 부분 문자열의 길이

위와 같이 정의하면, 다음과 같은 점화식이 유도되며,

LCS(i,  j)의 값을 Cache[i][j]에 캐싱하면 반복문으로도 해결할 수 있다.

재귀를 추적하면 A[0],  B[0]에서 시작해서.

매 단계마다 A 또는 B를 한칸씩 증가시키면서,

모든 A[i],  B[j]의 쌍에 대해 위의 루틴을 실행한다.

A[i]와 B[j]가 동일한 경우에는,

부분 문자열의 길이가 1 늘어난 것이고,

A[i],  B[j]가 동일하지 않은 경우에는,

부분 문자열이 끊긴 것이므로,  0을 반환해야 한다.

TOP-DOWN

#include <bits/stdc++.h>
using namespace std;
const int SIZE = 100;
int cache[SIZE+1][SIZE+1];
char A[SIZE+1];
char B[SIZE+1];
int LCS(int i, int j){
        //! base condition.
        if(i==0 || j==0) return 0;

        //! memoization.
        if(cache[i][j] != -1) return cache[i][j];

        //! solving.
        if(A[i] == B[j]) cache[i][j] = LCS(i-1, j-1) + 1;
        else cache[i][j] = 0;
        return cache[i][j];
}
int main()
{
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        memset(cache, -1, sizeof cache);
        cin >> (A+1);
        cin >> (B+1);
        int ans = 0;
        for(int i=0; i<strlen(A); i++){
                    for(int j=0; j<strlen(B); j++){
                            ans = max(ans, LCS(i, j));
                    }
        }
        cout << ans;
}

BOTTOM-UP

#include <bits/stdc++.h>
using namespace std;

const int SIZE = 100;
int cache[SIZE+1][SIZE+1];
char A[SIZE+1];
char B[SIZE+1];

int main()
{
        cin.tie(nullptr);
        ios::sync_with_stdio(false);

        memset(cache, 0, sizeof cache);
        cin >> (A+1);
        cin >> (B+1);

        int ans = 0;
        for(int i=1; i<=strlen(A+1); i++){
                for(int j=1; j<=strlen(B+1); j++){
                        if(A[i]==B[j])  cache[i][j] = cache[i-1][j-1]+1;
                        ans = max(ans, cache[i][j]);
                }
        }
        cout << ans;
}

 경로 추적

다음은 cache[i][j]를 시각화 한 것 이다.

substring은 각 문자열에서 인접하기 때문에,

substring이 끝나는 지점(값이 가장 큰 지점)에서 좌측 상단 방향으로 전진하면 된다.

 관련 문제

5582번: 공통 부분 문자열

9249번: 최장 공통 부분 문자열

16908번: 가장 긴 공통 부분 문자열