最长公共子序列与最长公共子串

0. 引言

最近鄙人面试百度,出了这道求解公子序列长度的算法题。故此总结一下,这是一个很典型的题目,希望对大家将来的面试中能起到学习的作用。

1. 问题描述

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

  • cnblogs
  • belong

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

2. 求解算法

对于母串X=<x1,x2,⋯,xm>, Y=<y1,y2,⋯,yn>,求LCS与最长公共子串。

暴力解法 假设 m<n, 对于母串X,我们可以暴力找出2的m次方个子序列,然后依次在母串Y中匹配,算法的时间复杂度会达到指数级O(n∗2的m次)。显然,暴力求解不太适用于此类问题。

动态规划 假设Z=<z1,z2,⋯,zk>是X与Y的LCS, 我们观察到 如果Xm=Yn,则Zk=Xm=Yn,有Zk−1是Xm−1与Yn−1的LCS; 如果Xm≠Yn,则Zk是Xm与Yn−1的LCS,或者是Xm−1与Yn的LCS。 因此,求解LCS的问题则变成递归求解的两个子问题。但是,上述的递归求解的办法中,重复的子问题多,效率低下。改进的办法——用空间换时间,用数组保存中间状态,方便后面的计算。这就是动态规划(DP)的核心思想了。

DP求解LCS 用二维数组c[i][j]记录串x1x2⋯xi与y1y2⋯yj的LCS长度,则可得到状态转移方程

public static int lcs(String str1, String str2) {
    int len1 = str1.length();
    int len2 = str2.length();
    int c[][] = new int[len1 + 1][len2 + 1];
    for (int i = 0; i <= len1; i++) {
        for (int j = 0; j <= len2; j++) {
            if (i == 0 || j == 0) {
                c[i][j] = 0;
            }
            else if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                c[i][j] = c[i - 1][j - 1] + 1;
            }
            else {
                c[i][j] = max(c[i - 1][j], c[i][j - 1]);
            }
        }
    }
    return c[len1][len2];
}

DP求解最长公共子串 前面提到了子串是一种特殊的子序列,因此同样可以用DP来解决。定义数组的存储含义对于后面推导转移方程显得尤为重要,糟糕的数组定义会导致异常繁杂的转移方程。考虑到子串的连续性,将二维数组c[i][j]用来记录具有这样特点的子串——结尾同时也为为串x1x2⋯xi与y1y2⋯yj的结尾——的长度。 得到转移方程:

最长公共子串的长度为 max(c[i,j]), i∈{1,⋯,m},j∈{1,⋯,n}。 代码实现

public static int lcs(String str1, String str2) {
    int len1 = str1.length();
    int len2 = str2.length();
    int result = 0;     //记录最长公共子串长度  
    int c[][] = new int[len1+1][len2+1];
    for (int i = 0; i <= len1; i++) {
        for( int j = 0; j <= len2; j++) {
            if(i == 0 || j == 0) {
                c[i][j] = 0;
            } else if (str1.charAt(i-1) == str2.charAt(j-1)) {
                c[i][j] = c[i-1][j-1] + 1;
                result = max(c[i][j], result);
            } else {
                c[i][j] = 0;
            }
        }
    }
    return result;
}  

原文发布于微信公众号 - 机器学习算法全栈工程师(Jeemy110)

原文发表时间:2017-07-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏mathor

matlab—数值微积分

12840
来自专栏進无尽的文章

数据结构与算法 - 时间复杂度与空间复杂度

时间复杂度:时间复杂度的计算并不是计算程序具体运行的时间,而是算法执行语句的最大次数。 空间复杂度:类似于时间复杂度的讨论,一个算法的空间复杂度为该算法所耗费...

85420
来自专栏java一日一条

java float double精度为什么会丢失?浅谈java的浮点数精度问题

由于对float或double 的使用不当,可能会出现精度丢失的问题。问题大概情况可以通过如下代码理解:

14210
来自专栏MyBlog

数值分析读书笔记(5)数值逼近问题(I)----插值极其数值计算

当给定插值函数是多项式函数的时候, 我们可以产生一种插值的方案, 下面介绍一下Lagrange插值

18310
来自专栏mukekeheart的iOS之旅

算法——(转)动态规划入门

动态规划相信大家都知道,动态规划算法也是新手在刚接触算法设计时很苦恼的问题,有时候觉得难以理解,但是真正理解之后,就会觉得动态规划其实并没有想象中那么难。网上也...

20010
来自专栏拂晓风起

Flex Actionscript 3 小球碰撞 多球碰撞

14940
来自专栏mathor

floyd算法

 floyd算法解决的问题是在图中找到从i号结点到j号结点最短路径值(边的权值)的问题,核心代码就下面四行

30910
来自专栏marsggbo

[转载]Tensorflow 的reduce_sum()函数的axis,keep_dim这些参数到底是什么意思?

转载链接:https://www.zhihu.com/question/51325408/answer/125426642 来源:知乎

19850
来自专栏aCloudDeveloper

算法导论第八章线性时间排序

一、线性时间排序算法历史概览       计数排序首先是由 Harold H. Seward 于1954年提出,而且他还提出将计数排序和基数排序进行结合的思想;...

24460
来自专栏Coding迪斯尼

详解神经网络算法所需最基础数据结构Tensor及其相关操作

10540

扫码关注云+社区

领取腾讯云代金券