백준 5582번 : 공통 부분 문자열

  생각보다 그냥 간단하게 생각하면 풀리는 DP였다. dp[i][j]란 첫번째 string의 i번째 글자까지와 두번째 string의 j번째 글자까지 비교했을 때 마지막 글자가 포함된 제일 긴 공통 부분 문자열의 길이다.

  좀 더 구체적인 예를 들어보자면 다음과 같다. 첫번째 문자열이 ABRACA이고 두번째 문자열이 ECADADABR이라면 dp[2][3]이란 AB와 ECA를 비교했을 때 각 문자열의 마지막 문자인 B와 A가 포함된 최장 공통 부분 문자열의 길이란 뜻이다. 하지만 이 경우 B와 A가 동일하지 않으니 0이다. dp[3][9]의 경우 ABR과 ECADADABR를 비교했을 때 각 문자열의 마지막 문자인 R과 R이 포함된 최장 공통 부분 문자열의 길이란 뜻이다. 이 경우 최장 공통 부분 문자열은 ABR로 그 길이는 3이다.

 

 

  dp가 증가하는 경우는 첫번째 문자열(a)의 i번째 문자와 두번째 문자열(b)의 j번째 문자가 동일할 경우 밖에 없다. 따라서 a[i] == b[j]라면 dp[i][j] = dp[i-1][j-1] + 1인 것이다.

 

#include <iostream>
#include <string>

using namespace std;

string a, b;
int dp[4001][4001];

int strlen(string str)
{
    int len = 0;
    while(str[len]) len += 1;
    return len;
}

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> a >> b;
    
    int a_len = strlen(a);
    int b_len = strlen(b);
    int ans = 0;
    for(int i = 1; i <= a_len; i++)
    {
        for(int j = 1; j <= b_len; j++)
        {
            if(a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
            ans = max(ans, dp[i][j]);
        }
    }
    
    cout << ans;
 
    return 0;
}