[BOJ] 백준 5582 공통 부분 문자열

문제 링크

www.acmicpc.net/problem/5582

5582번: 공통 부분 문자열

 

풀이

기본 논리는 간단합니다. 입력받은 두 문자열을 $u$, $v$라 하고, $i$는 $u$의 인덱스, $j$는 $v$의 인덱스라 합시다. 모든 $i$, $j$ 쌍에 대해 탐색하면서, $u[i]$ == $v[j]$ 인 지점에서 다음 문자부터 시작하는 최대 길이의 공통 부분 문자열의 길이값을 가지고 테이블을 업데이트해줍니다.

 

따로 정답을 저장하는 변수를 두어 그때그때 갱신하면 쉽게 짤 수 있지만, 꼭 그런 변수를 두지 않아도 풀 수 있습니다.

 

같은 $i, j$ 지점을 보아도 현재 문자가 공통 문자열에 포함되는 것인지, 아니면 그냥 지나가는 문자인지 구분하기 위해 상태를 더 추가해주어야합니다.

다음과 같은 DP 테이블을 잡을 수 있습니다.

d[i][j][k]: $u[i], v[j]$부터 시작되는 최장 공통 부분 문자열(이하 LCS)의 길이.

단, $k = 0$이면 뒷 구간 전체에 대한 LCS의 길이.

$k = 1$이면 $u[i], v[j]$에서 시작하는 공통 부분 문자열의 길이(이후 구간에서 가장 길어야 할 필요는 없음).

정답 코드

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

string u, v;
int n, m;
int d[4444][4444][2];

int go(int i, int j, int k) {
    if (i == n || j == m) return 0;

    int &ret = d[i][j][k];
    if (ret != -1) return ret;

    ret = 0;
    if (k) {
        if (u[i] == v[j]) return ret = go(i + 1, j + 1, 1) + 1;
        else return ret = 0;
    }
    ret = max(go(i + 1, j, 0), go(i, j + 1, 0));
    if (u[i] == v[j]) ret = max(ret, go(i + 1, j + 1, 1) + 1);

    return ret;
}

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

    cin >> u >> v;
    n = u.size();
    m = v.size();
    memset(d, -1, sizeof(d));

    cout << go(0, 0, 0);
}