美文网首页
如何输出两个字符串的最长公共字符串

如何输出两个字符串的最长公共字符串

作者: 怖拉修 | 来源:发表于2017-04-30 18:32 被阅读0次

最近在看《数据结构与算法JavaScript描述》这本书时,遇到了这个问题。结果我把代码复制到本地后,发现得不到正确的结果,于是对代码进行了改进。

function lcs(word1, word2) { 
word1 = '-' + word1;
word2 = '+' + word2;
var max = 0; 
var index = 0; 
var lcsarr = new Array(word1.length); 
for (var i = 0; i < lcsarr.length; i++) { 
    lcsarr[i] = new Array(word2.length); 
    for (var j = 0; j < lcsarr[0].length; j++) { 
        lcsarr[i][j] = 0; 
    } 
}
for (var i = 1; i < lcsarr.length; i++) { 
    for (var j = 1; j < lcsarr[0].length; j++) {            
        if (word1[i] == word2[j]) { 
            lcsarr[i][j] = lcsarr[i-1][j-1] + 1; 
        }
        if (max < lcsarr[i][j]) { 
            max = lcsarr[i][j]; 
            index = i; 
        }           
    } 
}    
return word1.slice(index+1-max,index+1);
}

不过此代码有缺陷,在最长公共字符串有多个的情况下,只能找到第一个。

相关文章

  • 最长公共子序列2

    描述 给定两个字符串str1和str2,输出两个字符串的最长公共子序列。如果最长公共子序列为空,则返回"-1"。目...

  • 【python】求两个字符串的公共字串?

    题目:找出两个字符串的最长公共字串,例如字符串“abccade”与字符串“dgcadde”的最长公共子串为“cad...

  • 2018-08-09

    动态规划之最长公共子序列 问题描述 给定两个字符串,求解两个字符串的最长公共子序列。比如字符串1:BDCABA;字...

  • 序列比对(二十四)——最长公共子序列

    原创:hxj7 本文介绍如何求解两个字符串的最长公共子序列。 最长公共子序列问题 前文《序列比对(23)最长公共子...

  • 腾讯 2017 暑假实习生编程题(一):给定一个字符串s,你可以

    回文串的特点是,逆序输出和正序输出是一样的。所以这道题可以转化为:如果将此字符串逆序输出,那么两个字符串的最长公共...

  • 2019-10-29

    求2个字符串的最长公共子序列和最长公共子字符串 一. 最长公共子序列 定义: 一个数列S,如果分别是两个或多个已知...

  • 最长公共连续子串

    给出两个字符串(可能包含空格),找出其中最长的公共连续子串,输出其长度。输入描述:输入为两行字符串(可能包含空格)...

  • 练习题:最长公共前缀

    求字符串数组内字符串的最长公共前缀

  • 求最长公共子序列

    问题 给出两个字符串,求出它们之中相对顺序相同,字符相同的最长的公共子序列。 用法 输出 代码实现

  • 最长公共子串

    问题: 找出最长、连续的子字符串 思路: 遍历X、Y的所有子字符串,找出最长公共后缀,则最长公共后缀的长度就是最长...

网友评论

      本文标题:如何输出两个字符串的最长公共字符串

      本文链接:https://www.haomeiwen.com/subject/fpuxtxtx.html