LCS - DP 이용

 

 

"GOOD MORNING. " 과 "GUTEN MORGEN." 문자열 비교 

 

int LCS(char* x, char* y, int i, int j, Table* table)
{
	// m행 1열에 0을 채운다.
	for (int m = 0; m <= i; m++)
		table->Data[m][0] = 0;

	// 0행 j열에 0을 채운다.
	for (int n = 0; n <= j; n++)
		table->Data[0][n] = 0;
	
	// 여긴 0, 0 부터 계산
	for (int m = 1; m <= i; m++)
	{
		for (int n = 1; n <= j; n++)
		{
			if (x[m - 1] != y[n - 1])
			{
				table->Data[m][n] = max(table->Data[m][n - 1], table->Data[m - 1][n]);
			}
			else
			{
				table->Data[m][n] = table->Data[m - 1][n - 1] + 1; 
			}
		}
	}

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

}

 

 

 초기 m = 0, n = 0 일 때 

0	G	U	T	E	N		M	O	R	G	E	N	.
G	0	0	0	0	0	0	0	0	0	0	0	0	0
O	0	0	0	0	0	0	0	0	0	0	0	0	0
O	0	0	0	0	0	0	0	0	0	0	0	0	0
D	0	0	0	0	0	0	0	0	0	0	0	0	0
	0	0	0	0	0	0	0	0	0	0	0	0	0
M	0	0	0	0	0	0	0	0	0	0	0	0	0
O	0	0	0	0	0	0	0	0	0	0	0	0	0
R	0	0	0	0	0	0	0	0	0	0	0	0	0
N	0	0	0	0	0	0	0	0	0	0	0	0	0
I	0	0	0	0	0	0	0	0	0	0	0	0	0
N	0	0	0	0	0	0	0	0	0	0	0	0	0
G	0	0	0	0	0	0	0	0	0	0	0	0	0
.	0	0	0	0	0	0	0	0	0	0	0	0	0

 

case 1

m = 1, n = 1 일 때, 

첫 문자 'G' 가 두 문자열 초기에 바로 등장하므로 table->Data[m][n]의 값을 1로 할당 

 

	G	U	T	E	N		M	O	R	G	E	N	.
G	0	0	0	0	0	0	0	0	0	0	0	0	0
O	0	1	0	0	0	0	0	0	0	0	0	0	0
O	0	0	0	0	0	0	0	0	0	0	0	0	0
D	0	0	0	0	0	0	0	0	0	0	0	0	0
	0	0	0	0	0	0	0	0	0	0	0	0	0
M	0	0	0	0	0	0	0	0	0	0	0	0	0
O	0	0	0	0	0	0	0	0	0	0	0	0	0
R	0	0	0	0	0	0	0	0	0	0	0	0	0
N	0	0	0	0	0	0	0	0	0	0	0	0	0
I	0	0	0	0	0	0	0	0	0	0	0	0	0
N	0	0	0	0	0	0	0	0	0	0	0	0	0
G	0	0	0	0	0	0	0	0	0	0	0	0	0
.	0	0	0	0	0	0	0	0	0	0	0	0	0

 

 

case 2

   이 후, n이 루프에 따라 n값이 증가하여 같은 문자를 발견할 때까지 반복한다. 그러나 같은 값은 9번 인덱스이다. 그 이전까진 다른 값이므로 max(table->Data[m][n-1] , table->Data[m-1][n]) 식에 따라 이전에 증가시킨 1을 계속 할당 

	G	U	T	E	N		M	O	R	G	E	N	.
G	0	0	0	0	0	0	0	0	0	0	0	0	0
O	0	1	1	1	1	1	1	1	1	0	0	0	0

 

 

case 3

같은 문자를 발견했으므로 (G) table->Data[m][n] = table->Data[m - 1][n - 1] + 1;  식을 사용 이전 값이 0이므로 1로 계산 한다. 

	G	U	T	E	N		M	O	R	G	E	N	.
G	0	0	0	0	0	0	0	0	0	0	0	0	0
O	0	1	1	1	1	1	1	1	1	1	0	0	0

 

 이후 값은 case2 와 같으므로 1로 채워진다. 이것을 계속 이전 값에 값을 더하고 그중 최대값을 가져오는 식으로 메모이제이션을 실행한다.