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

5582번: 공통 부분 문자열

LCS를 응용하여 풀었다. 문자열 크기만큼 반복문을 돌면서 같은 문자일 경우 이전 문자 카운트 + 1을 배열에 저장해주고 result 보다 클 경우 이를 result에 저장한 후 출력해주었다. 오랜만에 LCS도 상기시켜준 좋은 문제였다.

#include <iostream>

using namespace std;

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

void solution() {
    for (int i = 0; i < s1.size(); i++) {
        for (int j = 0; j < s2.size(); j++) {
            if (s1[i] == s2[j]) {
                dp[i + 1][j + 1] = dp[i][j] + 1;
                result = max(result, dp[i + 1][j + 1]);
            }
        }
    }

    cout << result;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> s1;
    cin >> s2;

    solution();

    return 0;
}