最长公共子序列

问题描述

子序列：将当前序列去掉零个或多个元素所得序列。

公共子序列：同时满足是两个序列的子序列的序列。

最长公共子序列问题：求解两个序列的公共子序列，使得它尽可能长。

形式化定义

输入：

• 序列 $X=⟨x_1,x_2,\cdots ,x_n⟩$
• 序列 $Y=⟨y_1,y_2,\cdots ,y_m⟩$

输出：

• 公共子序列 $Z=⟨z_1,z_2,\cdots ,z_l⟩$

优化目标：

$$\begin{array}{r}max\left|Z\right|\end{array}$$

约束条件：

$$\begin{array}{r}\mathbf{s}\mathbf{.}\mathbf{t}\mathbf{.}⟨z_1,z_2,\cdots ,z_l⟩=⟨x_{i_1},x_{i_2},\cdots ,x_{i_l}⟩=⟨y_{j_1},y_{j_2},\cdots ,y_{j_l}⟩\\ (1\le i_1<i_2,\cdots ,i_l\le n;1\le j_1<j_2,\cdots ,j_l\le m)\end{array}$$

问题分析

令 $C[i,j]$ 表示 $X[1:i]$ 和 $Y[1:j]$ 的最长公共子序列长度，那么原始问题就是求解 $C[n,m]$。

下面我们来考察末尾字符，分为如下两大类情况：

情况一

如果 $x_i\ne y_j$，那么需要考察 $C[i,j-1]$ 和 $C[i-1,j]$ 两个子问题。并且当前问题的解是这两个子问题解的最大值，即如下的状态转移方程：

$$\begin{array}{r}C[i,j]=max\{C[i-1,j],C[i,j-1]\}\end{array}$$

情况二

如果 $x_i=y_j$，那么既可以匹配这最后一对字符，也可以不匹配。这样一来，需要考察 $C[i-1,j-1]$、$C[i-1,j]$ 和 $C[i,j-1]$ 三个子问题。

问题：三个子问题是否都需要求解？

分析：

• $C[i-1,j]$ 比 $C[i-1,j-1]$ 至多大 1，即 $C[i-1,j]-C[i-1,j-1]⩽1$。
• $C[i,j-1]$ 比 $C[i-1,j-1]$ 至多大 1，即 $C[i,j-1]-C[i-1,j-1]⩽1$。

因此

$$\begin{array}{r}C[i-1,j-1]+1⩾max\{C[i-1,j],C[i,j-1]\}\end{array}$$

故只需要考虑子问题 $C[i-1,j-1]$ 即可。于是状态转移方程为

$$\begin{array}{r}C[i,j]=C[i-1,j-1]+1\end{array}$$

小结

综上所述，状态转移方程为

$$\begin{array}{r}C[i,j]=\{\begin{array}{cc}max\{C[i-1,j],C[i,j-1]\}& (x_i=y_j)\\ C[i-1,j-1]+1& (x_i\ne y_j)\end{array}\end{array}$$

算法代码

string longestCommonSubsequence(const string &x, const string &y) {
    enum Drct {
        LU, // 向左上方回溯
        U,  // 向上方回溯
        L   // 向左边回溯
    };
    auto lengthX = x.size(), lengthY = y.size();
    // C[i,j] 表示 x[1..i] 和 y[1..j] 的最长公共子序列长度
    vector<vector<int>> C(lengthX + 1, vector<int>(lengthY + 1, 0));
    // rec[i,j] 是追踪数组，记录子问题来源
    vector<vector<Drct>> rec(lengthX + 1, vector<Drct>(lengthY + 1));

    for (int i = 1; i <= lengthX; ++i) {
        for (int j = 1; j <= lengthY; ++j) {
            if (x[i - 1] == y[j - 1]) {
                C[i][j] = C[i - 1][j - 1] + 1;
                rec[i][j] = LU;
            } else {
                C[i][j] = C[i - 1][j] > C[i][j - 1] ? C[i - 1][j] : C[i][j - 1];
                rec[i][j] = C[i - 1][j] > C[i][j - 1] ? U : L;
            }
        }
    }

    int maxLength = (lengthX < lengthY ? lengthX : lengthY) + 1;
    char *pStr = new char[maxLength];
    char *p = pStr + maxLength - 1;
    *p = '\0'; // 字符串末尾结束符

    // 根据追踪数组回溯最长公共子序列
    for (int i = lengthX, j = lengthY; i > 0 && j > 0;) {
        if (rec[i][j] == LU) {
            *(--p) = x[i - 1]; // LU 才说明 x[i]==y[j]，该字符是最长公共子序列的一部分
            --i;
            --j;
        } else if (rec[i][j] == L) {
            --j;
        } else if (rec[i][j] == U) {
            --i;
        }
    }

    return string(p);
}

算法分析

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(n^2)$