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)}

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

相关推荐:Python视频教程

②重叠子问题

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

原问题是：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)，它总共出现了三次。假如用递归求解，fib(2)用DP计算三次（Dynamic Programming）在动态规划中，fib（2）只计算一次，另外两次直接通过“检查表”获得。更重要的是，在找到问题的解决方案后，没有必要继续分解问题。对于递归，它是不断地解决问题，直到它被分解为基准问题（fib(0)或fib(1)

说了这么多，写下最长公共子序列的递归式是完整的。

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

三、LCS 实现Python代码实现

#!/usr/bin/envpython3
#-*-coding:utf-8-*-
#Note:用于解决两个字符串的最长公共子序列
deflongestCommonSequence(str_one,str_two,case_sensitive=True):
"""
str_one和str_two最长的公共子序列
:paramstr_one:字符串1
:paramstr_two:字符串2(正确结果)
:paramcase_sensitive:比较时是否区分大小写，默认区分大小写
:return:公共子序列长度最长
"""
len_str1=len(str_one)
len_str2=len(str_two)
#定义一个列表来保存公共子序列长度最长，并初始化
record=[[[0forinrange](len_str2+1)forjinrange(len_str1+1)
foriinrange(len_str1):
forjinrange(len_str2):
ifstr_one[i]==str_two[j]:
record[i+1][j+1]=record[i][j]+1
elifrecord[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]
returnrecord[-1][-1]
if__name__='__main__':
#字符串1
s1="BDCABA"
#字符串2
s2="ABCBDAB"
#计算最长公共子序列的长度
res=longestCommonSequence(s1,s2)
#打印结果
print(res)#4