Longest Common Subsequence

💡 LCS는 주로 최장 공통 부분 수열을 말한다. 최장 공통 문자열을 말하기도 한다.

 

부분 수열과 부분 문자열의 차이점은 위와 같다.

 

최장 공통 문자열 (Longest Common Substring)

for i in range(len(string_A)) : 
	for j in range(len(string_B)):
		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

부분 수열 보다 조금 더 쉽고 최장 공통 부분 수열을 구하는데 사용됨

우선 LCS라는 2차원 배열을 이용해서 두 문자열을 행과 열에 매칭

과정

1. 문자열 A와 문자열 B의 한 글자 끼리 비교해본다
2. 두 문자가 다르다면 LCS[i][j]에 0을 표시
3. 두 문자가 같다면 LCS[i][j] = LCS[i-1][j-1] +1
4. 위 과정 반복

최댓값을 찾으면 탐색 종료

최댓값은 LCS 의 max 값!

최장 공통 부분수열 (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])

과정

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

부분 수열은 연속된 값이 아니기 때문에 현재의 문자를 비교하는 과정

이전의 공통된 부분 수열은 계속 유지 된다.

이전의 과정이 바로 LCS[i-1][j]와 LCS[i][j-1]

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

• 이제 위의 과정을 통해 길이를 알았음
• 만들어둔 LCS 배열을 통해 값을 찾아볼 수 있다
• 경우에 따라 여러가지 답이 나올 수 있다

과정

1. LCS 배열의 가장 마지막 값에서 시작. 결과 값을 저장할 result 배열 준비
2. LCS[i-1][j]와 LCS[i][j-1] 중 현재 값과 같은 값을 찾음
   1. 만약 같은 값이 있다면 해당 값으로 이동
   2. 같은 값이 없다면 result 배열에 해당 문자를 넣고 LCS[i-1][j-1]로 이동
3. 2번 과정 반복하다가 0으로 이동하게 되면 종료 …..! 배열의 역순이 LCS !