백준 5582 공통 부분 문자열 C++

https://www.acmicpc.net/problem/5582

5582번: 공통 부분 문자열

처음에 어렵게 생각해서 kmp로 풀어야하나 싶었지만 그러면 약 4000 * 4000 개 경우에 대해 4000 + 4000번의 kmp 알고리즘을 수행해야하기 때문에 (kmp : O(n+m)) 시간초과일거라 생각했지만 제출해보니 역시 시간초과였습니다.

 

하지만 dp로 쉽게 풀 수 있었습니다. dp[m][n] 을 문자열 s1, s2의 m, n 번째 문자가 일치할 때 최대 길이로 잡으면 결국 이전 문자까지의 최대 길이에 하나 더 연결되는 것을 찾은 것이므로 

dp[m][n] = dp[m - 1][n - 1] + 1 입니다. 

최종적으로 dp에 저장된 값 중 최대값이 최대 공통 문자열의 길이입니다.

 

코드는 다음과 같습니다.

#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>

using namespace std;

string s1, s2;
int result = 0;
int dp[4001][4001]; // dp[i][j] = dp[i-1][j-1] + 1 
// dp[i][j] : s1의 i번째랑 s2의 j번째가 일치할 때 최대 길이 

void init()
{
    cin >> s1 >> s2;
}

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    init();
    
    memset(dp, 0, sizeof(dp));   
    
    for(int i = 0; i < s1.size(); i++) {
        if(s1[i] == s2[0]){
            dp[i][0] = 1;
            result = 1;
        }
    }
    
    for(int j = 0; j < s2.size(); j++) {
        if(s2[j] == s1[0]) {
            dp[0][j] = 1;
            result = 1;
        }
    }
    
    for(int i = 1; i < s1.size(); i++) {
        for(int j = 1; j < s2.size(); j++) {
            if(s1[i] == s2[j]) {
                dp[i][j] = dp[i-1][j-1] + 1;
                result = max(result, dp[i][j]);
            }
        }
    }
    
    cout << result;
}