[Algorithm] 최장 공통 부분 수열 (LCS, Longest Common Subsequence)

단어가 일치하는지 확인하는 개념은, 연속 부분 문자열인 Substring이며
연속되지 않는 부분 문자열을 Subsequence라고 한다.

 
기본 구현 과정
1) 첫번째 행과 열을 0으로 맞춘다
2) 기준이 되는 열에 행의 문자를 넣고, 문자가 일치하면 행렬값에 1을 더한다
3) 행 테이블의 값은 이전 테이블 값의 누적된 값이 기록되며, 새롭게 매칭되는 문자가 나왔을 때 다음을 생각한다
 
☆ 3-1) 현재 서로다른 문자열인 경우, 현재 테이블에 들어갈 수는 (왼쪽or위쪽중 큰 값)을 따라간다
☆ 3-2) 현재 서로같은 문자열인 경우, 현재 테이블에 들어갈 수는 (왼쪽위 대각선 값 + 1)이다
 
4) LCS의 최종 길이는 행렬의 마지막 부분인 (r-1,c-1)의 값이다

void LCS() {
	string R, C;
	int LCSArray[1001][1001];
	for (int r = 0; r < R.length(); r++) {
		for (int c = 0; c < C.length(); c++) {
			if (r == 0 || c == 0) {
				LCSArray[r][c] = 0;
				continue;
			}

			// 3-2
			if (R[r] == C[c]) {
				LCSArray[r][c] = LCSArray[r - 1][c - 1] + 1;
			}
            		// 3-1
			else {
				LCSArray[r][c] = max(LCSArray[r - 1][c], LCSArray[r][c - 1]);
			}
		}
	}
	printf("%d", LCSArray[R.length() - 1][C.length() - 1]);
}

 완성된 LCS 단어 찾기
1) 기본 구현에서 만들어진 행렬 테이블의 (r-1,c-1)부터 시작한다
2) 1)에서 시작한 값의 크기를 지니는 반환배열을 만든다
 
☆ 2-1) (현재 값)에서 (왼쪽or위쪽의 같은 값)을 찾아 좌표를 옮긴다
☆ 2-2) 같은 값이 없다면, (대각선 방향의 값)이 (현재값 - 1)인지 확인하고 같은값이면 움직인다
☆ 3) 2-2)을 이용해 움직였다면, 해당 문자를 반환배열의 2-2)의 현재값 인덱스에 저장한다
 
4) 값이 0이 나올때 까지 2),3),4)를 반복한다

void LCS_World() {
	stack<char>s;
	string R, C;
	int LCSArray[1001][1001];
	int r = R.length() - 1, c = C.length() - 1;
	while (LCSArray[r][c] != 0) {
		if (LCSArray[r][c] == LCSArray[r][c - 1]) c--;
		else if (LCSArray[r][c] == LCSArray[r - 1][c]) r--;
		else if (LCSArray[r][c] - 1 == LCSArray[r - 1][c - 1]) {
			s.push(C[c]); r--; c--;
		}
	}
	while (!s.empty()) {
		printf("%c", s.top()); s.pop();
	}
}