[Algorithm]Baekjoon 5582번 :: 공통 부분 문자열

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

5582번: 공통 부분 문자열

 
 
int dp[4001][4001] = { 0 };
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int answer = 0;
    string s1, s2;
 
    cin >> s1 >> s2;
 
    for (int i = 1; i <= s1.size(); ++i)
    {
        for (int j = 1; j <= s2.size(); ++j)
        {
            if (s1[i - 1] == s2[j - 1])
            {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else
            {
                dp[i][j] = 0;
            }
 
            answer = max(answer, dp[i][j]);
        }
    }
 
    cout << answer;
}
 

 

공통문자열을 찾는 LCS문제이다.

즉, 두 문자열이 주어졌을 때 '연속된' 공통된 문자열의 길이를 구하는 문제이다.

 

만약 연속되지 않아도 되는 공통부분문자열을 구해야 하는 문제라면, s1[i-1]과 s2[j-1]이 달랐을 때 dp테이블을 업데이트하는 방식이 달라진다.

위는 그냥 0을 넣었지만, 부분문자열을 구할때는 dp[i-1][j]와 dp[i][j-1] 중, 큰 값을 업데이트 하면 된다.