[DP] BOJ 5582 공통 부분 문자열 (C++)

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

5582번: 공통 부분 문자열

 

문제 해결 알고리즘

 

 

간단한 문자열 + DP 문제

 

문자열을 탐색할 때, 두 문자가 같으면 그 두개의 전에 해당하는 배열에서 +1한 값을 입력한다.

거기서 최댓값을 구해준다.

 

 

소스 코드

 

#include <bits/stdc++.h>
using namespace std;

int dp[4001][4001], result = 0;

int main(){
    string str1, str2; cin >> str1 >> str2;

    str1 = '0' + str1;
    str2 = '0' + str2;

    for(int i=1;i<str1.size();i++){
        for(int j=1;j<str2.size();j++){

            if(str1[i] == str2[j])  dp[i][j] = dp[i-1][j-1] + 1;

            result = max(result, dp[i][j]);
        }
    }

    cout << result;

}