LCS 최장 공통 부분 수열

먼저 용어를 간단히 정리하자면, LCS(Longest Common Subsequence) 로 Subsequence 는 부분 수열이기 때문에, 꼭 연속적인 문자열일 필요가 없다. 만약 substring 이면 연속적인 문자열이다.

 

 

O(N^2)

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

9251번: LCS

 

DP 정의는 다음과 같다.

dp[p][q] : 첫 번째 문자열 p, 두 번째 문자열 q 위치까지의 LCS 길이

  if string_1 [p] == string_2 [q]:
       dp[p][q] = dp[p-1][q-1] + 1
  else :
       dp[p][q] = max( dp[p-1][q], dp[p][q-1] )

 위 dp 정의에 따라 두 문자열의 dp 배열 저장 값(그림)을 보면 이해하기 쉽다.

 

# Top-down

int dp[1001][1001];
string s1, s2;
 
int inline max(int a,int b){return a>b?a:b;}
int solve(int p, int q){
    if(p < 0 || q < 0) 
        return 0;
    
    int &ret = dp[p][q];
    if(ret != -1){
        return ret;
    }
 
    int h = 0;
    if(p >= 0){
        h = max(h, solve(p-1, q));
    }
 
    if(s1[p] == s2[q]){
        h = max(h, solve(p-1, q-1)+1);
    }
 
    if(q >= 0){
        h = max(h, solve(p, q-1));
    }
 
    return ret = h;
}

 

# Bottom-up

int dp[1001][1001];
string s1, s2;
 
for(int i=0; i < s1.length(); i++){
    for(int j=0; j < s2.length(); j++){
        dp[i][j] = max( (i==0 ? 0 : dp[i-1][j]), (j==0 ? 0 : dp[i][j-1]));
        if(s1[i] == s2[j]){
            dp[i][j] = max(dp[i][j], (i == 0 || j == 0 ? 0 : dp[i-1][j-1]) + 1);
        }
    }
}

 

 

# 9251 LCS 소스 코드

#include<iostream>
#include<string>
#include<cstring>
 
using namespace std;
int dp[1001][1001];
string s1, s2;
 
int inline max(int a,int b){return a>b?a:b;}
int solve(int p, int q){
    if(p < 0 || q < 0) 
        return 0;
    
    int &ret = dp[p][q];
    if(ret != -1){
        return ret;
    }
 
    int h = 0;
    if(p >= 0){
        h = max(h, solve(p-1, q));
    }
 
    if(s1[p] == s2[q]){
        h = max(h, solve(p-1, q-1)+1);
    }
 
    if(q >= 0){
        h = max(h, solve(p, q-1));
    }
 
    return ret = h;
}
int main(){
    memset(dp, -1, sizeof(dp));
    cin>>s1>>s2;
 
    // cout<< solve(s1.length()-1, s2.length()-1) <<endl;
    // printf("\t");
    // for(int i=0;i<s2.length(); i++){
    //     printf(" %c", s2[i]);
    // }
    // printf("\n");
    for(int i=0; i < s1.length(); i++){
        // printf("%5c\t:", s1[i]);
        for(int j=0; j < s2.length(); j++){
            dp[i][j] = max( (i==0 ? 0 : dp[i-1][j]), (j==0 ? 0 : dp[i][j-1]));
            if(s1[i] == s2[j]){
                dp[i][j] = max(dp[i][j], (i == 0 || j == 0 ? 0 : dp[i-1][j-1]) + 1);
            }
            // printf("%d ", dp[i][j]);
        }
        // printf("\n");
    }
    cout<<dp[s1.length()-1][s2.length()-1] <<endl;
    return 0;
}

 

---

O(N^2), LCS 문자열 출력

LCS 문자열까지 출력하기 위해선 dp 의 마지막 인덱스(dp[s1.length()-1][s2.length()-1]) 부터 0,0 까지 이동해가며, 문자열을 추적해야한다.

 

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

9252번: LCS 2

 

9252 LCS 2 소스코드

#include<iostream>
#include<string>
#include<cstring>
 
using namespace std;
int dp[1001][1001];
string s1, s2;
 
int inline max(int a,int b){return a>b?a:b;}
int solve(int p, int q){
    if(p < 0 || q < 0) 
        return 0;
    
    int &ret = dp[p][q];
    if(ret != -1){
        return ret;
    }
 
    int h = 0;
    if(p >= 0){
        h = max(h, solve(p-1, q));
    }
 
    if(s1[p] == s2[q]){
        h = max(h, solve(p-1, q-1)+1);
    }
 
    if(q >= 0){
        h = max(h, solve(p, q-1));
    }
 
    return ret = h;
}
int main(){
    memset(dp, -1, sizeof(dp));
    cin>>s1>>s2;
 
    // cout<< solve(s1.length()-1, s2.length()-1) <<endl;
    // printf("\t");
    // for(int i=0;i<s2.length(); i++){
    //     printf(" %c", s2[i]);
    // }
    // printf("\n");
    for(int i=0; i < s1.length(); i++){
        // printf("%5c\t:", s1[i]);
        for(int j=0; j < s2.length(); j++){
            dp[i][j] = max( (i==0 ? 0 : dp[i-1][j]), (j==0 ? 0 : dp[i][j-1]));
            if(s1[i] == s2[j]){
                dp[i][j] = max(dp[i][j], (i == 0 || j == 0 ? 0 : dp[i-1][j-1]) + 1);
            }
            // printf("%d ", dp[i][j]);
        }
        // printf("\n");
    }
    cout<<dp[s1.length()-1][s2.length()-1] <<endl;
    int p = s1.length()-1, q = s2.length()-1;
    string ans = "";
    while(p >= 0 && q >= 0){
        if(s1[p] == s2[q]){
            ans = s1[p] + ans;
            p--; q--;
            continue;
        }
        if(p > 0 && dp[p-1][q] == dp[p][q]){
            p--;
        }
        else if(q > 0 && dp[p][q-1] == dp[p][q]){
            q--;
        } else {
            break;
        }
    }
    cout << ans << endl;
    return 0;
}

 

 

 

---

BOJ 1958 LCS 3

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

1958번: LCS 3

이 문제는 문자열 3개의 LCS 문제이며, dp를 2차원에서 3차원으로 확장하여 풀면 된다.

#include<iostream>
#include<string>
using namespace std;
string s1,s2,s3;
int dp[101][101][101];
int main(){
    cin >> s1 >> s2 >> s3;
    int s1len = s1.length(), s2len = s2.length(), s3len = s3.length();
    for(int i = 1 ; i <= s1len; i++){
        for(int j = 1 ; j <= s2len; j++){
            for(int p = 1 ; p <= s3len; p ++){
                dp[i][j][p] = max(dp[i-1][j][p], max(dp[i][j-1][p], dp[i][j][p-1]));
                if(s1[i-1] == s2[j-1] && s2[j-1] == s3[p-1]){
                    dp[i][j][p] = max(dp[i][j][p], dp[i-1][j-1][p-1] + 1);
                }
            }
        }
    }
    cout<< dp[s1len][s2len][s3len] << endl;
    return 0;
}
 

 

 

---

O(n log n) 방법

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

13711번: LCS 4

이 문제는 n 의 길이가 100,000 까지 이므로, 기존의 O(n^2) 방법으로는 풀 수 없다. O(n log n)으로 풀기 위해선 조건이 필요한데, 문제에 쓰여있듯이 하나의 문자는 한 번만 나타나야 한다. 한 번씩 나타날 때, 이 문제를 LIS 로 응용해서 풀 수 있는데, 방법은 다음과 같다.

 

 1. 수열 A 의 값 A[i] 을 인덱스 배열 C에 저장한다. C[ A[i] ] = i
 2. 수열 B의 값을 A 값에 따른 인덱스 배열로 치환한다. B[i] = C[ B[i] ]
 3. B 배열에 LIS 를 구한다.

 

즉, A 값의 인덱스로 B 배열 값을 치환한 뒤, LIS 를 구하면 두 문자열의 LCS가 된다. 

 

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
 
int n, idx[100001], A[100001], B[100001];
 
int main(){
    scanf("%d", &n);
    for(int i=0;i<n;i++){
        scanf("%d", &A[i]);
        idx[A[i]] = i;
    }
    vector<int> ans;
    for(int i=0;i<n;i++){
        scanf("%d", &B[i]);
        B[i] = idx[B[i]];
        if( ans.empty() || ans.back() < B[i])
            ans.push_back(B[i]);
        else {
            vector<int>::iterator it = lower_bound(ans.begin(), ans.end(), B[i]);
            *it = B[i];
        }
    }
    printf("%d\n", ans.size());
    return 0;
}