Algorithm. LCS(Subsequence)

소개

두 문자열이 있을 때, 가장 긴 공통 부분 문자열을 찾아내는 알고리즘, 부분 문자열이란 원소들이 원래 순서를 유지하면서 일부 원소를 생략할 수 있는 형태를 말함

예시:

문자열 A: A**B**CB**DAB**
문자열 B: **BD**C**AB**B

A와 B의 LCS는 BDAB라고 할 수 있다.

아이디어

2차원 배열을 통해 중간 결과를 메모이제이션 한다. 이 배열은 두 문자열의 길이에 따라 결정된다.

알고리즘

1. 편의상 첫 번째 열과 행은 0으로 초기화 한다. 빈 문자열과 비교했을 때의 경우를 처리할 수 있다.

1. 두 번째 문자열의 문자를 차례대로 가져와 비교한다.

• 테이블의 각 원소는 그 시점의 substring간의 LCS를 의미한다. 즉 위 표에서 1인 원소는 substring “AB”와 “B”의 LCS의 길이가 1임을 의미한다.

1. 앞선 결과를 기반으로 LCS의 크기를 계산한다.

• B와 C는 같지 않더라도, “ABC”와 “B”를 비교하는 것과 같으므로, 이전에 “AB”와 “B”를 비교한 값인 1이 유지된다.

1. 만약 두 문자가 다른 경우

• B와 D는 다르지만, “AB”와 “BD”의 LCS의 길이는 1이다. 3번의 경우와 합쳐서 두 원소가 다르지 않을 때, DP 테이블을 채우는 점화식을 세울 수 있다.
• dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

1. 두 문자가 같은 경우

• 두 문자가 같은 경우, 즉 위 표의 상황에서는 “ABCBD”와 “BD”의 LCS의 크기를 구하는 경우가 된다. 이 경우는 “ABCB”와 “B”의 LCS의 크기에서 원소 “D”가 더해진 것과 같으므로, 대각선 위에 있는 값에서 1을 더한 값이 된다.
• dp[i][j] = dp[i - 1][j - 1] + 1

동작 원리

• DP 테이블을 채우면서 두 문자가 다른 경우
  • 이전에 계산한 결과를 그대로 유지한다.
• 두 문자가 같은 경우
  • 그 문자가 없는 경우의 LCS의 크기에서 1을 더한다.
• 점화식

if (A[i - 1] == B[j - 1]) {
    dp[i][j] = dp[i - 1][j - 1] + 1
} else {
    dp[i][j] = (dp[i - 1][j] > dp[i][j - 1]) ? dp[i - 1][j] : dp[i][j - 1];
}

기타

길이와 실제 문자열

DP 테이블의 마지막 값인 dp[m][n]은 LCS의 길이만 나타낸다.

실제 LCS 문자열이 필요하다면 DP 테이블의 마지막 위치부터 역산해야 한다. 두 문자가 같다면 해당 문자를 결과에 추가하고 대각선 위로 이동하며, 다르다면 위쪽과 왼쪽 중 더 큰 값을 가진 방향으로 이동한다.

역산 과정에서는 문자열의 뒤쪽 문자부터 찾게 되므로, 결과를 마지막에 뒤집어야 한다.

실제 LCS 문자열 구하기

DP 테이블의 마지막 값인 dp[m][n]은 LCS의 길이만 나타낸다. 따라서 실제 LCS 문자열을 구하려면, DP 테이블에서 역산해야 한다.

1. 처음에 dp[m][n]에서 시작한다.

1. A의 i번째 문자와 B의 j번째 문자가 같다면 LCS에 포함되는 문자이므로, i와 j를 각각 감소시킨다.
2. 다르다면 dp[i - 1][j] 와 dp[i][j - 1] 중에서 더 큰 쪽으로 이동한다.
3. i 또는 j가 0에 도달하면 역추적을 종료한다. 같은 문자를 만날 때마다 기록한 문자를 뒤집으면 실제 LCS 문자열이 된다.

시간/공간 복잡도

문자열 A의 길이를 m, 문자열 B의 길이를 n이라고 하면 다음과 같다.

• 시간 복잡도: O(mn)
• 공간 복잡도: O(mn)