LCS(Longest Common Subsequence) 알고리즘 C언어

LCS(Longest Common Subsequence) 알고리즘

---

LCS는 가장 긴 공통 부분 문자 수열 또는 최장 공통 문자 수열을 의미 합니다.

---

LCS를 구하는 방법

LCS를 구하는 방법은 생각보다 간단 합니다. 

str1 = CAPCAK

str2 = ACAYKP

두 개의 문자열을 가지고 Table의 값을 채우는 방법을 설명 드리겠습니다.

배열 맨 앞은 0으로 채워줍니다. 

• 동일       한 문자가 탐색 되면   :  대각선 ↖의 방향의 값을 비교하여 해당 값보다 1 을 증가 시켜줍니다.
• 동일하지 않은 문자가 탐색 되면 : 이전 행의 값, 이전 열의 값을 비교하여 큰 값을 입력 합니다.

결과 : 4 (Table의 마지막 값)

소스 코드를 이용해서 다시 설명 해보겠습니다.

    for (int i = 1; i < str1_len; i++) {
        for (int j = 1; j < str2_len; j++) {
            if (str1[i] == str2[j]) {
                Table[i][j] = Table[i - 1][j - 1] + 1;
            }
            else {
                Table[i][j] = MAX(Table[i - 1][j], Table[i][j - 1]);
            }
        }
    }

str1, str2 두개의 문자열이 있고 해당 문자열들의 길이 만큼 반복문으로 탐색을 합니다. 

• 두개의 문자열이 같은 경우 - 대각선 ↖의 방향의 문자열에서 +1을 더한 숫자를 Table에 입력을 합니다.  
• 두개의 문자열이 다른 경우 - Table의 'i-1' 인덱스와, 'j-1' 인덱스를 비교하여 더 큰 숫자를 입력 합니다. 

이렇게 Table를 완성 시키면 맨 마지막 Table의 값이 입력된 수는 LCS를 의미하게 됩니다. 

---

LCS 문자열을 구하는 방법

LCS를 구하는 방법보다 조금 더 어렵습니다. 하지만 조금만 더 집중해서 보면 크게 다를 것이 없습니다. 

그 이유는 LCS를 구하면서 이용한 Table를 사용하고 배열을 역으로 탐색한다고 생각하면 됩니다. 

그림을 이용해서 먼저 설명을 드리겠습니다.

1.이전 열과 비교한다.

2.이전 열과 값이 다른 경우

2.a) 이전 열과, 이전 행의 값을 비교해서 같은지 확인한다.

2.b) 같은 경우 해당 문자를 저장하고 대각선 방향으로 이동한다.

(P와 A를 비교한 부분이 헷갈릴 수도 있지만 이전 열과, 이전 행의 값이 다르기 때문에 조건문을 지나감)

(조건문이 자나갔기 대문에 i의 값이 줄어들어 c열의 탐색 시작을 합니다.)

3. 2를 계속 반복 한다.

결과 : ACAK ( 추가한 문자열 역으로 출력을 해야 합니다. )

소스 코드를 이용해서 다시 설명 해보겠습니다.

    char LCS_Str[10] = {'\0',};
    int LCS_len = Table[str1_len-1][str2_len-1]-1; 
 
    int i = str1_len - 1;
    for (int j = str2_len - 1; j > 0; ) {
        if (Table[i][j] == Table[i-1][j]) {
            i--;
        }
        else if (Table[i][j] == Table[i][j - 1]) {
            j--;
        }
        else if (Table[i - 1][j] == Table[i][j - 1]) { 
            LCS_Str[LCS_len--] = str2[j--];
            i--;
        }
        else if (Table[i - 1][j] == Table[i][j - 1]) {
            LCS_Str[LCS_len--] = str2[j--];
        }
    }

1. Table 맨 마지막부터 시작을 하면서 역방향으로 탐색을 합니다. 

2. 현재 값과 이전 행의 값이 다른 경우, 이전 행, 이전 열의 값을 비교합니다.

   만약 이전 행과 열의 값이 같은 경우 해당 문자를 LCS_Str 배열에 넣어줍니다.  

( LCS_str 배열을 나중에 역방향으로 출력 할 수도있지만 저는 LCS의 크기를 이용해서 역방향 입력을 합니다. )

( LCS의 크기는 Table의 마지막 값 입니다. )

3. 2번을 계속 반복합니다. 

---

전체 소스 코드

#include <stdio.h>
#include <malloc.h>
 
#define MAX(a,b) ((a)>(b)? (a):(b))
 
int _strlen(char* str) {
    int size = 0;
    while (str[size++]);
    return size-1;
}
 
void strAddZero(char* str) {
    if (_strlen(str) == 0) {
        str[0] = '\0';
        return;
    }
 
    int cur = 0;
    char temp = str[cur];
    char temp2;
    while (str[cur]) {
        temp2 = str[cur + 1];
        str[cur + 1] = temp;
        temp = temp2;
        cur++;
    }
    str[cur+1] = '\0';
    str[0] = '0';
}
 
int main() {
    int Table[15][15] = { 0, };
    
    char str1[10];    int str1_len;
    char str2[10];    int str2_len;
 
    scanf("%s", str1);
    scanf("%s", str2);
 
    strAddZero(str1);
    strAddZero(str2);
 
    str1_len = _strlen(str1);
    str2_len = _strlen(str2);
 
    // set table
    for (int i = 1; i < str1_len; i++) {
        for (int j = 1; j < str2_len; j++) {
            if (str1[i] == str2[j]) {
                Table[i][j] = Table[i - 1][j - 1] + 1;
            }
            else {
                Table[i][j] = MAX(Table[i - 1][j], Table[i][j - 1]);
            }
        }
    }
 
    char LCS_Str[10] = {'\0',};
    int LCS_len = Table[str1_len-1][str2_len-1]-1; 
 
    int i = str1_len - 1;
    for (int j = str2_len - 1; j > 0; ) {
        if (Table[i][j] == Table[i-1][j]) {
            i--;
        }
        else if (Table[i][j] == Table[i][j - 1]) {
            j--;
        }
        else if (Table[i - 1][j] == Table[i][j - 1]) { 
            LCS_Str[LCS_len--] = str2[j--];
            i--;
        }
        else if (Table[i - 1][j] == Table[i][j - 1]) {
            LCS_Str[LCS_len--] = str2[j--];
        }
    }
 
    printf("LCS Size : %d,   LCS String : %s\n", Table[str1_len - 1][str2_len - 1], LCS_Str);
}