LCS(Longest Common Subsequence)

최장 공통 부분 문자열입니다.

부분이라는 뜻은 연속하지 않아도 된다는 뜻입니다. 이 문제는 두 문자열이 겹치는 문자들의 최장 길이를 구하는 문제입니다. 띄엄띄엄 겹치더라도 이들을 모아 각각 하나의 문자열을 만들었을 때 두 문자열이 같다면 공통 부분 문자열이고 이 문자열의 길이가 곧 LCS에서 구하는 답 입니다.

 

www.acmicpc.net/problem/9251

9251번: LCS

대표적인 백준 문제를 예시로 이해해 봅시다.

 

나와 있는 첫 번쨰 에시에는 두 문자열을 입력으로 받습니다.

 

a = ACAYKP

b = CAPCAK

 

두 문자열을 각각 a,b라고 정의합니다.

이때 a의 i번째까지의 문자열과 b의 j번째까지의 문자열의 lcs를 구하게 되면 곧 답이 된다는 dp식을 유도할 수 있습니다. 두 가지의 정보가 필요하므로 2차원의 배열을 사용한다면 모든 정보를 표현할 수 있습니다.

 

정보를 표현하면 다음과 같습니다. 이를 점화식으로 표현하자면 

 

if a[i] == b[j]

 

i+1번째까지의 문자열, j+1번째까지의 문자열의 lcs 길이 d[i+1][j+1]은

d[i+1][j+1] = d[i][j] + 1

else

d[i+1][j+1] = max(d[i][j+1], d[i+1][j])

가 됩니다. 매치가 되어있다면 그 이전에 매칭되었을 때의 lcs길이 + 1인 것이고 매치가 안되어있다면 둘 중 더 큰 lcs 값을 저장하면 됩니다.

 

Code

 

#include <bits/stdc++.h>
using namespace std;
string a,b;
int d[1001][1001],i,j;
int main(){
    cin >> a >> b;
    for(i = 0; i < a.size(); i++){
        for(j = 0; j < b.size(); j++){
            if(a[i] == b[j]) d[i+1][j+1] = d[i][j] + 1;
            else d[i+1][j+1] = max(d[i][j+1],d[i+1][j]);
        }  
    }
    cout << d[i][j];
}