C++로 구현하는 두 문자열 간 가장 긴 공통 부분 수열(부분 문자열 조건) 찾기

두 문자열 X와 Y가 주어졌을 때, X의 부분 수열(subsequence) 중에서 Y의 부분 문자열(substring)이 되는 가장 긴 것의 길이를 구하는 문제입니다.

예를 들어 X = "ABCD", Y = "BACDBDCD"라고 한다면 결과는 3이 됩니다. "ACD"가 X의 부분 수열이면서 동시에 Y의 부분 문자열이 되는 가장 긴 경우이기 때문입니다.

동적 계획법(Dynamic Programming) 접근

이 문제는 동적 계획법을 활용해 효율적으로 해결할 수 있습니다. X의 길이를 n, Y의 길이를 m이라고 할 때, (m+1)×(n+1) 크기의 DP 테이블을 생성합니다.

여기서 DP[i, j]의 값은 X[0…j]의 부분 수열 중 Y[0…i]의 부분 문자열이 되는 최대 길이를 의미합니다. 각 셀은 아래 규칙에 따라 채워집니다.

• i를 1부터 m까지 반복합니다.
  • j를 1부터 n까지 반복합니다.
    • X[j-1]과 Y[i-1]이 같다면: DP[i, j] = 1 + DP[i-1, j-1]
    • 그렇지 않다면: DP[i, j] = DP[i, j-1]

모든 셀을 채운 후, 최종 답은 max(DP[i, n]) (단, 1 ≤ i ≤ m)이 됩니다. 이는 Y의 어느 위치에서든 끝나는 부분 문자열 중 가장 긴 값을 선택하는 과정입니다.

C++ 구현 예제

#include<iostream>
#define MAX 100
using namespace std;

int maxSubLength(string x, string y) {
    int table[MAX][MAX];
    int n = x.length();
    int m = y.length();

    // DP 테이블 초기화
    for (int i = 0; i <= m; i++)
        for (int j = 0; j <= n; j++)
            table[i][j] = 0;

    // DP 테이블 채우기
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (x[j - 1] == y[i - 1])
                table[i][j] = 1 + table[i - 1][j - 1];
            else
                table[i][j] = table[i][j - 1];
        }
    }

    // 최대값 탐색
    int ans = 0;
    for (int i = 1; i <= m; i++)
        ans = max(ans, table[i][n]);

    return ans;
}

int main() {
    string x = "ABCD";
    string y = "BACDBDCD";
    cout << "Maximum subsequence substring length: " << maxSubLength(x, y);
}

실행 결과

Maximum subsequence substring length: 3

시간 복잡도 분석

위 알고리즘은 DP 테이블의 모든 셀을 한 번씩 채우므로 시간 복잡도는 O(m×n)이며, 공간 복잡도 역시 O(m×n)입니다. 두 문자열의 길이가 각각 최대 100일 때 MAX 크기의 정적 배열로 충분히 처리할 수 있습니다.