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

2017-04-30  本文已影响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);
}

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

上一篇下一篇

猜你喜欢

热点阅读