[5582번] 공통 부분 문자열

 

www.acmicpc.net/problem/5582

5582번: 공통 부분 문자열

이 문제는 동적 계획법을 2차원 배열에 적용하여 풀 수 있습니다.

두 문자열을 각각 A와 B라고 할 때,

2차원 배열의 가로는 문자열 A, 세로는 문자열 B로 지정하고,

인덱스 마다 해당 지점까지 존재할 수 있는 가장 긴 부분 문자열의 길이를 저장하면 됩니다.

 

해당 지점 (X, Y). A문자열의 X까지, B문자열의 Y까지 등장할 수 있는 공통 부분 문자열의 길이는

A의 X - 1까지, B의 Y - 1까지 등장할 수 있는 공통 부분 문자열 길이에

A의 X위치, B의 Y위치의 문자열이 같은지 여부를 합하면 됩니다.

 

문자열 BCDEFD 와 DEFABCDE 의 경우를 확인해 보겠습니다.

탐색이 모두 끝나면 이런 결과가 나옵니다.

그러나 정석대로 탐색한다면 다음과 같은 결과가 나와야 합니다.

위 표와 아래 표를 보고 조금 고민해보시면,

이 문제에서는 굳이 아래 표처럼 구할 필요가 없다는 것을 알 수 있습니다.

정석대로 탐색한다면 이런 결과가 나오는게 맞습니다.

 

#include <iostream>
#include <string>
using namespace std;

int count[4001][4001];
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string A, B;
    int result = 0;
    cin >> A >> B;

    for (int x = 0; A[x] != '\0'; x++) {
        for (int y = 0; B[y] != '\0'; y++) {
            if (A[x] == B[y]) {
                if (x == 0 || y == 0) count[x][y] = 1;
                else count[x][y] = count[x - 1][y - 1] + 1;
                result = max(result, count[x][y]);
            }
        }
    }
    cout << result;
    return 0;
}