9252 LCS2

이전 글에서 LCS 방법을 살펴보았다. 이번에는 LCS의 길이뿐만 아니라, LCS를 출력해보기로 한다.

 

LCS를 출력하기 위해선 현재 값을 갱신할 때, 이전의 어느 값에서 가져온건지를 알아야 한다.

즉, 가져오는 값을 추적할 수 있어야 한다.

LCS의 분기문을 다음과 같이 구현했었다.

if x[i] == y[j]: dp[i][j] = dp[i - 1][j - 1] + 1
else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

그런데, 위의 점화식엔 두 가지 문제가 있다.

1. 테이블에 값을 넣을 때, 어느 방향에서 온 값인지 알 수 없다.
2. 문자 비교 결과가 다를 때, else 분기문에서 위쪽의 값인지 왼쪽의 값인지 알 수 없다.

각각의 문제는 다음과 같이 생각해볼 수 있다.

1. LCS 길이를 저장하는 테이블외에 인덱스를 저장하기 위한 테이블을 만든다.
2. else 분기문 대신, else if로 방향을 구분한다.

반복문, 분기문을 다시 구성해보겠다.

for(int i = 1; i < x.length(); i++){
	for(int j = 1; j < y.length(); j++){
    	if(x[i] == y[j]){
        	dp[i][j] = dp[i - 1][j - 1] + 1;
            track[i][j] = DAIG; //대각선에서 온 값
        }
        else if(dp[i - 1][j] >= dp[i][j - 1]){
        	dp[i][j] = dp[i - 1][j];
            track[i][j] = UP; //위에서 온 값
        }
        else{
        	dp[i][j] = dp[i][j - 1];
            track[i][j] = LEFT; //왼쪽에서 온 값
        }
    }
}

LCS의 테이블을 생각해보면, 비교하는 원소가 같을 때, 대각선의 값 + 1을 해왔다. 즉, 대각선의 값을 추적한다면 LCS를 구할 수 있게 된다.

이제 추적 테이블도 만들었으니 재귀적으로 출력하면 문자열을 모두 출력할 수 있게 된다!

추적 테이블 기반의 재귀함수는 다음과 같다.

void PrintLCS(const string& b, int x, int y)
{
	switch (track[x][y])
	{
	case UP:
		PrintLCS(b, x - 1, y);
		break;
	case LEFT:
		PrintLCS(b, x, y - 1);
		break;
	case DIAG:
		PrintLCS(b, x - 1, y - 1);
		printf("%c", b[y]);
		break;
	default:
		return;
	}
}

문자열 변수 이름을 b로 해놓은 이유는, 어차피 공통 부분 문자열이기 때문에 둘 중 하나만 출력해도 상관없고 두 번째로 입력받은 문자열임을 구분하기 위해서이다.

---

최종 코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
#define MAX_LEN	1001
#define LEFT	1
#define UP		2
#define DIAG	3
int dp[MAX_LEN][MAX_LEN] = { {0, 0} };
int track[MAX_LEN][MAX_LEN] = { {0, 0} };
void PrintLCS(const string& b, int x, int y)
{
	switch (track[x][y])
	{
	case UP:
		PrintLCS(b, x - 1, y);
		break;
	case LEFT:
		PrintLCS(b, x, y - 1);
		break;
	case DIAG:
		PrintLCS(b, x - 1, y - 1);
		printf("%c", b[y]);
		break;
	default:
		return;
	}
}
void CalcLCSAndLength(const string& x, const string& y)
{
	int xLen = x.length(), yLen = y.length();
	for (int i = 1; i < xLen; i++) {
		for (int j = 1; j < yLen; j++) {
			if (x[i] == y[j]) {
				dp[i][j] = dp[i - 1][j - 1] + 1;
				track[i][j] = DIAG;
			}
			else if (dp[i - 1][j] >= dp[i][j - 1]) {
				dp[i][j] = dp[i - 1][j];
				track[i][j] = UP;
			}
			else {
				dp[i][j] = dp[i][j - 1];
				track[i][j] = LEFT;
			}
		}
	}
	printf("%d\n", dp[xLen - 1][yLen - 1]);
	PrintLCS(y, xLen - 1, yLen - 1);
}
int main()
{
	string x, y;
	cin >> x >> y;
	
	x.insert(0, "0");
	y.insert(0, "0");
	
	CalcLCSAndLength(x, y);
	return 0;
}