백준 [9251] LCS

여기에 설명이 진짜 잘 돼있다.

ko.wikipedia.org/wiki/%EC%B5%9C%EC%9E%A5_%EA%B3%B5%ED%86%B5_%EB%B6%80%EB%B6%84_%EC%88%98%EC%97%B4

최장 공통 부분 수열 - 위키백과, 우리 모두의 백과사전

 

문자열 A, B가 있을 때LCS함수는 다음과 같이 정의한다.

i = 0 또는 j = 0 일 때 -> 0

A[i] == B[i] 일 때 -> LCS[i][j] = LCS[i-1][j-1] + 1

A[i] != B[i] 일 때 -> LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1])

 

그림으로 보자.

초기 캐시 테이블이다. 캐시 이름은 LCS로 한다.

초기 캐시 테이블

i = 1, j= 1일 때. A[i] = C이고, B[i] = A이므로, A[i] != B[i]이다.

그러므로 캐시는 왼쪽과 위쪽에서 큰 값을 찾는다.

하지만, 둘 다 0이므로, LCS[i][j] = 0 이 저장된다.

왼쪽에과 위쪽에서 큰 값을 찾는 이유는,

A를 기준으로 문자열을 이어나가는게 이득인지(왼쪽),

B를 기준으로 문자열을 이어가는게 이득인지 판별하기 위해서다(위쪽).

A[i] != B[i]

문자열 A의 일부인 C를 가지고 B문자열과 만들 수 있는 LCS를 구하는 과정이다.

B[2] 의 값이 C이므로, LCS는 C가 추가되기 전 최장 LCS길이 + 1을 해준다.

LCS[i][j] = LCS[i-1][j-1] + 1

이 1은 만들 수 있는 문자열의 최대 길이가 1이라는 뜻이다.

A[i] == B[i]

이후 문자열 B 중에서, C와 동일한 값을 가지는 문자가 없기 때문에, 이전 값들을 계속 가져온다.

이제 문자열 A의 일부인 CA로 만들 수 있는 경우를 보자.

B[1] == A[2] 이므로, LCS[1][0] +1 을 LCS[2][1]에 넣어준다.

여기서, LCS[2][2] 부분에선 만들 수 있는 공통 문자열 길이가 A가 되고 C도 될 수 있다.

다만, 우리는 길이를 구하는 거니 1을 저장한다.

다음 i=2, j= 3일 때, 만들 수 있는 최대 공통 문자열이 CA가 되므로,

LCS[2][3]은 2가 된다.

최종 캐시 테이블은 다음과 같다.

최종 캐시 테이블

 

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	string A, B;
	int LCS[1024][1024] = { 0, };
	int i, j, temp = 0;
	int Alen, Blen;

	cin >> A >> B;
	A = '0' + A;
	B = '0' + B;
	Alen = A.length();
	Blen = B.length();
	if (Blen > Alen)
	{
		swap(A, B);
		swap(Alen, Blen);
	}

	// 마지막 원소들이 같은지 비교
	i = Alen - 1;
	j = Blen - 1;
	while (i & j)
	{
		if (A[i] != B[j])
			break;
		else
		{
			Alen--;
			Blen--;
			temp++;
		}
		i--;
		j--;
	}
	if (Alen == 0 || Blen == 0)
		cout << temp;
	else
	{
		for (i = 1; i < Alen; i++)
		{
			for (j = 1; j < Blen; j++)
			{
				if (A[i] == B[j])
					LCS[i][j] = LCS[i - 1][j - 1] + 1;
				else
					LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1]);
			}
		}
		cout << LCS[i - 1][j - 1] + temp;
	}
	return 0;
}