공통 부분 수열이란, 두 문자열이 공통으로 가지고 있는 부분 수열을 말한다.


예를 들어 문자열


문자열 A : CDABE

문자열 B : CDEGT

가 있다면,


공통 부분 수열은

{},{C},{D},{E},{C,D},{D,E},{C,E},{C,D,E}

일 것이다.





1. 최장 공통 부분 수열 길이 구하기

최장 공통 부분 수열은 공통 부분 수열 중에서 길이가 가장 긴 부분 수열을 말한다.

위 예제 최장 공통 부분 수열은{C,D,E}이고, 길이가 3이다.


최장 증가 부분 수열은 또한 다음과 같은 정의를 따른다. 각 점화식을 에제를 들어 확인해보자.





(1) Ai != Bj

두 문자열 CDABE,CDEGT의 최장 공통 부분 수열을 구한다고 해보자.

여기서 맨 마지막 문자인 E와 T가 각각 다르므로 다음과 같은 경우를 고려 할 수 있다.

1. 최장공통부분 수열이 E로 끝나는 경우.

이 경우 K는 최장 공통 부분 수열에 아무련 영향을 끼치지 않으므로 없어도 상관 없다.

즉 LCS(i,j) = LCS(i,j-1)이다.


2. 최장 공통 부분 수열이 T로 끝나는경우

이 경우 E가 최장 공통 부분 수열에 아무런 영향을 끼치지 않으므로 지워도 상관없다.

이 경우엔 LCXS(i,j) = LCS(i-1,j)이다 


3. 둘 다 해당이 되지 않는 경우.

둘 다 지워도, 하나만 지워도 최장 증가 부분 수열에 영향을 끼치지 않는다. 따라서 고려 할 필요가 없다.


두 문자가 일치하지 않을 때, 최소 둘 중 하나는 최장 공통 부분 수열에 영향을 끼치지 않으므로 둘 중 하나를 지워도 상관없다.

즉 둘 중 하나를 지웠을 때의 더 큰 LCS가 LCS(i,j)이다.

따라서 LCX(i,j) = max(LCS(i-1,j),LCS(i,j-1))임을 알 수 있다.



(2) Ai == Bj

두 문자열 CDABE CDE라고 가정해보자. 맨 뒤의 문자 E가 설 일치하는데, 공통 문자인 E는 최장 공통 부분 수열에 반드시 포함될 것이다.

따라서 이 두 문자열을 지운다면, 최장 공통 부분 수열에서 또한 E가 사라질 것이라는 것을 알 수 있다.

즉 최장 증가 부분 수열의 길이 또한 1 감소하므로, LCX(i,j) = LCS(i-1,j-1) + 1이다.





이제 위 공식을 이용하여 구현하면 된다. 각 인덱스는 현재 문자열의 길이라고 생각하면 된다.


 

 

 C (j=1)

 D (j=2)

 E (j=3)

 G (j=4)

 T (j=5)

 

 0

 0

 0

 0

 0

 0

 C (i=1)

 0

 

 

 

 

 

 D (i=2)

 0

 

 

 

 

 

 A (i=3)

 0

 

 

 

 

 

 B (i=4)

 0

 

 

 

 

 

 E (i=5)

 0

 

 

 

 




맨첨 1행, 1열들은 모두 0으로 치워지는데 이는 빈 수열을 뜻한다. 빈 수열과 문자열의 최장 증가 부분 수열은 0이기 때문이다.



밑은 앞서 확인한 공식으로 작성한 테이블이다.


 

 

 C (j=1)

 D (j=2)

 E (j=3)

 G (j=4)

 T (j=5)

 

 0

 0

 0

 0

 0

 0

 C (i=1)

 0

 1

 1

 1

 1

 1

 D (i=2)

 0

 1

 2

 2

 2

 2

 A (i=3)

 0

 1

 2

 2

 2

 2

 B (i=4)

 0

 1

 2

 2

 2

 2

 E (i=5)

 0

 1

 2

3

 3

 3


LCS(5,5)=3으로, 최장 공통 부분 수열의 길이는 3임을 알 수 있다.


int LCS(string& input, string& compare){
    int cache[1001][1001];
    memset(cache,0,sizeof(cache));
    for(int i=1;i<=compare.length();i++){
        for(int j=1; j<=input.length();j++){
            if(compare[i-1] == input[j-1]){
                cache[i][j] = cache[i-1][j-1] +1;
                }
            else{
                cache[i][j] = max(cache[i-1][j], cache[i][j-1]);
            }
        }
    }
    return cache[compare.length()][input.length()];
}



1. 최장 공통 부분 수열 구하기


이는 우리가 구한 2차원 배열을 역추적 하여 구할 수 있다.


 

 

 C (j=1)

 D (j=2)

 E (j=3)

 G (j=4)

 T (j=5)

 

 0

 0

 0

 0

 0

 0

 C (i=1)

 0

 1

 1

 1

 1

 1

 D (i=2)

 0

 1

 2

 2

 2

 2

 A (i=3)

 0

 1

 2

 2

 2

 2

 B (i=4)

 0

 1

 2

 2

 2

 2

 E (i=5)

 0

 1

 2

3

 3

 3



최장 증가 부분 수열을 찾는 공식을 잘 고려해 보자.


우리가 찾아야 하는건 Ai == Bi인 문자이다.


Ai == Bj일 때 LCS(i,j) = LCS(i-1,j-1) + 1였는데. 이를 고려해 역추적 해나가면 된다.

다만 또 고려할 것이 있는데, LCX(i,j) = max(LCS(i-1,j),LCS(i,j-1))의 경우이다.

Ai != Bj일 지라도, LCS(i,j) = max(LCS(i-1,j),LCS(i,j-1))를 통해 LCS(i-1,j-1) + 1가 도출 될 수 있다.

따라서 LCS(i-1,j), LCS(i,j-1)이 둘 다 LCS(i,j)보다 작으면서, LCS(i-1,j-1)이 LCS(i,j)보다 작은 경우가 Ai==Bj일 때이다. 

즉 LCS[i][j] > LCS[i-1][j-1] && LCS[i][j] > LCS[i][j-1] && LCS[i][j] > LCS[i-1][j])를 조건으로 코드를 구현하면 된다.


밑은 해당 코드이며, output에 최장 공통 부분 수열 문자열이 저장된다.


string output;
void backTracking(int m, int n){
    if(m==0 || n ==0) return;
    if(cache[m][n] > cache[m-1][n-1] && cache[m][n] > cache[m][n-1] && cache[m][n] > cache[m-1][n]){
        //문자열 인덱스는 캐시 인덱스보다 1씩 더 작다. 
        output = input[n-1] + output;
        backTracking(m-1, n-1);
    }else if(cache[m][n] > cache[m-1][n] && cache[m][n] == cache[m][n-1]){
        backTracking(m, n-1);
    }else{
          backTracking(m-1, n);
    }
}


+ Recent posts