[백준 5582번] 공통 부분 문자열 (C++)

문제링크 : https://www.acmicpc.net/problem/5582

5582번: 공통 부분 문자열

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

string s1, s2;
int dp[4001][4001];
int result;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> s1 >> s2;
    for(int i=0; i<s1.size(); i++)
    {
        for(int j=0; j<s2.size(); j++)
        {
            if(s1[i]==s2[j]) 
            {
                if(i==0 || j==0) dp[i][j]=1; //0일 경우 예외처리
                else dp[i][j] = dp[i-1][j-1]+1; //길이 증가
                result = max(result, dp[i][j]); //최대값 저장
            }
        }
    }

    cout << result;
    
}

기본적인 dp 식은 s1[i] == s2[j] 일 때, dp[i][j] = dp[i-1][j-1] + 1이다.

현재 가리키는 문자들이 같을 때마다 직전 dp의 길이에 + 1을 하여 길이를 늘려나간다.

 

이때 주의해야할 것은 반복문에서 인덱스가 0부터 시작한다는 점이다.

따라서 i==0 || j==0 일 때 dp식에서 범위가 벗어나므로 이에 대한 예외처리를 해주어야 한다.

이 경우 맨 첫 번째 값에 해당하므로 시작 길이를 나타내기 위해 1로 초기화해준다.

 

이후 가장 큰 길이를 따로 저장하여 출력해주면 된다.