LCS(Longest Common Substring and Subsequence)

헷갈리는 용어들을 간단하게 정리하면 다음과 같다.

LCS(Longest Common Substring, 최장 공통 부분문자열)
ABCDE, ZBCDZE의 최장 공통 부분문자열은 BCD(연속성이 요구됨)

LCS(Longest Common Subsequence, 최장 공통 부분수열)
ABCDE, ZBCDZE의 최장 공통 부분수열은 BCDE(연속성이 요구되지 않음)

LIS(Longest Increasing Subsequence, 최장 증가 부분수열)
5 2 4 3 7 8 1 9의 최장 증가 부분수열은 2 3 7 8 9(연속성이 요구되지 않음)

 

다음을 예시로 해서 Longest Common Substring, Longest Common Subsequence의 길이를 구해보자.

 

s1 = "POCKETNIZED"

s2 = "TOKENIZER"

 

1. 최장 공통 부분문자열

먼저 최장 공통 부분문자열의 길이를 구해보자.

 

나이브하게 생각해보면, 다음과 같은 풀이를 떠올릴 수 있다.

① s1은 P부터 탐색

①-1 s2는 T부터 탐색해서 일치하지 않는 문자를 만나면 종료 (길이: 0),

①-2 s2는 O부터 탐색해서 일치하지 않는 문자를 만나면 종료 (길이: 0),

①-3 s2는 K부터 탐색해서 일치하지 않는 문자를 만나면 종료 (길이: 0),

...

 

② s1은 O부터 시작

②-1 s2는 T부터 탐색해서 일치하지 않는 문자를 만나면 종료 (길이: 0),

②-2 s2는 O부터 탐색해서 일치하지 않는 문자를 만나면 종료 (길이: 1),

②-3 s2는 K부터 탐색해서 일치하지 않는 문자를 만나면 종료 (길이: 0),

...

 

물론 위 알고리즘의 시간복잡도는 O(n * m^2)로서 비효율적이다.

이는 다음과 같이 DP를 통해 O(n*m)으로 개선할 수 있다.

 

 

D[i][j] = s1의 i번째 문자, s2의 j번째 문자까지만 살펴보았을 때, 최장 공통 부분문자열의 길이

 

예를 들어, D[4][3]은 s1의 4번째 문자, s2의 3번째 문자까지만 살펴보았을 때 Longest Common Substring의 길이를 말한다. 다시 말해, s1에 대해서 "POCK", s2에 대해서 "TOK"에 대해서 LCS는 "K"이므로 d[2][3] = 1이다.

이를 위해 D[i][0]과 D[0][i]를 먼저 0으로 채워두고, 다음의 식을 따른다.

새로운 문자를 추가하려고 봤더니, 서로 다르다면? 이 때에는 더이상 공통 부분문자열이 아닌 것이다. 따라서 길이는 0이 될 것이다. 서로 같다면? 이전 공통 부분문자열 길이에 1을 더해준다.

 

2. 최장 공통 부분수열

위 내용을 잘 이해했다면 굉장히 쉽다.

 

 

먼저 D[5][4] = 3인 것은, "POCKE"과 "TOKE"의 최장 공통 부분수열이 "O,K,E"인 것을 의미한다. 여기서 다음 문자를 볼 때 substring과 subsequence의 차이가 나타난다. s1[6] = 'T', s2[5] = 'N'이라 두 문자가 다르므로 substring은 0의 길이는 0이 될 것이다. 하지만 subsequence의 경우 연속성을 요구하지 않기 때문에 저장해둔 길이는 유지해줄 필요가 있다.

이를 위해서는 위 식을 이용하되, s1[i] != s2[j]가 이해되지 않는 경우를 위해 부연설명한다.

D[4][4]의 경우 "POCK"과 "TOKE"에 대한 최장 공통 부분수열의 길이이다. 이는 "POC"과 "TOK"를 비교한 D[3][3]의 상태에서 다음 문자를 본 것인데, 'K'와 'E'가 일치하지 않는다. 이 때에는 DP[3][3]의 값을 그대로 가져오면 안 된다. "POCK", "TOK"는 "O,K"를, "POC", "TOKE"는 "O"로서 서로 다른 길이를 보여주는데, 전자의 경우와 같이 한 글자만 추가되어도 길이가 증가하는 경우가 있기에 DP[3][3]이 아니라, DP[3][4]와 DP[4][3], 즉 여기서는 DP[4][3]의 값을 복사해야 하는 것이다.