C++로 두 문자열의 가장 긴 공통 부분 문자열 길이 찾기

두 개의 소문자 문자열 X와 Y가 주어졌을 때, 두 문자열에 공통으로 나타나는 가장 긴 부분 문자열(longest common substring)의 길이를 구하는 문제입니다.

예를 들어, X = "helloworld", Y = "worldbook"이라고 하면, 두 문자열에 공통으로 포함된 가장 긴 부분 문자열은 "world"이므로 결과는 5가 됩니다.

이 문제는 동적 계획법(Dynamic Programming)을 이용해 효율적으로 해결할 수 있습니다. 풀이 과정은 다음과 같습니다.

• (m+1) × (n+1) 크기의 2차원 배열 longest를 정의합니다.
• 결과값을 저장할 변수 len을 0으로 초기화합니다.
• i를 0부터 m까지 반복하면서, 내부에서 j를 0부터 n까지 반복합니다.
• i가 0이거나 j가 0인 경우 → longest[i][j] = 0으로 설정합니다. (경계 조건)
• X[i-1]과 Y[j-1]이 같은 경우 → longest[i][j] = longest[i-1][j-1] + 1로 갱신하고, 현재 값이 len보다 크면 len, row, col을 업데이트합니다.
• 그 외의 경우(문자가 다른 경우) → 연속성이 끊기므로 longest[i][j] = 0으로 설정합니다.
• 모든 반복이 끝나면 len을 반환합니다.

여기서 핵심은 부분 수열(subsequence)과 달리 부분 문자열(substring)은 연속되어야 한다는 점입니다. 따라서 문자가 일치하지 않으면 DP 값을 0으로 초기화하여 연속성을 유지합니다.

아래 예제 코드를 통해 더 자세히 이해해 보겠습니다.

예제 코드

#include <iostream>
#include <stdlib.h>
#include <string.h>
using namespace std;
int solve(char* X, char* Y, int m, int n){
    int longest[m + 1][n + 1];
    int len = 0;
    int row, col;
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0)
                longest[i][j] = 0;
            else if (X[i - 1] == Y[j - 1]) {
                longest[i][j] = longest[i - 1][j - 1] + 1;
                if (len < longest[i][j]) {
                    len = longest[i][j];
                    row = i;
                    col = j;
                }
            }
            else
                longest[i][j] = 0;
        }
    }
    return len;
}
int main(){
    char X[] = "helloworld";
    char Y[] = "worldbook";
    int m = strlen(X);
    int n = strlen(Y);
    cout << solve(X, Y, m, n);
    return 0;
}

입력

"helloworld", "worldbook"

출력

5

이 알고리즘의 시간 복잡도는 O(m×n), 공간 복잡도 역시 O(m×n)입니다. row와 col 변수는 실제 가장 긴 공통 부분 문자열 자체를 추출할 때 활용할 수 있으며, 이 예제에서는 길이만 반환하도록 작성되었습니다.