如何在 Python 中找到最长的公共子序列

Python-求解两个字符串的最长公共子序列

一、问题描述

给定两个字符串，找出这两个字符串的最长公共子序列（Longest Common Sequence）。例如，字符串 1：BDCABA；字符串 2：ABCBDAB。那么这两个字符串的最长公共子序列的长度为4，最长公共子序列为：BCBA。

二、算法求解

这是一个动态规划问题。对于可以用动态规划求解的问题，一般有两个特点：①最优子结构； ②重叠子问题

①最优子结构

设X=(x1,x2,...,xn)和Y=(y1,y2,...,ym)是两个序列，将X和Y的最长公共子序列记为LCS(X,Y)

寻找 LCS(X,Y) 是一个优化问题。因为，我们需要找到X和Y的最长公共子序列。而要找到X和Y的LCS，首先要考虑X的最后一个元素和Y的最后一个元素。

(1) 若xn=ym，即X的最后一个元素与Y的最后一个元素相同，也就是说该元素一定在公共子序列中。因此，现在只需要求：LCS(Xn-1,Ym-1)

LCS(Xn-1, Ym-1) 是原问题的一个子问题。为什么称为子问题？因为它的规模比原来的问题小。

为什么它是最优子问题？因为我们要找的是Xn-1和Ym-1的最长公共子序列。最长！换句话说，最好的。

(2) 如果xn!=ym，这有点麻烦，因为它产生了两个子问题：LCS(Xn-1,Ym)和LCS(Xn,Ym-1)

因为序列X和序列Y的末尾元素不相等，意味着末尾元素不可能是最长公共子序列中的元素。

LCS(Xn-1,Ym)表示：最长公共序列可以在(x1,x2,...xn-1)和(y1,y2,...,ym)中找。

LCS(Xn,Ym-1)表示：最长公共序列可以在(x1,x2,...xn)和(y1,y2,...,ym-1)中找。

求解以上两个子问题，谁得到的最长公共子序列就是LCS(X,Y)。在数学上，它是：

LCS=max{LCS(Xn-1,Ym),LCS(Xn,Ym-1)}

由于条件⑴和⑵，考虑了所有可能的情况。因此，我们成功地将原来的问题转化为三个更小的问题。

②重叠子问题

什么是重叠子问题？也就是说，原问题转化为子问题后，子问题中存在同样的问题。

原问题是：LCS(X,Y)。子问题有❶LCS(Xn-1,Ym-1)❷ LCS(Xn-1,Ym)❸ LCS(Xn,Ym-1)

乍一看，这三个问题并不重叠。但本质上它们是重叠的，因为它们只重叠了很大一部分。例子：

第二个子问题：LCS(Xn-1,Ym)就包含了问题❶LCS(Xn-1,Ym-1)，为什么？

因为，当Xn-1和Ym的最后一个元素不相同时，我们需要将LCS(Xn-1,Ym-1)分解为：LCS(Xn-1,Ym-1)和LCS(Xn -2, ym)

也就是说：在子问题的不断分解中，有些问题是重叠的。

由于像 LCS 这样具有重叠子问题的问题的性质，使用递归来解决它们并不划算。为了使用递归，它反复求解子问题，需要注意的是所有子问题相加的数量是指数级的。

那么问题来了，如果用递归来解决，有指数级的子问题，所以时间复杂度是指数级的。使用动态规划时，这个指数子问题会变成多项式时间吗？ ？

关键是在使用动态规划的时候，不需要把那些重叠的子问题一一计算。换句话说：使用动态规划后，一些子问题直接通过“查表”得到，而不是重新计算。例如：比如求Fib序列。

查找 fib(5) 分解为两个子问题：fib(4) 和 fib(3)。在求解fib(4)和fib(3)的时候，它分解了一系列的小问题...

从图中可以看出：根的左右子树：在fib(4)和fib(3)下，有很多重叠！例如，对于 fib(2)，它出现了 3 次。如果用递归求解，fib(2)会计算3次，而用DP(Dynamic Programming)动态规划，fib(2)只会计算一次，另外两次直接通过“look-”得到上桌”。而且，更重要的是：找到问题的解决方案后，就没有必要再继续分解问题了。对于递归，问题不断求解，直到分解为基准问题（fib(0) 或 fib(1)）

说了这么多，还是把最长公共子序列的递推公式写下来吧。

C[i,j]表示：(x1,x2,...,xi)和(y1,y2,...,yj)的最长公共子序列的长度。公式的具体解释请参考《算法导论》动态规划章节

三、LCS Python代码实现

#! /usr/bin/env python3
# -*- coding:utf-8 -*-
# Note     : 用于实现求解两个字符串的最长公共子序列
def longestCommonSequence(str_one, str_two, case_sensitive=True):
    """
    str_one 和 str_two 的最长公共子序列
    :param str_one: 字符串1
    :param str_two: 字符串2（正确结果）
    :param case_sensitive: 比较时是否区分大小写，默认区分大小写
    :return: 最长公共子序列的长度
    """
    len_str1 = len(str_one)
    len_str2 = len(str_two)
    # 定义一个列表来保存最长公共子序列的长度，并初始化
    record = [[0 for i in range(len_str2 + 1)] for j in range(len_str1 + 1)]
    for i in range(len_str1):
        for j in range(len_str2):
            if str_one[i] == str_two[j]:
                record[i + 1][j + 1] = record[i][j] + 1
            elif record[i + 1][j] > record[i][j + 1]:
                record[i + 1][j + 1] = record[i + 1][j]
            else:
                record[i + 1][j + 1] = record[i][j + 1]
    return record[-1][-1]
if __name__ == '__main__':
    # 字符串1
    s1 = "BDCABA"
    # 字符串2
    s2 = "ABCBDAB"
    # 计算最长公共子序列的长度
    res = longestCommonSequence(s1, s2)
    # 打印结果
    print(res) # 4