Longest Common Subsequence (LCS)

최장 공통 부분 문자열

LCS란?

“Longest Common Subsequence”의 약자로, 두 문자열의 공통 부분 문자열 중 그 길이가 가장 긴 것을 말한다. LCS 알고리즘이라고 하면 일반적으로 그 공통된 부분 문자열을 찾는 과정을 말한다. 부분 문자열이라고 해서 찾는 문자열이 꼭 붙어있을 필요는 없고, 문자들이 각각 떨어져있어도 된다. 문자들이 모두 붙어있는 것은 substring이라고 한다. 차이점은 아래에 있다.

• substring : 전체 문자열에서 연속적으로 나타나는 문자들로 만든 부분 문자열
  • 주어진 문자열이 “ABCDE”라면, “ABC”, “BCDE”, “E”, “CD” 등이 가능하다
  • 다만 “ACE”, “BD” 등은 substring이 될 수 없다
• subsequence : 전체 문자열에서 문자들로 만든 부분 문자열. 꼭 연속될 필요는 없다. 그러나 나타나는 문자의 순서는 바뀌어서는 안된다
  • “ACE”, “BD” 등도 subsequence가 될 수 있다
  • 다만 “CA”, “ECD” 등은 subsequence가 될 수 없다

LCS 문제는 주어지는 문자열들 중에서 가장 긴 subsequence를 찾는 것이다. 예시로 백준의 “9251 - LCS” 의 예제를 살펴보면, “ACAYKP”와 “CAPCAK“의 LCS는 “ACAK“가 된다.

---

알고리즘 해법

이 단계에서는 LCS 문제를 해결하기 위해, 문제 예시와 그 해법에 대해 설명한다.

시나리오 예시

문제는 위에서 얘기했던 대로 백준의 “9251 - LCS” 문제에서의 예제를 이용한다. 조건은 아래와 같다.

• 첫 번째 문자열 : ACAYKP
• 두 번째 문자열 : CAPCAK

DP를 이용한 방법

dp는 ‘이전의 상태를 미리 기록해두었다가 이후의 큰 문제를 풀 때 이전의 값을 활용’하는 방법이다. dp문제는 항상 “어떤 subproblem의 답을 저장할 것인지” 확정하는 것이 어려운데, 냅색에서는 아래와 같이 정의할 수 있다.

dp[i][j] : 첫번째 문자열의 i번째 문자와 두번째 문자열의 j번째 문자까지 확인했을 때, LCS 길이의 최댓값을 기록

이렇게 지정하면 문제에서 원하는 답은 dp[len1][len2]에 존재하게 될 것이다. 모든 문자를 고려한 이후의 LCS 값이 우리가 원하는 값이기 때문이다.

시나리오 예시를 통해 이해해보자. 아래와 같은 표를 채워나가는 것이 dp의 목적이다.

dp[][]	0	A	C	A	Y	K	P
0
C
A
P
C
A
K

dp배열의 값을 채우기 위한 작업을 진행해보자. index를 잘 보면 제일 앞에 $0$이 있는 것을 볼 수 있는데, index를 벗어나는 범위를 쉽게 핸들링하기 위해 미리 끼워넣는 것이라고 생각하면 편할 것 같다.

먼저 dp[0][]을 보자. $0$은 일단 모든 문자와는 매칭되지 않는다. 다만 맨 처음 $0$과는 서로 매칭되기 때문에 값을 $1$로 두어야한다고 생각할 수 있다. 하지만 우리가 임의로 지정한 칸이지, 실제로는 비어있는 칸이므로 값을 넣어주면 안된다. 첫 줄을 모두 채운 값은 아래와 같아질 것이다.

dp[][]	0	A	C	A	Y	K	P
0	0	0	0	0	0	0	0
C	0
A	0
P	0
C	0
A	0
K	0

첫번째 문자인 C를 보자. 문자열의 모든 문자에 대해 매칭되는지 확인한다.

1. C는 A와 같지 않음. 매칭되지 않음

   dp[][]	0	A	C	A	Y	K	P
   0	0	0	0	0	0	0	0
   C	0	0
   A	0
   P	0
   C	0
   A	0
   K	0

2. C는 C와 같음. 매칭됨

   • 이 때, 매칭된 문자는 첫번째 문자열의 “AC“와 두번째 문자열의 “C” 사이의 매칭을 의미한다. 이것은 “A”와 ““에서의 매칭의 최댓값에서 C라는 문자를 추가한 것이라고 이해할 수 있다.

   dp[][]	0	A	C	A	Y	K	P
   0	0	0	0	0	0	0	0
   C	0	0	1
   A	0
   P	0
   C	0
   A	0
   K	0

3. C는 A와 다름. 매칭되지 않음

   • 이 때, “ACA”와 “C”의 공통부분은 여전히 “C” 가 있으므로 그 길이가 1이다.

   dp[][]	0	A	C	A	Y	K	P
   0	0	0	0	0	0	0	0
   C	0	0	1	1
   A	0
   P	0
   C	0
   A	0
   K	0

위 방식대로 진행하여 “C”에 대해 dp배열을 채우면 아래와 같다.

dp[][]	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
P	0
C	0
A	0
K	0

다음으로는 “A”에 대하여 매칭을 진행하자. 진행하는 방법은 “C”를 매칭했던 방법 그대로 진행한다.

1. A는 A와 같음. 매칭됨

   dp[][]	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
   P	0
   C	0
   A	0
   K	0

2. A는 C와 다름. 매칭되지 않음

   • 이 때, 충돌이 발생할 수 있다. “CA”와 “AC”는 어떤 문자를 중복이라고 생각하냐에 따라 결과가 달라질 수 있기 때문이다. C가 중복이라고 생각할수도, A가 중복이라고 생각할수도 있다.
   • 선택할 수 있는 경우는 “AC“와 “C” + “A”, “AC”와 “C” + “A“이다.

   dp[][]	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
   P	0
   C	0
   A	0
   K	0

3. A는 A와 같음. 매칭됨

   • 이 때, 선택할 수 있는 경우는 아래와 같다.
     • “ACA” 와 “C” + “A“로 계산하는 경우 $dp = 1$
     • “AC” + “A” 와 “CA“로 계산하는 경우 $dp = 1$
     • “AC” + “A” 와 “C” + “A“로 계산하는 경우 $dp = 2$

   dp[][]	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
   P	0
   C	0
   A	0
   K	0

같은 방법으로 결과값을 채워나가면 최종적으로 아래와 같은 표를 얻을 수 있다.

dp[][]	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

점화식의 결론은 위에서 “A”를 매칭할 때의 상황으로 설명할 수 있을 것 같다. 이전의 상황이라고 참고할 수 있는 부분은 총 3가지가 존재한다.

• “ACA” / “C” + “A” ( 1번째 문자열, 2번째 문자열 + “A” )
• “AC” + “A” / “CA” ( 1번째 문자열 + “A”, 2번째 문자열 )
• “AC” + “A” / “C” + “A” ( 1번째 문자열 + “A”, 2번째 문자열 + “A” )

위 상황을 이용하여 점화식을 설계하면 아래와 같다. \(dp[i][j] = \begin{cases} \max(dp[i-1][j], dp[i][j-1]) & \text{일반적인 경우} \\ \max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1] + 1) & \text{각 문자열에서 추가되는 문자가 같아서} \\ & \text{매칭시킬 수 있는 경우} \end{cases}\)

결과값은 dp[len1][len2]에 저장되어있으므로 그 값을 출력하면 LCS의 길이를 얻을 수 있다. 기존에 입력받은 문자열의 앞에 $0$을 추가하였음을 꼭 잊지 말 것.

#include <stdio.h>

#define First 0
#define Second 1

#define MAX_IDX 1001
char str[2][MAX_IDX + 1];
int len[2];
int dp[MAX_IDX + 1][MAX_IDX + 1];

#define max(a, b) (((a) > (b)) ? (a) : (b))

int main() {
    scanf("%s %s", &str[First][1], &str[Second][1]);
    str[First][0] = str[Second][0] = '0';

    for (len[First] = 0; str[First][len[First]] != '\0'; ++len[First]) {
    }
    for (len[Second] = 0; str[Second][len[Second]] != '\0'; ++len[Second]) {
    }

    for (int i = 1; i <= len[First]; ++i) {
        for (int j = 1; j <= len[Second]; ++j) {
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            if (str[First][i] == str[Second][j]) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
            }
        }
    }
    printf("%d", dp[len[First] - 1][len[Second] - 1]);
    return 0;
}