[1][LCS : 최장 공통 부분 수열 알고리즘] (Longest Common Substring)

최장 공통 부분 수열( LCS : Longest common substring )

최장 공통 부분 수열(이하 LCS)은 주어진 여러 개의 수열 모두의 부분수열이 되는 수열들 중에 가장 긴 것을 찾는 문제이다.

 

여기서 공통 부분 수열이라함은 예를 들어 ABCD ADEFB 두 문자열이 있을 때, 공통 부분 수열은 

 

A D AD AB 라고 할 수 있다. 여기서 최장 공통 부분 수열은 이들중 가장 길이가 긴 수열이므로 AD 혹은 AB가 된다.

 

이 LCS를 구하기 위해서 대표적으로 사용되는 예인 ACAYKP 와 CAPCAK 로 살펴보자.

 

 

 

 

위의 표로 설명을 할텐데 안에 채워질 숫자의 의미는 해당 열와 행까지의 수열에서 LCS를 의미한다.

 

다음 그림을 참고해보자.

 

 

 

맨 첫칸부터 (0,0) 이라하면 ? 가 있는 부분은 (2,3) 이고 (2,3)의 의미는 첫번째문자열("ACAYKP") 에서 3번째 문자열까지("ACA"), 두번째문자열("CAPCAK")에서 2번째 문자열("CA")까지 중 LCS값을 의미한다.

 

따라서 두 문자열중 하나가 비어있는 (0,0) (1,0) ... (6,0) 과 (0,1) (0,2) ... (0,6) 은 0으로 모두 채운다.

 

앞으로 채워야할 칸을 ( i , j ) 라고 하고 첫번째 문자열을 arr1[], 두번째 문자열을 arr2[] 라고하자. 그리고 해당 테이블을 저장할 배열을 dp[][]라고 하자.

 

(1,1)부터 채우게 될텐데 여기서 두가지 경우가 있다.

 

1. arr1[ j ] = arr2[ i ] 인 경우

이 경우 왼쪽 대각선 위칸(dp[i-1][j-1])의 값에 1을 더하면된다.

이유는 해당 문자를 제외하고 지금까지 최대값이 dp[i-1][j-1] 인데 공통인 문자가 하나 추가되었으니 지금까지의 최대값에 1을 더해주는것이다.

 

2. arr1[ j ] ≠ arr2[ i ] 인 경우

이 경우는 새로 추가된 문자를 써도 추가되는 공통부분이 없으므로 현재까지 최대를 가져와야한다.

이경우 바로위칸(dp[i-1[j]) 또는 바로왼쪽칸(dp[i][j-1]) 중 큰 값을 가져오면된다.

 

직접 테이블을 채워나가면서 보면 이해가 쉬울것이다.

 

그 다음줄을 채우는 것도 살펴보자

 

 

 

이런 식으로 계속 채워나가게 되면 마지막 (6,6) 값이 최종 LCS가 된다.

 

 

이를 C코드로 구현하면 다음과 같다.

#include <stdio.h>

char arr[1001]; 
char arr2[1001];
int dp[1002][1002] = {0};
int max(int a, int b);
int main(){
    scanf("%s",arr);
    scanf("%s",arr2);
    int i,j;
    for(i=0;i<strlen(arr)+1;i++){
        for(j=0;j<strlen(arr2)+1;j++){
            if(i == 0 || j == 0){
                dp[i][j] = 0;
            }
            else if(arr[i-1] == arr2[j-1]){
                dp[i][j] = dp[i-1][j-1]+1;
            }
            else{
                dp[i][j] = max(dp[i-1][j],dp[i][j-1]);    
            }
        }
    }
    printf("%d",dp[strlen(arr)][strlen(arr2)]);
}

int max(int a, int b){
    if(a < b){
        return b;
    }
    else{
        return a;
    }
}