[Gold V] 공통 부분 문자열 - 5582

[문제 위치]

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

[문제 풀이]

DP 문제의 대표적 유형 중 하나인 LCS 문제이다.

1. 두 문자의 문자가 같으면:
   • dp[i][j] = dp[i-1][j-1] + 1
2. 두 문자가 다르면:
   • dp[i][j] = 0

LCS 알고리즘은 다음을 따른다. 따라서 상기의 내용만 구현해주면 간단한 문제이다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

int longest_common_substring(const string& s1, const string& s2) {
    int n = s1.length();
    int m = s2.length();

    // 동적 프로그래밍 테이블 초기화
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    int maxLength = 0;

    // dp 테이블 채우기
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                maxLength = max(maxLength, dp[i][j]);
            }
        }
    }

    return maxLength;
}

int main() {
    fastio;  // 입출력 속도 향상

    string s1, s2;
    cin >> s1 >> s2;

    int result = longest_common_substring(s1, s2);
    cout << result << endl;

    return 0;
}