动态规划之 LCS （最长公共子序列/最长公共子串）

Question

最长公共子序列（Longest Common Subsequence LCS）是从给定的两个序列 X 和 Y 中取出尽可能多的一部分字符，按照它们在原序列排列的先后次序排列得到。

LCS 问题的算法用途广泛，如在软件不同版本的管理中，用 LCS 算法找到新旧版本的异同处;在软件测试中，用 LCS 算法对录制和回放的序列进行比较，在基因工程领域，用 LCS 算法检查患者 DNA 连与键康 DNA 链的异同;在防抄袭系统中，用 LCS 算法检查论文的抄袭率。LCS 算法也可以用于程序代码相似度度量，人体运行的序列检索，视频段匹配等方面，所以对 LCS 算法进行研究具有很高的应用价值。

动态规划思想，把大问题分解成若干小问题，用矩阵记录状态结果。

一、 最长公共子序列 & 最长公共子串的区别

找两个字符串的最长公共子串，这个子串要求在原字符串中是连续的。而最长公共子序列则并不要求连续。

• 子序列(subsequence)： 一个特定序列的子序列就是将给定序列中零个或多个元素去掉后得到的结果(不改变元素间相对次序)。例如序列 <A,B,C,B,D,A,B> 的子序列有：<A,B>、<B,C,A>、<A,B,C,D,A>等。
• 子串： 将一个序列从最前或最后或同时删掉零个或几个字符构成的新系列。区别与子序列，子序列是可以从中间抠掉字符的。

子串是串的一个连续的部分，子序列则是从不改变序列的顺序，而从序列中去掉任意的元素而获得新的序列；也就是说，子串中字符的位置必须是连续的，子序列则可以不必连续。

二、 求最长公共子序列的长度和该子序列

1. 从一个矩阵开始分析，推导出状态迁移方程。

input1 = [" ", "a", "c", "b", "a", "d"],
input2 = [" ", "a", "b", "c", "a", "d", "f"]

首先设置我们的第一个子序列为空字符串。表示字符串无法匹配，你可以理解这是一种辅助的计算方式。

然后，把即将进行比较的第一个字符串当做矩阵的纵坐标，因为我们总是从左往右进行比较。

LCS问题与背包问题有点不一样，背包问题还可以设置 -1 行，而最长公共子序列因为有空子序列的出现，一开始就把左边与上边固定死了。

因为我们这个矩阵是一个状态表，从左到右，从上到下描述状态的迁移过程，并且这些状态是基于已有状态累加出来的。现在我们需要确认的是，现在我们要填的这个格子的值与它周围已经填好的格子的值是存在何种关系。

• 状态转移方程：

假设当 input1[i] == input2[j]时，dp[i][j]=dp[i-1][j-1]+1。

当input1[i] != input2[j]时，dp[i][j] = max(dp[i-1][j],T[i][j-1])。(取它上方或左边的较大值)

(dp[i][j]表示 LCS 的长度)

用一句通俗的话来描述这种dp[i][j]规律，就是相等左上角加一，不等取上或左最大值，如果上左一样大，优先取左。

可以利用反证法来证明这种假设是正确的。

2. 求 LCS 的长度

代码实现：

// dp[i][j] 先找列 后找行
// 规律：相等左上角加一；不等取上或左最大值，如果上左一样大，优先取左。
function LCS(str1, str2) {
    let m = str1.length; // 列
    let n = str2.length; // 行
    let dp = [new Array(n + 1).fill(0)]; // 固定第一行
    for(let i = 1; i <= m; i++) {
        dp[i] = [0]; // 固定第一列 注意 这里要是个数组[0]
        for(let j = 1; j <= n; j++) {
            if(str1[i - 1] === str2[j - 1]) { // str1 str2 要从 i - 1 j - 1开始
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                //dp[i][j] = dp[i][j - 1] >= dp[i - 1][j] ? dp[i][j - 1] : dp[i - 1][j];
            }
        }
    }
    // console.log(dp);
    return dp[m][n];
}

LCS('acbad','abcadf'); // 4

• 算法分析

时间复杂度： O(m * n)；
空间复杂度： O(m * n)；（因为使用了一个动态规划表。）

3. 寻找子序列

我们完成填表后，只能求出最长公共子序列的长度，但是无法得知它的具体构成。我们可以，从填表的反向角度来寻找子序列。

我们子序列保存在名为 s的数组中，从表格中反向搜索，找到目标字符后，每次都把目标字符插入到数组最前面。

根据前面提供的填表口诀，我们可以反向得出寻找子序列的口诀： 如果dp[i][j]来自左上角加一，则是子序列；否则向左或上回退。如果上左一样大，优先取左。

// dp[i][j] 先找列 后找行
function LCS(str1, str2) {
    let m = str1.length; // 列
    let n = str2.length; // 行
    let dp = [new Array(n + 1).fill(0)];
    for(let i = 1; i <= m; i++) {
        dp[i] = [0];
        for(let j = 1; j <= n; j++) {
            if(str1[i - 1] === str2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
            }
        }
    }

    // 从表格左下角开始往前查找
    function printLCS(str1, str2, i, j, dp) {
        let result = [];
        while(i > 0 && j > 0) {
            if(str1[i - 1] === str2[j - 1]) { // i - 1 j - 1
                result.unshift(str1[i - 1]);
                i--;
                j--;
            } else {
                dp[i][j - 1] >= dp[i - 1][j] ? j-- : i--; // 一样大 优先取左
                // dp[i][j - 1] > dp[i - 1][j] ? j-- : i--;  一样大 优先取右
            }
        }
    }
    return printLCS(str1, str2, m, n, dp);
}

LCS('acbad','abcadf'); // ["a", "c", "a", "d"]

可以发现，求出的最长公共子序列只是其中的一个而已，当'一样大，优先取右'，会发现得到另外一个最长公共子序列；并可以取右取左穿插安排，也就是说，两个序列的最长公共子序列是有多个的。

4. 要输出所有LCS的内容

二、 求最长公共子串的长度和该子串

1. 从一个矩阵开始分析，推导出状态迁移方程。

var str1="abcdefg";
var str2="xyzabcd";

最长公共子串是最长公共子序列的一种特殊情况，解法类似。可推导出状态转移方程。

当 input1[i] == input2[j]时，dp[i][j]=dp[i-1][j-1]+1。

当input1[i] != input2[j]时，dp[i][j] = 0。

2. 求长度：找出最大值即可

function LCS(str1, str2) {
    let m = str1.length;
    let n = str2.length;
    let dp = [new Array(n + 1).fill(0)];
    let result = 0;
    for(let i = 1; i <= m; i++) {
        dp[i] = [0];
        for(let j = 1; j <= n; j++) {
            if(str1[i - 1] === str2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                result = Math.max(dp[i][j], result);
            } else {
                dp[i][j] = 0; // 与最长公共子序列的差别仅在这
            }
        }
    }
    return result;
}

3. 寻找子串

需要记录下最大值所在的矩阵坐标，然后往前去找。

Reference

javascript 最长公共子序列
最长公共子序列和最长公共子串区别