C++ 동적 계획법으로 푸는 가장 긴 반복 부분 문자열 문제

문자열 S가 주어졌을 때, 가장 긴 반복 부분 문자열(longest repeating substring)의 길이를 찾는 것이 이번 문제의 목표입니다. 만약 반복되는 부분 문자열이 존재하지 않는다면 0을 반환해야 합니다.

예를 들어 문자열이 "abbaba"라고 해봅시다. 이 경우 정답은 2입니다. 왜냐하면 가장 긴 반복 부분 문자열이 "ab" 또는 "ba"이고, 그 길이가 2이기 때문입니다.

문제 접근 방법

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

dp[i][j]는 인덱스 i에서 끝나는 부분 문자열과 인덱스 j에서 끝나는 부분 문자열이 공통으로 가지는 최대 길이를 의미합니다.
j를 항상 i+1부터 시작함으로써 두 부분 문자열이 같은 위치를 겹치지 않도록 보장합니다.

알고리즘 단계

n := 문자열 S의 길이로 설정합니다.
S 앞에 공백 한 칸을 붙여 인덱스를 1부터 사용할 수 있게 조정합니다.
정답을 저장할 변수 ret := 0으로 초기화합니다.
(n + 1) × (n + 1) 크기의 DP 테이블 dp를 생성합니다.
i를 1부터 n까지 순회하면서, 각 i에 대해 j를 i + 1부터 n까지 순회합니다.
- 만약 S[i] == S[j]라면:
  - dp[i][j] := max(dp[i][j], 1 + dp[i-1][j-1])
  - ret := max(ret, dp[i][j])
모든 반복이 끝난 후 ret을 반환합니다.

dp[i][j]의 값은 이전 대각선 값인 dp[i-1][j-1]에 현재 일치하는 문자 1개를 더한 것과 같습니다. 즉, 연속해서 일치하는 문자들의 개수를 누적해 나가는 방식입니다.

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int longestRepeatingSubstring(string S) {
        int n = S.size();
        S = " " + S;
        int ret = 0;
        vector<vector<int>> dp(n + 1, vector<int>(n + 1));
        for(int i = 1; i <= n; i++){
            for(int j = i + 1; j <= n; j++){
                if(S[i] == S[j]){
                    dp[i][j] = max(dp[i][j], 1 + dp[i - 1][j - 1]);
                    ret = max(ret, dp[i][j]);
                }
            }
        }
        return ret;
    }
};
main(){
    Solution ob;
    cout << (ob.longestRepeatingSubstring("abbaba"));
}

입력

"abbaba"

출력

시간 복잡도 분석

이 알고리즘은 두 개의 중첩 반복문을 사용하므로 시간 복잡도는 O(n²)이며, (n+1) × (n+1) 크기의 DP 테이블을 사용하므로 공간 복잡도 역시 O(n²)입니다. 문자열 길이가 수천 수준이라면 충분히 실용적인 성능을 보여줍니다.