Longest Common Subsequence/Substring(LCS)

2023. 5. 10. 10:27C++/알고리즘

DP를 활용하는 알고리즘 중 하나.

 

Longest Common Subsequence는 최장 공통 부분 수열

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

 

문자열은 연속되는 순서를 의미하고 수열은 연속되지 않는 순서도 모두 포함한 의미이다.

 

ABRAC라는 문자열이 존재할때

이 문자열의 부분 수열은 0(공집합), A, AB, ABR, AR, ABRAC... 등등 여러개가 존재한다.

여기서 AR이라는 부분 수열은 Substring에는 포함되지 않지만 Subsequence에는 포함된다.

 

1. Longest Common Subsequence

먼저 연속되지 않은 최장 공통 부분 수열의 길이를 탐색하는 방법을 살펴보자.

두 문자열 ABCBD, CABCD를 비교할때

단순하게 문자열의 맨 앞에서부터 비교하는 과정을 할 수 있다.

  • A와 CCABD는 A라는 LCS를 공유한다. 따라서 LCS의 길이는 1.
  • AB와 CCABD는 AB라는 LCS를 공유한다. 따라서 LCS의 길이는 2.
  • ABC와 CCABD는 여전히 AB라는 LCS를 공유한다. 따라서 LCS의 길이는 2.
  • ABCB와 CCABD는 AB와 CB라는 LCS를 공유한다. 따라서 LCS의 길이는 2.
  • ABCBD와 CCABD는 ABD라는 CBD라는 LCS를 공유한다. 따라서 LCS의 길이는 3.

 

해당 과정에서 비교하는 문자열에서 글자 하나가 추가될때마다

추가된 글자가 조건을 충족할때 이전 LCS에 추가되는 것을 볼 수 있다.

이런 상황을 사용하여 이전 문자열의 LCS 길이를 활용하는 방법으로 DP적 접근을 생각해 볼 수 있다.

 

  0 C C A B D
0 0 0 0 0 0 0
A 0 0 0 1 1 1
B 0 0 0 1 2 2
C 0 1 1 1 2 2
B 0 1 1 1 2 2
D 0 1 1 1 2 3

다음은 Longest Common Subsequence의 DP적 접근법이다.

 

CCAB와 AB를 비교할때 비교하는 문자가 B로 동일하므로 B가 추가되기 전 LCS의 값에 1을 더한다.

->DP[i][j] = DP[i-1][j-1] + 1

 

CCAB와 ABCBD를 비교할때 비교하는 문자가 B와 D로 각각 다르므로 각각 맨 끝의 문자가 추가되기 전의 LCS값 중 큰 것을 고른다.

->DP[i][j] = max(DP[i-1][j], DP[i][j-1]

 

DP[i][j]의 값이 두 문자열의 Longest Common Subsequence의 길이가 된다.

 

2. Longest Common Substring

최장 공통 부분 문자열은 수열과 다르게 연속도 판단해야한다.

연속 여부를 판단하는 과정이 복잡하다고 생각할 수 있겠지만 오히려 수열보다 과정이 하나 줄어든다고 생각하면 된다.

 

1. 비교하는 문자가 같을때 해당 문자가 추가되기 전 LCS값에서 +1을 해주면 된다.

2. 비교하는 문자가 다를때 DP의 값을 0으로 설정한다.

(LCS는 연속되어야 하므로 다른 값이 들어오면 LCS는 이어질 수 없음)

 

2번 과정을 통해서 1번 과정이 연속성을 보장하게된다.

 

  0 C C A B D
0 0 0 0 0 0 0
A 0 0 0 1 0 0
B 0 0 0 0 2 0
C 0 1 1 0 0 0
B 0 0 0 0 1 0
D 0 0 0 0 0 1

다음은 Longest Common Substring의 DP적 접근법이다.

 

0으로 초기화된 return값을 정의하고

DP를 채워나갈 때 return과 채워진 값 중 더 큰 값으로 return을 초기화 시켜주면 된다.

DP를 전부 탐색했을때 return값이 Longest Common Substring의 길이가 된다.

'C++ > 알고리즘' 카테고리의 다른 글

벽장문의 이동(DP)  (0) 2023.05.10
공통 부분 문자열(DP)  (1) 2023.05.10
구간 나누기(DP)  (0) 2023.05.04
고층빌딩(DP)  (1) 2023.05.02
집합의 표현(Union-Find)  (0) 2023.01.02