最长公共子序列

介绍

最长公共子序列（Longest Common Subsequence, LCS）问题 就是在一组序列（通常是 2 个）中找出所有序列的最长公共子序列，它与 最长公共字串（Longest Common Substring） 问题不同，它不要求子序列在原来的序列中是位置连续的。

两个序列的最长公共子序列

用 $S_n$ 表示 $S$ 的前 $n$ 个字符，例如，$S=(\text{AGCA})$ 的前缀为：

$$ \begin{aligned} S_0&=()\\ S_1&=(\text{A})\\ S_2&=(\text{AG})\\ S_3&=(\text{AGC})\\ S_4&=(\text{AGCA}) \end{aligned} $$

用 $\texttt{LCS}(X,Y)$ 表示计算 $X$ 和 $Y$ 的最长公共子序列的函数，该函数具有两个性质。

$$ \begin{aligned} \texttt{LCS}(X\verb|^|a,Y\verb|^|a)&=\texttt{LCS}(X,Y)\verb|^|a\\ \texttt{LCS}(X\verb|^|a,Y\verb|^|b)&=\max(\texttt{LCS}(X\verb|^|a,Y),\texttt{LCS}(X,Y\verb|^|b))\\ \end{aligned} $$

其中符号 $\verb|^|$ 表示字符串连接，$a,b$ 表示某个字符且 $a\neq b$。

所以 $\texttt{LCS}$ 函数的递推定义如下，$X=(x_1x_2\cdots x_m),Y=(y_1y_2\cdots y_n)$，$\texttt{LCS}(X_i,Y_i)$ 表示前缀 $X_i$ 和 $Y_j$ 的最长公共子序列，则有：

$$ \texttt{LCS}(X_i,Y_i)=\begin{cases} \phi&(i=0 \text{ or } j=0)\\ \texttt{LCS}(X_{i-1},Y_{j-1})\verb|^|x_i&(i,j\gt0\text{ and }x_i=y_j)\\ \max(\texttt{LCS}(X_i,Y_{j-1}),\texttt{LCS}(X_{i-1},Y_j))&(i,j\gt0 \text{ and }x_i\neq y_j) \end{cases} $$

类似问题

最短公共超序列（Shortest Common Supersequence, SCS）：$|\texttt{SCS}(X,Y)|=n+m-|\texttt{LCS}(X,Y)|$。

编辑距离（Edit Distance，即把一个字符串变为另一个字符串需要的最小操作数量）。当只允许插入或者删除字符，或者替换字符的代价是插入或删除的两倍时：$d'(X,Y)=n+m-2\cdot|\texttt{LCS}(X,Y)|$。

动态规划代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


vector<vector<int>> LCS(string X, string Y) {
    // 计算 LCS 的长度
    int n = X.size(), m = Y.size();
    vector<vector<int>> C(n + 1, vector<int>(m + 1));

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (X[i - 1] == Y[j - 1]) {
                C[i][j] = 1 + C[i - 1][j - 1];
            } else {
                C[i][j] = max(C[i - 1][j], C[i][j - 1]);
            }
        }
    }

    return C;
}

string LCS(vector<vector<int>> &C, string X, string Y, int i, int j) {
    // 输出某个 LCS
    // C: 动态规划矩阵; i: 初始值为 X.size(); j: 初始值为 Y.size()
    if (i == 0 || j == 0) {
        return "";
    }

    if (X[i - 1] == Y[j - 1]) {
        return LCS(C, X, Y, i - 1, j - 1) + X[i - 1];
    }

    if (C[i - 1][j] > C[i][j - 1]) {
        return LCS(C, X, Y, i - 1, j);
    }

    return LCS(C, X, Y, i, j - 1);
}

两个序列的最长公共子串

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


int LCSs(string X, string Y) {
    int n = X.size(), m = Y.size();
    vector<vector<int>> C(n + 1, vector<int>(m + 1));
    int c = 0;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (X[i - 1] == Y[j - 1]) {
                C[i][j] = 1 + C[i - 1][j - 1];
            } else {
                C[i][j] = 0;
            }

            c = max(c, C[i][j]);
        }
    }

    return c;
}

例题

参考

https://en.wikipedia.org/wiki/Longest_common_subsequence_problem