78. Longest Common Subsequence

최장 공통 부분수열(Longest Common Subsequence, LCS)은 두 수열에 대해 정의되는 수열로, 두 수열 $a, b$가 존재하고 수열 $c$가 $a$의 부분수열이면서 $b$의 부분수열일 때 $c$를 $a$와 $b$의 공통 부분수열이라고 하고, 그런 공통 부분수열 중 가장 긴 것을 $a$와 $b$의 최장 공통 부분수열이라고 한다. 예를 들어 수열 $a$와 $b$가 다음과 같을 때 두 수열의 LCS는 $\{5, 7, 4, 6\}$이다.

$$a = \{2, {\color{red}5}, 2, {\color{red}7}, 1, {\color{red}4}, 3, {\color{red}6}\}$$

$$b = \{4, {\color{red}5}, {\color{red}7}, 6, {\color{red}4}, 2, {\color{red}6}\}$$

LIS와 마찬가지로 두 수열의 LCS도 두 개 이상 존재할 수 있다.

---

길이가 $n$인 수열 $a$와 길이가 $m$인 수열 $b$가 주어졌을 때 $n$과 $m$이 크지 않은 경우 동적 계획법을 이용하면 두 수열의 LCS의 길이와 LCS를 구할 수 있다. $s_{i, j}$를 $a$의 $i$번째 원소와 $b$의 $j$번째 원소까지 고려했을 때의 LCS의 길이라고 하면 다음과 같은 관계식을 세울 수 있게 된다.

$$s_{i, j} = \begin{cases} 0, & i = 0 \text{ or } j = 0 \\ s_{i-1, j-1}+1, & a_i = b_j \\ \max(s_{i-1, j}, s_{i, j-1}), & a_i \ne b_j \end{cases} (0 \le i \le n, 0 \le j \le m)$$$s_{i, j}$를 전부 구했다면 $s_{n, m}$에 $a$의 $b$의 LCS의 길이가 저장된다. 구현도 다음과 같이 그대로 하면 되기 때문에 어렵지 않다. 시간복잡도는 $\Theta(nm)$이고 단순화하면 $\Theta(n^2)$이다.

int lcs(int n, int m)
{
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            if(a[i] == b[j])s[i][j] = s[i - 1][j - 1] + 1;
            else s[i][j] = max(s[i - 1][j], s[i][j - 1]);
        }
    }
    return s[n][m];
}

만약 LCS 자체를 구해야 할 경우 각각의 $s_{i, j}$가 어떤 기준에 따라서 정해졌는지를 체크한 다음 $s_{n, m}$에서 역추적을 하면 된다. 역추적 과정에서 $a_i = b_j$를 만족할 때마다 그 값을 스택에 넣고, 마지막에 스택에서 차례로 꺼내면 $a$와 $b$의 LCS가 된다. 다음과 같이 구현할 수 있다.

stack<int>S;
void lcs(int n, int m)
{
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            if(a[i] == b[j])
            {
                s[i][j] = s[i - 1][j - 1] + 1;
                d[i][j] = 1;
            }
            else if(s[i - 1][j] > s[i][j - 1])
            {
                s[i][j] = s[i - 1][j];
                d[i][j] = 2;
            }
            else
            {
                s[i][j] = s[i][j - 1];
                d[i][j] = 3;
            }
        }
    }
    for(int i = n, j = m; i || j;)
    {
        if(d[i][j] == 1)
        {
            S.push(a[i]);
            i--;
            j--;
        }
        else if(d[i][j] == 2)i--;
        else j--;
    }
}

함수의 실행이 끝났을 때 $s[n][m]$이 LCS의 길이가 되고, 스택에 저장된 원소들을 차례로 뽑으면 LCS가 된다.

 

대부분의 LCS 문제는 이 방법으로 해결할 수 있고, 그렇지 않은 어려운 문제들도 존재하지만 이 블로그에는 그런 문제들을 풀 수 있는 방법까지는 설명하지 않았다.

 

[연습문제]

 

BOJ 9251. LCS (Gold V)

위에 나온 방법대로 LCS의 길이를 구하면 된다.

 

BOJ 9252. LCS 2 (Gold V)

LCS의 길이를 구하고 역추적을 해서 LCS를 구한다.

 

BOJ 1958. LCS 3 (Gold III)

문자열이 $3$개인데, 풀이는 문자열이 $2$개인 경우와 다르지 않아서 그냥 $\Theta(n^3)$ DP로 LCS의 길이를 구하면 된다.

 

CF 1446B. Catching Cheaters (1800)

일반적인 LCS와 비슷한 방식으로 DP 테이블을 채우면 된다. 앞쪽부터 채우는 테이블과 뒤쪽부터 채우는 테이블이 있는데, 문자열의 인덱스를 1-based로 두면 다음과 같은 식을 세울 수 있다.

$$a_{i, j} = \begin{cases} 0 & (i = 0 \text{ or } j = 0) \\ \max(a_{i-1, j-1}+2, a_{i-1, j}, a_{i, j-1}) & (A_i = B_j) \\ \max(a_{i-1, j}, a_{i, j-1}, 1)-1 & (A_i \ne B_j) \end{cases}$$

$$b_{i, j} = \begin{cases} 0 & (i > n \text{ or } j > m) \\ \max(b_{i+1, j+1}+2, b_{i+1, j}, b_{i, j+1}) & (A_i = B_j) \\ \max(b_{i+1, j}, b_{i, j+1}, 1)-1 & (A_i \ne B_j) \end{cases}$$

모든 $a_{i, j}$와 $b_{i, j}$ 중 최댓값이 답이다.