[Algorithm] 백준 5582 공통 부분 문자열 - C++, LCS, DP

5582번: 공통 부분 문자열

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

const int MAX = 4001;
int LCS[MAX][MAX];
string s1, s2;

int main(){
    int maxLength = -1;

    cin >> s1;
    cin >> s2;

    for(int i = 1; i <= s1.size(); i++){
        for(int j = 1; j <= s2.size(); j++){
            LCS[i][j] = (s1[i-1] == s2[j-1]) ? LCS[i-1][j-1] + 1 : 0;
            maxLength = max(LCS[i][j], maxLength);
        }
    }

    cout << maxLength << '\n';
}

---

기본적인 공통 부분 문자열 문제였습니다. 알고리즘을 이해한 뒤 풀이하면 쉽게 풀이할 수 있습니다.