查找---最大公共子串、最长公共子序列

时间:2022-04-13 16:02:45


转自https://www.nowcoder.com/questionTerminal/98dc82c094e043ccb7e0570e5342dd1b



查找---最大公共子串、最长公共子序列

最长公共子串(LCS)

找两个字符串的最长公共子串,这个子串要求在原字符串中是连续的。其实这又是一个序贯决策问题,可以用动态规划来求解。我们采用一个二维矩阵来记录中间的结果。这个二维矩阵怎么构造呢?直接举个例子吧:"bab"和"caba"(当然我们现在一眼就可以看出来最长公共子串是"ba"或"ab")

   b  a  b

c  0  0  0

a  0  1  0

b  1  0  1

a  0  1  0

我们看矩阵的斜对角线最长的那个就能找出最长公共子串。

不过在二维矩阵上找最长的由1组成的斜对角线也是件麻烦费时的事,下面改进:当要在矩阵是填1时让它等于其左上角元素加1。

   b  a  b

c  0  0  0

a  0  1  0

b  1  0  2

a  0  2  0

这样矩阵中的最大元素就是 最长公共子串的长度。

查找---最大公共子串、最长公共子序列


查找---最大公共子串、最长公共子序列   

查找---最大公共子串、最长公共子序列

关于vector<vector<int> >dp(m+1,vector<int>(n+1,0));参考http://write.blog.csdn.net/postedit


#############################################################

#############################################################

#############################################################

二:概念

     举个例子,cnblogs这个字符串中子序列有多少个呢?很显然有27个,比如其中的cb,cgs等等都是其子序列,我们可以看出

子序列不见得一定是连续的,连续的那是子串。

     我想大家已经了解了子序列的概念,那现在可以延伸到两个字符串了,那么大家能够看出:cnblogs和belong的公共子序列吗?

在你找出的公共子序列中,你能找出最长的公共子序列吗?

查找---最大公共子串、最长公共子序列

从图中我们看到了最长公共子序列为blog,仔细想想我们可以发现其实最长公共子序列的个数不是唯一的,可能会有两个以上,

但是长度一定是唯一的,比如这里的最长公共子序列的长度为4。


子串应该比较好理解,至于什么是子序列,这里给出一个例子:有两个母串

  • cnblogs
  • belong

比如序列bo, bg, lg在母串cnblogs与belong中都出现过并且出现顺序与母串保持一致,我们将其称为公共子序列。最长公共子序列(Longest Common Subsequence, LCS),顾名思义,是指在所有的子序列中最长的那一个。子串是要求更严格的一种子序列,要求在母串中连续地出现。在上述例子的中,最长公共子序列为blog(cnblogs,belong),最长公共子串为lo(cnblogs, belong)。


查找---最大公共子串、最长公共子序列

查找---最大公共子串、最长公共子序列