C++로 두 문자열의 가장 긴 공통 부분 문자열(LCS) 찾아 출력하기

이 튜토리얼에서는 두 문자열에서 가장 긴 공통 부분 문자열(Longest Common Substring)을 찾아 출력하는 프로그램을 C++로 구현하는 방법을 다룹니다.

문자열 A와 B가 주어졌을 때, 두 문자열 모두에 연속적으로 등장하는 가장 긴 부분 문자열을 찾아 출력하는 것이 목표입니다.

예를 들어 "helloworld"와 "worldbook"이라는 두 문자열이 주어진다면, 가장 긴 공통 부분 문자열은 "world"입니다.

알고리즘의 동작 원리

이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

2차원 배열 longest[m+1][n+1]을 생성합니다. 여기서 longest[i][j]는 X의 i번째 문자와 Y의 j번째 문자에서 끝나는 공통 부분 문자열의 길이를 의미합니다.
X[i-1] == Y[j-1]이면 longest[i][j] = longest[i-1][j-1] + 1로 갱신하고, 지금까지의 최대 길이와 해당 위치(행, 열)를 함께 기록합니다.
두 문자가 일치하지 않으면 연속성이 끊기므로 longest[i][j] = 0으로 설정합니다. 이것이 '부분 수열' 문제와의 가장 큰 차이점입니다.
탐색이 끝난 후, 최대 길이가 기록된 위치에서 대각선 방향으로 역추적하며 문자를 하나씩 모으면 정답 문자열을 얻을 수 있습니다.

예제 코드

#include <iostream>
#include <stdlib.h>
#include <string.h>
using namespace std;

void print_lstring(char* X, char* Y, int m, int n) {
    int longest[m + 1][n + 1];
    int len = 0;
    int row, col;

    // DP 테이블 채우기
    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;
        }
    }

    // 공통 부분 문자열이 존재하지 않는 경우
    if (len == 0) {
        cout << "There exists no common substring";
        return;
    }

    // 역추적을 통해 결과 문자열 생성
    char* final_str = (char*)malloc((len + 1) * sizeof(char));
    while (longest[row][col] != 0) {
        final_str[--len] = X[row - 1];
        row--;
        col--;
    }
    cout << final_str;
}

int main() {
    char X[] = "helloworld";
    char Y[] = "worldbook";
    int m = strlen(X);
    int n = strlen(Y);
    print_lstring(X, Y, m, n);
    return 0;
}

실행 결과

world

시간 및 공간 복잡도

시간 복잡도: O(m × n) — 두 문자열의 모든 문자 쌍을 한 번씩 비교합니다.
공간 복잡도: O(m × n) — 2차원 DP 테이블을 저장해야 합니다.

마무리

가장 긴 공통 부분 문자열 문제는 문자열이 일치하지 않을 때 값을 0으로 초기화한다는 점에서 최장 공통 부분 수열(LCS, Longest Common Subsequence) 문제와 구별됩니다. 이 차이만 이해하면 동일한 DP 프레임워크 안에서 두 문제를 모두 손쉽게 해결할 수 있습니다.