[BOJ] C++ 5582 공통 부분 문자열 - LCS와 유사한 문제

5582번: 공통 부분 문자열

예제

ABRACADABRA
ECADADABRBCRDARA

ans : 5
------------------------------
UPWJCIRUCAXIIRGL
SBQNYBSBZDFNEV

ans : 0

---

LCS와 유사하지만 이 문제는 공통부분 문자열이 연속되어야 한다는 점이 다르다. 예를 들어 ABCD와 ABDC의 공통부분 문자열 중 BD는 존재하지 않는다. 

 

풀이는 처음부터 LCS를 고려하고 생각했다. 그 외의 방법은 떠오르지도 않아서 일단 LCS처럼 2차원 배열을 세팅해두고 이것저것 해보다 떠오른 방법이다. 

 

LCS에서 dp[i][j]는 str2 [j] 까지만 사용한 문자열과 str1 [i] 까지만 사용한 문자열의 LCS였다. 이 문제에서는 dp [i][j]를 str2 [j]와 str1 [i]를 부분 문자열 마지막 원소로 사용했을 때 부분 문자열 길이로 정했다. LIS와도 비슷한 느낌이었다. 왜 이렇게 정했냐면, LCS와 비슷하게 풀다가 연속된 문자열만 카운팅 해야 해서 이 방법을 선택했다. 그러니까 대충 감으로 했다... 원래 LCS를 몰랐다면 정말 풀기 힘들었을 것 같다.

/** 문자열 5582 공통 부분 문자열 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    string s1, s2;
    cin >> s1 >> s2;
    int ans = 0;

    vector<vector<int>> dp(s2.length(), vector<int>(s1.length(), 0));
    for (int i = 0; i < s2.length(); i++)
    {
        for (int j = 0; j < s1.length(); j++)
        {
            if (s2[i] == s1[j])
            {
                if (i == 0 || j == 0)
                    dp[i][j] = 1;
                else
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                ans = max(ans, dp[i][j]);
            }
        }
    }
    cout << ans;
}