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

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

作者: 怖拉修 | 来源:发表于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);
    }
    

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

    相关文章

      网友评论

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

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