(알고리즘) LCS알고리즘

<최장 공통 부분순서>

최장 공통 부분 수열(Longest Common Subsequence, LCS) 문제는 두 수열의 가장 긴 공토 부분 수열을 찾아내는 문제이다. 그 문제를 푸는 LCS 알고리즘에 대해 살펴보자.

예) "GOOD MORNING"
     "GUTEN MORGEN"

--->G,GO,GON,GMORN등


*LCS 알고리즘*
-> 두 문자열 X:<x1,x2,x3....xi>
                 Y:<y1,y2,y3...yi> 인 두 문자열

LCS의 길이를 구하는 함수를 LCS_LENGTH()라 하자
먼저, i나 j가  둘 중하나가 0이라 하면 LCS_LENGTH(xi,yj)의 결과는 0

1. 0이라는 말은 , 길이가 0이라는 의미이다.
2. 만약, 마지막 요소가 같다면 LCS_LENGTH(xi,yj)는 LCS_LENGTH(x(i-1),y(j-1))+1이다.
3. 두 문자열의 길이가 어느 한쪽도 0이 아니고 마지막요소도 서로 다른 경우에는
X(i-1),Yj와 Xi,Y(j-1) 중에서 큰 쪽이 Xi,Yj의 해이다.

-------------------------------------------------------------------------------------
다이나믹 알고리즘으로 푸는 방법이 제일 잘 알려진 방법이다. 두 문자열을 이용해서 일정한 규칙의 테이블을 만든 후, 그 테이블을 살펴보면서 최장 공통 부분 문자열을 찾아낼 수 있다. 이 경우 테이블에 따라 계산하므로 시간 복잡도는 $O(n^2)$이다.

다이나믹 프로그래밍은 아래와 같은 과정을 거친다.

1. 다음 공식에 맞춰서 표를 생성한다.
• 0 ≤ i ≤ len(A)이고 0 ≤ j ≤ len(B)일 때,
• A[i] == B[j]일 경우 LCSTable(i, j) = LCSTable(i - 1, j - 1) + 1
• 아닐 경우 LCSTable(i, j) = 0
2. 표에서 가장 큰 숫자를 확인한다.
• A = BCBBBC, B = CBBBCC 인 경우

		B	C	B	B	B	C
	0	0	0	0	0	0	0
C	0	0	1	0	0	0	1
B	0	1	0	2	1	1	0
B	0	1	0	1	3	2	0
B	0	1	0	1	2	4	0
C	0	0	2	0	0	0	5
C	0	0	0	0	0	0	1

3. 이 숫자들은 공통 부분 문자열의 길이를 나타내는 것으로, 대각선으로 왼쪽 위로 올라가면서 해당 문자를 확인해보게 되면 실제 최장 공통 부분 문자열, 즉 Longest Common Substring을 찾을 수 있다. 위의 표에서 가장 큰 것은 5이므로, 대각선으로 올라가면서 문자를 확인해보면"CBBBC"가 최장 공통 문자열임을 확인할 수 있다.

<재귀적 접근 법>

-->시간복잡도는 O(2^(n+m))이다.

typedef struct structLCSTABLE

{

int **Data;

}LCSTABLE;

int LCS(char* X, char* Y, int i, int j, LCSTABLE* table)

{

if (i == 0 || j == 0)

{

table->Data[i][j] = 0;

return table->Data[i][j];

}

else if (X[i - 1] == Y[j - 1])

{

table->Data[i][j] = LCS(X, Y, i - 1, j - 1, table) + 1;

return table->Data[i][j];

}

else{

int A = LCS(X, Y, i - 1, j, table);

int B = LCS(X, Y, i, j - 1, table);

if (A > B)

table->Data[i][j] = A;

else

table->Data[i][j] = B;

return table->Data[i][j];

}

}

<동적계획법으로 하는 LCS알고리즘>
-->이것은 시간복잡도가 O(nm)이다.

i=0,j=0 은 Table[i,j]=0으로
즉, Table[0,j]=0    Table[i,0]=0이다.

int LCS(char* X, char* Y, int i, int j, LCSTABLE* table)
{
int m = 0;
int n = 0;
for (m = 0; m <= i; m++)
table->Data[m][0] = 0;
for (n = 0; n <= j; n++)
table->Data[0][n] = 0;

for (m = 1; m <= i; m++)
{
for (n = 1; n <= j; n++)
{
if (X[m - 1] == Y[n - 1])
{
table->Data[m][n] = table->Data[m - 1][n - 1] + 1;
}
else{
if (table->Data[m][n - 1] >= table->Data[m - 1][n])
table->Data[m][n] = table->Data[m][n - 1];
else
table->Data[m][n] = table->Data[m-1][n];
}
}
}
return table->Data[i][j];
}

<동적계획법을 추적하는 메소드>
-> 이 함수는 최장공통부분의 문자열을 추적하여 반환하는 함수이다.


void LCS_TraceBook(char* X, char* Y, int m, int n, LCSTABLE* table, char* LCS)
{
if (m == 0 || n == 0)
return;
if (table->Data[m][n] > table->Data[m - 1][n]
&& table->Data[m][n] > table->Data[m][n - 1]
&& table->Data[m][n] > table->Data[m - 1][n - 1])
{
char tempLCS[100];
strcpy(tempLCS, LCS);
sprintf(LCS, "%c%s", X[m - 1], tempLCS);
LCS_TraceBook(X, Y, m - 1, n - 1, table, LCS);
}
else if (table->Data[m][n] > table->Data[m - 1][n]
&& table->Data[m][n] == table->Data[m][n - 1])
{
LCS_TraceBook(X, Y, m, n - 1, table, LCS);
}
else
{
LCS_TraceBook(X, Y, m - 1, n, table, LCS);
}
}