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

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 条评论
登录 后参与评论

相关文章

来自专栏小小挖掘机

如何使用tensorflow做张量排序和字符串拼接?

本文,将总结一下最近使用tensorflow中遇到的两个小需求:张量排序和字符串拼接,咱们一起来学习一下,嘻嘻!

1572
来自专栏机器学习和数学

[ Tensorflow]Tensorflow Reduction operations

reduce系列在平时工程中是经常使用的,其中reduce_sum是使用最频繁的一个。主要用在计算loss的时候,当我们定义好loss之后,我们一般要求loss...

3544
来自专栏marsggbo

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

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

1585
来自专栏ATYUN订阅号

【学术】独热编码如何在Python中排列数据?

机器学习算法不能直接处理分类数据,分类数据必须转换为数字。这适用于当你处理一个序列分类类型的问题,并计划使用深度学习方法,比如长短期循环神经网络(RNN)时。 ...

38910
来自专栏蜉蝣禅修之道

LeetCode之Jump Game II

1514
来自专栏mathor

matlab—数值微积分

834
来自专栏拂晓风起

Flex Actionscript 3 小球碰撞 多球碰撞

1294
来自专栏java一日一条

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

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

662
来自专栏進无尽的文章

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

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

1692
来自专栏派森公园

最简单的NP-Hard问题

1618

扫码关注云+社区