[TIL] LCS 알고리즘

LCS 알고리즘

Longest Common Subsequence 최장 공통 부분 수열 
또는 Longest Common Substring 최장 공통 부분 문자열 

 

출처 https://velog.io/@emplam27

Longest Common Substring

두 개 이상의 문자열에서 연속적으로 나타나는 가장 긴 부분 문자열 찾기 

부분 문자열은 주어진 문자열의 연속된 부분을 의미한다

원래 문자열에서 특정 시작 위치에서부터 특정 끝 위치까지의 모든 문자를 포함한다

이는 문자들이 연속적으로 이어져 있어야 하며, 반드시 전체 문자열의 일부분이어야 한다

ex. 문자열 abcde 에서 bcd 는 부분 문자열이지만 acd 는 부분 문자열이 아니다 

Longest Common Substring 찾는 방법 

1. 문자열 A, 문자열 B 를 한 글자씩 비교해 보기

2. 두 문자가 다르다면 LCS[i][j] 에 0 표시하기

3. 두 문자가 같다면 LCS[i-1][j-1] 에서 + 1 하기

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 

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

부분 수열은 원래 수열에서 일부 요소를 선택하여 순서를 유지하면서 만들어지는 수열이다

ex. 문자열 abcde 에서 ace 는 부분 수열이지만 ca 는 부분 수열이 아니다

Longest Common Substring 찾는 방법

1. 문자열 A, 문자열 B 를 한 글자씩 비교해 보기

2. 두 문자가 다르다면 LCS[i-1][j] 와 LCS[i][j-1] 중에 큰 값을 표시하기 (왼쪽 값과 위쪽 값)

3. 두 문자가 같다면 LCS[i-1][j-1] 에서 + 1 하기 

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

'현재의 문자를 비교하는 과정' 이전의 과정이 LCS[i-1][j] 와 LCS[i][j-1]

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

 

문자열 A "ACATKP" 과 문자열 B "CAPCAK" 을 비교한 내용을 표로 정리하면 아래와 같다

	0	A	C	A	Y	K	P
0	0	0	0	0	0	0	0
C	0	0	1	1	1	1	1
A	0	1	1	2	2	2	2
P	0	1	1	2	2	2	3
C	0	1	2	2	2	2	3
A	0	1	2	3	3	3	3
K	0	1	2	3	3	4	4

 

0 인 행렬을 추가한 이유는 비교 과정에서 대각선 +1 과 왼쪽/ 위쪽 비교를 위해서 추가했고,

그렇기 때문에 for 문의 범위를 m/ n+1 까지로 설정하여 첫번째 행과 열이 0으로 초기화된 상태에서 비교가 가능하다 

X 처리한 부분이 대각선 +1 된 부분이다 

 

 

 

 

LCS 참고한 블로그