두 개의 문자열 Sequence가 있을 때 얼마나 유사한지를 측정할 때 사용할 수 있는 알고리즘이다.
Substring은 연속된 부분 문자열이고, Subsequence는 연속적이지는 않은 부분 문자열이다.
따라서 LCS에서는 연속적이지는 않더라도 공통 부분 중 가장 긴 길이를 찾는 것이 목적이다.
다음 표를 채우기 위한 점화식은 다음과 같다.
점화식
- i,j 두 알파벳이 같을 경우 dp[i][j] = dp[i-1][j-1]+1
- i,j 두 알파벳이 다를 경우 dp[i][j] = max(dp[i-1][j], dp[i][j-1])
따라서 위 예시의 경우에는 GACAT와 ACCGATCG에서 최장 공통 부분 수열은 ACAT이고
표에서 알 수 있듯 최장 공통 부분 수열의 길이는 4가 된다.
비슷한 예제인 편집거리를 구할 때에는 비용을 구하는 것이므로 두 문자가 같을 때 대각선의 값을 그대로 가져왔다.
하지만 LCS는 공통 부분의 길이를 구하는 것이므로 같으면 대각선의 값에 +1을 해서 가져온다.
그리고 다를 경우 dp[i-1][j]와 dp[i][j-1]의 값 중 더 큰 걸 가져오는데
이전까지의 비교를 통해 언제나 자신까지의 최대 공통 부분 수열의 값을 가지고 있기 때문이다.
참고
그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence
Game Programmer