[Algorithm] LCS (최장 공통 부분 수열, 최장 공통 부분 문자열)

LCS의 2가지

• Longest Common Subsequence (최장 공통 부분 수열)
• Longest Common Substring (최장 공통 부분 문자열)

 

 

Subsequence와 Substring의 차이점

Subsequence : 전체 문자열에서 꼭 연속적이지는 않은 부분 문자열
Substring : 전체 문자열에서 연속된 부분 문자열

 

<Subsequence>
str1 : 'ABECJ'
str2 : 'ABKJG'

공통 부분 수열 -> {}, {A}, {B}, {J}, {A, B}, {A, J}, {B, J}, {A,B,J} -> 최장 공통 부분 수열

<Substring >
str1 : 'ABECJ'
str2 : 'TABJG'

공통 부분 수열 -> {}, {A}, {B}, {A, B} -> 최장 공통 부분 문자열

 

---

 

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

공통 부분 수열 中 길이가 가장 긴 부분 수열

ex) 
str1 : 'ABEWHCJ'
str2 : 'AEWHABJ'
Longest Common Subsequence - 'AEWHJ'

 

- str1[i]와 str[j]가 같으면 대각선 왼쪽 위를 가리키며 LCS[i][j] = LCS[i-1][j-1] + 1을 해준다. (대각선 왼쪽 위 방향의 값 + 1)

- str1[i]와 str[j]가 다르다면, 좌측이나 위에 있는 숫자 중 큰 값을 가리키며 같은 값을 가진다. 동일한 값일 때는 위의 값을 가리킨다.  

- 제일 좌측 하단에서부터 시작해 화살표 방향으로 따라가면서 대각선 방향을 가리키는 부분의 문자를 나열하면 최장 공통 부분 수열LCS가 된다. 

 

※ LCS[0][0-7]과 LCS[0-7][0]의 행은 0으로 초기화 해야한다. (가로, 세로 첫번째 행은 0으로 초기화)

-> 아래의 조건으로 생각해보면  str1 : 'ABEWHCJ' , str2 : 'AEWHABJ'에서 첫번째 A를 만났을 때 LCS[i-1][j-1]을 참조해야하는데 만약 가로, 세로 첫번째 행을 0으로 초기화 하지 않았다면 LCS[-1][-1]를 참조해  ERROR가 날 것이다. 

 

 

 

 

 

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

두 문자열에서 공통 문자열 中 가장 긴 문자열

ex) 
str1 : 'ABEWHCJ'
str2 : 'AEWHABJ'
Longest Common Substring - 'EWH'

 

- str1[i]와 str[j]가 같으면 LCS[i][j] = LCS[i-1][j-1] + 1 저장한다. (가로, 세로 첫번째 행은 0으로 초기화)

- str1[i]와 str[j]가 다르다면 LCS[i][j] = 0을 저장하면 된다. 

- 가장 큰 값을 찾아 대각선을 따라 올라가면 최장 공통 부분 문자열 LCS가 나온다. 

 

※ LCS[0][0-7]과 LCS[0-7][0]의 행은 0으로 초기화 해야한다. (문자열의 인덱스는 1부터 시작)

설명은 최장 공통 부분 수열과 같다. 

 

• LCS 백준 문제

[백준(Baekjoon)] 9251 LCS