[BOJ] 5582 - 공통 부분 문자열 (C++)

문제

공통 부분 문자열

코드

#include <iostream>

using namespace std;

int dp[4001][4001];

int main(void){
    string a, b;
    int m = 0;

    cin >> a >> b;

    for (int i = 1; i <= a.size(); i++){
        for (int j = 1; j <= b.size(); j++){
            if (a[i-1] == b[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
                m = max(m, dp[i][j]);
            }
        }
    }
    cout << m;
    return 0;
}

접근

이 문제는 전형적인 LCS(Longest Common substring) 이다. 진행 과정은 다음과 같다.

1. 문자열A, 문자열B의 한글자씩 비교한다.
2. 두 문자가 다르다면 LCS[i][j]에 0을 표시한다.
3. 두 문자가 같다면 LCS[i - 1][j - 1] 값을 찾아 +1 한다.
4. 위 과정을 반복한다.

현재 두 문자가 같을때 두 문자의 앞 글자까지가 공통 문자열이라면 계속 공통 문자열이 이어질 것이고, 아니라면 본인부터 다시 공통 문자열을 만들어 가게 될 것이다. 따라서 위와 같은 순서로 진행하면 된다.

참고
https://velog.io/@emplam27/알고리즘-그림으로-알아보는-LCS-알고리즘-Longest-Common-Substring와-Longest-Common-Subsequence