9252 LCS 2

https://www.acmicpc.net/problem/9252

9252번: LCS 2

 

Dynamic Programmming 기본 문제들 중 하나이다.

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

 

이 때, 이문제는 LCS의 길이만을 출력하는 것이 아닌, 해당 부분 문자열을 찾는 문제이다.

 

LCS를 찾는 점화식을 구하면 다음과 같다.

ACAYKP

CAPCAK

예시가 위과 같을 때, 다음과 같은 표를 만들 수 있다.

		C	A	P	C	A	K
	0	0	0	0	0	0	0
A	0	0	1	1	1	1	1
C	0	1	1	1	2	2	2
A	0	1	2	2	2	3	3
Y	0	1	2	2	2	3	3
K	0	1	2	2	2	3	4
P	0	1	2	3	3	3	4

 빨간색 숫자들은 LCS를 찾을 때 따라가는 수를 뜻한다.

점화식을 통해 위 테이블을 만들고, [6][6]에서부터 점화식에 맞게 뒤로 따라가게 되면 LCS를 찾을 수 있다.

1. 해당 숫자가 같은 방향으로 따라가면 된다. (해당 숫자가 왼쪽 수나 위쪽 수와 같으면 두 방향 중 아무방향으로 가면된다.)

2. 해당 숫자가 왼쪽 수와 위쪽 수보다 크면, 대각선방향으로 가면 된다.(해당 방향에서 왔기 때문)

3. 대각선방향으로 갈때마다 해당 문자를 추가하면 된다.

그렇게 따라가면 LCS가 "KACA"를 뒤집은 "ACAK"임을 알 수 있다.

 

 

#include <bits/stdc++.h>
 
using namespace std;
 
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
#define int long long
 
using pii = pair<int, int>;
 
const double EPS = 1e-9;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
 
 
int32_t main()
{
    cin.sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
 
    string s, key;
    cin >> s >> key;
    vector<vector<int>> dp(s.length()+1, vector<int>(key.length()+1, 0));
    
    for(size_t i=1;i<=s.length();i++)
    {
        for(size_t j=1;j<=key.length();j++)
        {
            if(s[i-1] == key[j-1]) dp[i][j] = 1+dp[i-1][j-1];
            else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }
    int y = s.length(), x = key.length();
    string ans = "";
    cout << dp[s.length()][key.length()] << endl;
 
    while(y > 0 && x > 0)
    {
        if(dp[y][x] == dp[y-1][x]) y--;
        else if(dp[y][x] == dp[y][x-1]) x--;
        else
        {
            y--;
            x--;
            ans += key[x];
        }
    }
    reverse(ans.begin(), ans.end());
    cout << ans << endl;
 
    return 0;
}