跳转至

最长公共子序列#
发布于2021-02-23
上次编辑2021-04-20

Introduction

最长公共子序列（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;
}

例题#

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

返回顶部

在手机上阅读