LCS(Longest Common Subsequence) 문제

• 문자열(sequence 또는 string)의 부문자열(subsequence 또는 substring)은 문자열에서 0개 이상의 문자를 지우고 남은 문자열로 정의한다. [ex: 'ACDAB'에서 'ADA'는 부문자열, 'CAD'는 부문자열이 아님]
• 두 문자열 과 이 입력으로 주어진다.
• 두 문자열에 공통으로 있는 부문자열 중에서 가장 긴 부문자열을 최장 공통 부문자열(LCS)이라 한다.

LCS 문제는 최장공통부문자열 을 계산하는 문제.

• 의 성질을 파악해 작은 해의 재귀식으로 표현해야 한다.
  • 가장 마지막 두 문자 과 가 같은 경우와 다른 경우로 분리해 고려한다.
  • 여기서 은 두 문자열의 LCS의 길이로 정의한다.

(1) 인 경우

(즉, )을 포함한 LCS가 반드시 존재할까? 만약 증명할 수 있다면, 을 LCS의 가장 마지막 문자로 선택하면 된다. (증명이 가능하니, 해보길~) 즉,

(2) 인 경우

서로 다르다면, 최소한 두 문자 중 하나는 LCS의 마지막 문자가 될 순 없다. 즉, 그 문자를 아예 제외하고 LCS를 구하더라도 전혀 문제가 없다. 그런데 두 문자 중 어느 문자를 제외할 수 있는지는 모르기 때문에, 두 가지 경우 중에 더 긴 공통 부문자열을 택하면 된다. 즉,

이 재귀식을 이차원 배열 C에 대해 정리하면 다음과 같다. (C[i][0] = 0이고 C[0][j] = 0)