[ dp ] LCS(Longest Common Substring)

Longest Common Substring

 

 

LCS(Longest Common Substring)은 두 문자열이 있을 때, 두 문자열의 최장 공통 부분 수열(공통되는 문자열 중, 최대 길이의 문자열)을 구하는 문제이다.

 

예를 들어 두 문자열 ACAYKP와 CAPCAK의 LCS는 ACAYKP, CAPCAK => ACAK임을 알 수 있다.

 

 

이는 간단한 dp로 풀 수 있는데, 두 문자열 a, b에 대하여 항 $dp[i][j]$를 '첫 번째 문자열 a의 구간 [ i, 끝 ], 두 번째 문자열 b의 구간 [ j, 끝 ]에 속하는 LCS 길이'라고 정의하면

 

i) a[i]와 b[j]가 같을 때: $dp(i, j)=dp(i+1, j+1)+1$

ii) 같지 않을 때: $dp(i, j)=max( dp(i+1, j), dp(i, j+1) )$

 

 

 

탑다운으로 푼 코드

#include <iostream>

using namespace std;

string a, b;
int as, bs;
int memo[1001][1001];

int dp(int x, int y)
{
    if(x==as && y==bs){ return 0; }
    if(memo[x][y]!=-1){ return memo[x][y]; }
    memo[x][y]=0;
    int &ret=memo[x][y];
    if(x<as && y<bs && a[x]==b[y]){
        ret=max(ret, dp(x+1, y+1)+1);
    }
    else{
        if(x<as){ ret=max(ret, dp(x+1, y)); }
        if(y<bs){ ret=max(ret, dp(x, y+1)); }
    }
    return ret;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    memset(memo, -1, sizeof(memo));
    cin >> a >> b;
    as=a.size(); bs=b.size();
    cout << dp(0, 0) << "\n";
    return 0;
}

 

 

바텀업으로 푼 코드

#include <iostream>

using namespace std;

int dp[1001][1001];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    string a, b;
    cin >> a >> b;
    int n=a.size(), m=b.size();
    a='#'+a;
    b='#'+b;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(a[i]==b[j]){
                dp[i][j]=dp[i-1][j-1]+1;
            }
            else{
                dp[i][j]=max(dp[i][j-1], dp[i-1][j]);
            }
        }
    }
    cout << dp[n][m] << "\n";
    return 0;
}

 

 

 

LCS 문자열 출력하기

 

 

그럼 이제 LCS 문자열도 출력해보자.

 

예를 들어 ACAYKP와 CAPCAK의 LCS는 ACAK이고 길이가 4이다.

 

 

이는 경로 역추적을 통해 구할 수 있다. 자세한 설명은 아래를 참고하면 된다.

 

https://david0506.tistory.com/39

동적계획법(경로 역추적)

 

 

바텀업으로 푼 코드

#include <iostream>

using namespace std;

int dp[1001][1001];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    string a, b;
    cin >> a >> b;
    int n=a.size(), m=b.size();
    a='#'+a;
    b='#'+b;
    //해 구하기
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(a[i]==b[j]){
                dp[i][j]=dp[i-1][j-1]+1;
            }
            else{
                dp[i][j]=max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    cout << dp[n][m] << "\n";
    
    //경로 역추적
    int x=n, y=m;
    string res;
    while(x>=1 && y>=1){
        if(a[x]==b[y]){
            res=a[x]+res;
            x--; y--;
        }
        else{
            if(dp[x-1][y]>dp[x][y-1]){ x--; }
            else{ y--; }
        }
    }
    cout << res << "\n";
    return 0;
}

 

 

탑다운으로 푼 코드

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

string a, b;
int n, m;
int memo[1005][1005];

int dp(int x, int y)
{
    if(x>=n || y>=m){ return memo[x][y]=0; }
    if(memo[x][y]!=-1){ return memo[x][y]; }
    memo[x][y]=0;
    int &ret=memo[x][y];
    if(x<n && y<m && a[x]==b[y]){
        ret=max(ret, dp(x+1, y+1)+1);
    }
    else{
        if(x<n){ ret=max(ret, dp(x+1, y)); }
        if(y<m){ ret=max(ret, dp(x, y+1)); }
    }
    return ret;
}

void tracking(int x, int y)
{
    if(x>=n || y>=m){ return; }
    if(a[x]==b[y]){
        cout << a[x];
        tracking(x+1, y+1);
    }
    else if(dp(x+1, y)>dp(x, y+1)){
        tracking(x+1, y);
    }
    else{
        tracking(x, y+1);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    memset(memo, -1, sizeof(memo));
    cin >> a >> b;
    n=a.size(); m=b.size();
    cout << dp(0, 0) << "\n";
    tracking(0, 0);
    return 0;
}