动态规划问题（2）——寻找最长公共子串

wushuiyong 发布于2019-08-21 11:27 / 3012人阅读

摘要：题目给定两个字符串求出它们的最长公共字串说明比如在单词和它们的最长公共子序列是。最长公共子串和最长公共子序列的区别。

题目

给定两个字符串,求出它们的最长公共字串

var str1="abcdefg";
var str2="xyzabcd";

说明：比如在单词"abcdefg"和"abcdefg"它们的最长公共子序列是"abcd"。寻找最长子序列常用于遗传学中，用于使用核苷酸碱基的首字母对DNA的描述（这段话从网上抄的）。

最长公共子串和最长公共子序列的区别。

最长公共子串和最长公共子序列的区别为：子串是串的一个连续的部分，子序列则是从不改变序列的顺序，而从序列中去掉任意的元素而获得新的序列；也就是说，子串中字符的位置必须是连续的，子序列则可以不必连续。

这道题，想了很长时间，终于慢慢的把题目做出来了，接下来的内容可能会很难理解，也许我比较笨吧至少对我来说想了好久。我会尽量结合图文去展示解题的思路，也可以自己想想，然后在看接下来的内容。

暴力破解

其实看到这个问题我们直接可以用暴力的方式解决这个问题。给定两个字符串A和B，我们可以通过从A的第一个字符开始与B对应的每一个字符进行对比的方式找到最长的公共字串。如果此时没有找到匹的字母，则移动到A的第二个字符处，然后从B的第一个字符处进行对比，以此类推。由于下面的内容较多，爆力方法我这里就不写了。

动态规划

我们回顾一下动态规划的解题思路：

从底部开始解决问题，将所有小问题解决掉，然后合并成一个整体的解决方案。

使用一个数组建立一张表，用于存放被分解成众多子问题的解。

那基于这两点我们首先要分解这个问题，怎么分解呢？

第一步： 最小的是每个字符，所以要把分解成单个的字符去匹配每个单个的字符。因此这里我们可以得到下面这一张表：

匹配为1，不匹配为0，这个时候我们就分解成为每个字符的匹配情况，由此得到。

第二步： 每个子问题有了，这个时候我们要建立一个数组去存放每个子问题的解。关键问题在于，我们怎么样把每个子问题的解存起来，并且可以得到我们想要的结果。对表做一些处理，初始化一个二维数组：

var arr = new Array(str1.length + 1);
for (var i = 0; i <= str1.length + 1; i++) {
    arr[i] = new Array(str2.length + 1);
    for (var j = 0; j <= str2.length + 1; j++) {
        arr[i][j] = 0;
    }
}

得到如下的表：

图中我们可以看到行和列都多加了一个并且都是0，这是为了判断上一个是否相等的操作，后面你就会明白它的意思了。

对初始化的二维数组坐些处理，得到如下图：

一开始看到这个图的时候你可能会很懵逼，如果你已经看明白了，那你就跳过我这段废话吧。我们应该一直的告诉自己，新建的这个数组是存放每个子问题的解，首先要明确的是找出最长字串，有哪些方式可以做到把字串从原来的字符串中截取，所以要知道起始位置和字串的长度。从图中可以看到的红字就是存放这个位置的最优解字串的长度，所以应该建立两个变量去存储其实位置的index 和最大长度 maxLen 。得到一下代码：

var maxLen = 0;
var index = 0;
for(var i = 0; i <= str1.length; i++){
    for(var j = 0; j <= str2.length; j++){
        if(i == 0 || j == 0){
            arr[i][j] = 0
        }else{
            if (str1[i] == str2[j] && str1[i - 1] == str2[j - 1]) {
                arr[i][j] = arr[i - 1][j - 1] + 1;
            }else{
                arr[i][j] = 0;
            }
        }
        if(arr[i][j] > maxLen){
            maxLen = arr[i][j];
            index = i;
        }
    }
}

简单的解释一下，这里要明确连续的字串的位置，是二维数组对角线上的值，这点明确了很多问题就好理解了。

上面的代码把最主要的两个参数找到了，那接下来就是选择其中的一个字符串去截取字串：

var str = "";
if(maxLen == 0){
    return "";
}else{
    for(var k = index - maxLen; k < maxLen; k++){
        str += str1[k];
    }
    return str;
}

下面贴上完整的代码，你也可以去我的github上查看源码；

function LCS(str1, str2){
    var maxLen = 0;
    var index = 0;

    var arr = new Array();
    for (var i = 0; i <= str1.length + 1; i++) {
        arr[i] = new Array();
        for (var j = 0; j <= str2.length + 1; j++) {
            arr[i][j] = 0;
        }
    }

    for(var i = 0; i <= str1.length; i++){
        for(var j = 0; j <= str2.length; j++){
            if(i == 0 || j == 0){
                arr[i][j] = 0
            }else{
                if (str1[i] == str2[j] && str1[i - 1] == str2[j - 1]) {
                    arr[i][j] = arr[i - 1][j - 1] + 1;
                }else{
                    arr[i][j] = 0;
                }
            }
            if(arr[i][j] > maxLen){
                maxLen = arr[i][j];
                index = i;
            }
        }
    }

    var str = "";
    if(maxLen == 0){
        return "";
    }else{
        for(var k = index - maxLen; k < maxLen; k++){
            str += str1[k];
        }
        return str;
    }
}
var str1="abcdefg";
var str2="xyzabcd";
LCS(str1, str2)     // abcd

到此为止我们终于找到了最长公共字串。到这里我们需要想想能不能在优化了，虽然这样解决问题，但是引入了一个二维数组，在两个字符串都较大的情况下不是很划算，是否可以进一步优化？答案是可以的，需要改变一下策略，是否可以建立一个一维数组就可以解决问题了呢，这里晚了先写这么多把，之后我会在公众号中贴出暴力解法和动态规划的优化解法，欢迎持续关注我的公众号获得一手的信息。

欢迎关注微信公众账号查看最新文章

GPU云服务器云服务器最长公共子串 java最长相同子串最长公共子序列 java公共子串

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/86727.html

[算法笔记]动态规划之最长公共子串和最长公共子序列

摘要：源代码管理中，指令，可以查找出编辑前后文件的差异，这是基于动态规划实现的。编辑距离，判断字符串的相似程度，也是基于动态规划计算。本文是《算法图解》笔记应用场景一切脱离实际应用场景的算法都是耍流氓！生物学家根据最长公共序列来确定 DNA 链的相似性，进而判断两种动物或疾病有多相似。最长公共序列还被用来寻找多发性硬化症治疗方案。源代码管理中，git diff指令，可以查找出编辑...

DandJ 2019-07-30 15:40 评论0 收藏0
算法设计 - LCS 最长公共子序列&&最长公共子串 &&LIS 最

摘要：若且，则是和的最长公共子序列若且，则是和的最长公共子序列。递归结构容易看到最长公共子序列问题具有子问题重叠性质。例如，在计算和的最长公共子序列时，可能要计算出和及和的最长公共子序列。虽是读书笔记，但是如转载请注明出处 http://segmentfault.com/blog/exploring/ .. 拒绝伸手复制党本章讲解： 1. LCS（最长公共子序列）O(n^2)的时间复杂...

weizx 2019-08-14 12:07 评论0 收藏0
字符串处理文章outline

摘要：遇到问题查查，看看，大神的讲解问问岛胖君下面是我最近整理出来的关于字符串的文章的怎么翻译汇集目录非常希望强化博客的功能，比如分类，置顶。虽是读书笔记，但是如转载请注明出处 http://segmentfault.com/blog/exploring/ .. 拒绝伸手复制党最近在看算法和语言，基本属于看知识 --> java实现 --> 整理blog 这个路线。遇到问题查查st...

Karuru 2019-08-14 15:07 评论0 收藏0
动态规划法（十）最长公共子序列（LCS）问题

摘要：最长公共子序列问题指的是求解两个序列和的长度最长的公共子序列。当然，可以看出，问题容易出现重叠子问题，这时候，就需要用动态规划法来解决。问题介绍给定一个序列$X=$，另一个序列$Z=$满足如下条件时称为X的子序列：存在一个严格递增的X的下标序列${i_1,i_2,...,i_k}$，对所有的$j=1,2,...,k$满足$x_{i_j}=z_j.$ 给定两个序列$X$和$Y$...

Ashin 2019-08-15 18:17 评论0 收藏0
动态规划法（十）最长公共子序列（LCS）问题

摘要：最长公共子序列问题指的是求解两个序列和的长度最长的公共子序列。当然，可以看出，问题容易出现重叠子问题，这时候，就需要用动态规划法来解决。问题介绍给定一个序列$X=$，另一个序列$Z=$满足如下条件时称为X的子序列：存在一个严格递增的X的下标序列${i_1,i_2,...,i_k}$，对所有的$j=1,2,...,k$满足$x_{i_j}=z_j.$ 给定两个序列$X$和$Y$...

IamDLY 2019-07-30 16:49 评论0 收藏0