BOJ)9252 LCS 2

문제: icpc.me/9252

LCS를 구해주는 문제이다. 다이나믹 프로그래밍을 통하여 LCS를 구해준 뒤 백트래킹하여 해당 LCS를 출력해주면 된다.

dp테이블의 정의는 dp[x][y]는 첫번째 문자열을 x까지 두번째 문자열을 y까지 봤을 때 LCS의 크기이다.

점화식은 (if a[x]!=b[y]) dp[x][y]=max(dp[x][y-1],dp[x-1][y]) else dp[x][y]=dp[x-1][y-1] 이 된다. 

소스코드에서는 테이블의 정의를 반대로 사용하였다.

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <iostream>
using namespace std;
string a, b;
int dp[1001][1001];
pair<int, int> back[1001][1001];
int alen, blen;
int func(int i, int j){
    if (alen == i || blen == j)return 0;
    int& ret = dp[i][j];
    if (ret != -1)return ret;
    if (a[i] == b[j]) {
        back[i][j] = { i + 1,j + 1 };
        return ret = 1 + func(i + 1, j + 1);
    }
    int x = func(i + 1, j);
    int y = func(i, j + 1);
    if (x > y) {
        back[i][j] = { i + 1,j };
        return ret = x;
    }
    else {
        back[i][j] = { i,j + 1 };
        return ret = y;
    }
}
int main(){
    cin >> a >> b;
    alen = a.size();
    blen = b.size();
    memset(dp, -1, sizeof(dp));
    printf("%d\n", func(0, 0));
    int x, y;
    x = y = 0;
    while (x != alen&&y != blen) {
        if (a[x] == b[y])
            printf("%c", a[x]);
        int tx = x;
        x = back[x][y].first;
        y = back[tx][y].second;
    }
    return 0;
}