BOJ - 5582 공통 부분 문자열

5582번 공통 부분 문자열

주어진 두 문자열에서 서로 공통된 최장 문자열의 길이를 구하는 문제이다.

dynamic programming을 통해 정보를 유지하며 문제를 해결할 수 있다.

두 문자열을 탐색하며 서로 같은 문자가 있는 경우 동일한 문자가 나오기 이전 까지의 문자열의 최대 길이에 +1을 해 주는 것이다.

예를 들어 ABRACAD와 ECADAD가 있다고 하자.

그림에서 ECAD와 ABRACAD를 보자. 맨 마지막 글자가 D로 서로 일치하기 때문에 ECA와 ABRACA가 이루는 최대 공통 문자열의 길이에 +1을 해 주면 된다.

두 문자가 이루는 최대 길이의 공통 문자열은 CA이기 때문에 D까지 포함하게 되면 CAD가 되며 길이는 3이 되는 것이다.

위의 예제처럼 현재 탐색할 문자를 기준으로 만약 두 문자가 서로 같다면 그 문자가 나오기 전 까지의 공통 문자열의 최대 길이에 +1을 해 주고, 만약 두 문자가 다르다면 공통 문자열이 아니므로 0을 해 주는 것이다.

그리고 위 결과를 유지함으로써 똑같은 연산의 반복을 줄일 수 있다.

코드

#include <iostream>

using namespace std;

int arr[4001][4001];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    string str1;
    string str2;
    cin >> str1 >> str2;

    int max = 0;
    for(int i=1;i<=str1.size();i++)
    {
        for(int j=1;j<=str2.size();j++)
        {
            if(str1[i-1] == str2[j-1])
            {
                arr[i][j] = arr[i-1][j-1] + 1;
                if(arr[i][j] > max)
                    max = arr[i][j];
            }
        }
    }

    cout << max;
    return 0;
}

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