최장 공통 부분수열_LongestCommonSubsequence

최장 공통 부분수열(Longest Common Subsequence)

최장 공통 문자열Longest common substring

• 점화식

if i == 0 or j == 0:
	LCS[i][j] = 0
elif string_A[i] == string_B[j]
	LCS[i][j] = LCS[i-1][j-1] + 1
else:
	LCS[i][j] = 0

동작

1. 문자열 A, 문자열 B의 한 글자씩 비교한다.
2. 두 문자가 다르다면 LCS[i][j]에 0을 표시
3. 두 문자가 같다면 LCS[i-1][j-1] 값을 찾아 + 1
4. 위 과정을 반복한다.

• 이 과정이 성립하는 이유는 공통 문자열은 연속 되어야 하기 때문에 현재 두 문자가 같을 때 두 문자의 앞 글자 까지가 공통 문자열이라면 계속 공통 문자열이 이어질 것이고, 아니라면 본인부터 다시 공통 문자열을 만들어가게 될 것이다.

최장 공통 부분수열

• 점화식

if i == 0 or j == 0:
	LCS[i][j] = 0
elif string_A[i] == string_B[j]
	LCS[i][j] = LCS[i-1][j-1] + 1
else:
	LCS[i][j] max(LCS[i-1][j],LCS[i][j-1])

동작

1. 문자열 A, 문자열 B의 한 글자씩 비교한다
2. 두 문자가 다르다면 LCS[i-1][j] 와 LCS[i][j-1] 중 큰 값을 표시한다.
3. 두 문자가 같다면 LCS[i-1][j-1] 값을 찾아 +1 한다
4. 위 과정을 반복한다.

• 부분 수열은 연속된 값이 아니다. 현재의 문자를 비교하는 과정 이전의 최대 공통 부분수열은 계속해서 유지된다.