[TIL] LCS 알고리즘

 

LCS 알고리즘

최장 공통 부분문자열 (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

 

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

두 개 이상의 수열에서 공통으로 나타나는 가장 긴 부분수열을 찾는 문제다.

 

점화식 

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])

 

참고 자료 

[블로그] https://velog.io/@emplam27/알고리즘-그림으로-알아보는-LCS-알고리즘-Longest-Common-Substring와-Longest-Common-Subsequence