[BOJ C++] 백준 5582번: 공통 부분 문자열

 📚 문제

[BOJ C++] 백준 5582번: 공통 부분 문자열
https://www.acmicpc.net/problem/5582

 

---

 📝 입력 및 출력

 

---

 🔎 문제 풀이

• 이 문제는 앞서 풀었던 LCS(Longest Common Subsequence) 문제를 응용하면 해결할 수 있다. 부분 수열(Subsequence)와 부분 문자열(Substring)의 차이는 연속성에 있다.
• 공통 부분 수열(Subsequence)를 구할 때는 연속하지 않은 문자열이어도 되므로 문자가 다를 때 이전까지의 값 중 더 큰 값을 선택하여 적용하지만, 공통 부분 문자열(Substring)을 구할 때는 연속성이 깨지게 되므로 0을 저장한다.
• LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 DP를 사용하여 해결할 수 있다. 자세한 설명은 아래 링크를 참조하자.
  [이론] 최장 공통 부분 수열 (LCS, Longest Common Subsequence)

---

 ⌨️ C++ 코드

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

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

    string s1, s2;
    cin >> s1 >> s2;
    int l1 = s1.size(), l2 = s2.size(), len = 0;
    vector<vector<int>> dp(l1 + 1, vector<int>(l2 + 1));

    for (int i = 1; i <= l1; i++) {
        for (int j = 1; j <= l2; j++) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                len = max(len, dp[i][j]);
            }
            else
                dp[i][j] = 0;
        }
    }
    cout << len;
}