DP/최단거리 역추적. [9252]

[1. 문제 설명]

두개의 문자열이 주어졌을 때, 

두 문자열에서 공통되는 가장 긴 문자열을 출력한다.

---

[2. 풀이 접근]

LCS 의 길이를 찾는 방법은 아래를 참조한다.

=> 링크

 

 

LCS 길이를 찾고 난 다음 cache table 은 아래와 같은 초기화 되어있다.

	C	A	P	C	A	K
A	4	4	-1	-1	-1	-1
C	3	-1	3	3	-1	-1
A	-1	2	2	2	2	-1
Y	-1	-1	1	1	1	1
K	-1	-1	1	1	1	1
P	-1	-1	1	0	0	0

최초 cache[0][0] 이 어떻게 초기화 되었는지 추적해보면

str1[0] != str2[0] 이므로,

LCS(1, 0) 과 LCS(0, 1) 중 최대 값에 의해 초기화 되어있음을 알 수 있다.

 

그래서 cache[0][1] 로 이동해야 한다.

여기서 str1[0] == str1[1] 이며,

cache[0][1] = 1 + LCS(1, 2) 에 의해 초기화 되었음을 역시 알 수 있다.

 

따라서 이번에는 대각선 방향으로 움직여야 한다. 

 

정리하면, 현재 y, x 에 대해서

두 문자가 같다면, 대각선 방향으로 움직일 수 있고,

두 문자가 다르다면, 현재 캐시 값이 어떤 방향으로 부터 초기화 되어있는지 확인하고

초기화를 유도한 방향으로 움직이는 것이다.

 

LCS 의 길이를 찾는데는 O(N²) 의 시간이 걸린다면

아래 코드에서 getLCS() 함수의 시간복잡도는 O(N) 이다.

---

[3. 코드]