LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence

Longest Common Subsequence? Substring?

LCS는 주로 최장 공통 부분수열(Longest Common Subsequence) 또는, 최장 공통 문자열(Longest Common Substring)을 뜻한다.

해당 예시에서 최장 공통 부분수열(Longest Common Subsequence)은 BCDF, BCDE가 될 수 있다. 부분수열이기 때문에 문자 사이를 건너뛰어 공통되면서 가장 긴 부분 문자열을 찾으면 된다. 최장 공통 문자열(Longest Common Substring)은 BCD입니다. 부분문자열이 아니기 때문에 한번에 이어져있는 문자열만 가능하다.

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

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

LCS라는 2차원 배열을 이용하여 두 문자열을 행, 열에 매칭한다. 편의상 i, j가 0일때는 모두 0을 넣어줘 마진값을 설정한다. 이후 i, j가 1이상일 때부터 검사를 시작한다. 

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

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

구현과정

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

위와 마찬가지로 LCS라는 2차원 배열에 매칭하고 마진값을 설정한 후 검사한다.

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

최장 공통 문자열을 구하는 과정과 다른부분은 비교하는 두 문자가 다를 때 이다. 비교하는 두 문자가 같을 때는 같은 과정을 보여준다. 

1. LCS[i - 1][j]와 LCS[i][j - 1]는 어떤 의미인가?

부분수열은 연속된 값이 아니다. 때문에 현재의 문자를 비교하는 과정 이전의 최대 공통 부분수열은 계속해서 유지된다. '현재의 문자를 비교하는 과정' 이전의 과정이 바로 LCS[i - 1][j]와 LCS[i][j - 1]가 된다.

문자열 AB와 GBC를 비교(위 그림의 초록색 부분)하는 과정을 예로 들어보겠다. AB와 GBC의 최대 공통 부분수열이 B라는 것을 알기 위해서는 문자열 A와 GBC를 비교하는 과정, 문자열 AB와 GB를 비교하는 과정이 필요하다. 문자열 AB와 GB의 비교 과정에서 최대 공통 부분수열이 B임을 확인했기 때문에 문자열 AB와 GBC의 최대 공통 부분수열 역시 B가 되는 것이다.

2. 왜 문자가 같으면 LCS[i][j] = LCS[i - 1][j - 1] + 1인가?

최대 공통 문자열을 구할 때 비교하는 문자가 같으면 LCS[i][j] = LCS[i - 1][j - 1] + 1의 과정을 거쳤다. 여기도 동일하다

문자열 ABC와 GBC를 비교(위 그림의 초록색 부분)하는 과정을 예로 들어보겠다. LCS 배열은 LCS[i - 1][j]와 LCS[i][j - 1]의 비교를 통해 언제나 본인까지의 최대 공통 부분수열 값을 가지고 있다. 문자열 AB와 GB를 비교할때와 문자열 ABC와 GBC를 비교할 때 달라진 점은 두 문자열 모두에 C가 추가된 점이다. 때문에 기존의 최대 공통 부분수열인 B에 C를 더한 BC가 최대 공통 부분수열이 되는 것이다.

구현과정

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

이제 만든 LCS 배열을 이용해 최장 공통 부분수열의 값을 찾아보겠다. 경우에 따라 여러가지 답이 나올 수 있기 때문에 아래 예시는 한가지 경우만을 보겠다.

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

구현과정

개인 소스코드 참고

 

출처 : [알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence (velog.io)