JavaScript实现求最大公共子串的方法

2023-09-16 21:35:05 59

本文实例讲述了JavaScript实现求最大公共子串的方法。分享给大家供大家参考，具体如下：

求最大公共子串，常见的做法是使用矩阵。假设有字符串：abcdefg和字符串abcd，则可构成如下表所示矩阵。

a b c d e f g a 1 0 0 0 0 0 0 b 0 1 0 0 0 0 0 c 0 0 1 0 0 0 0 d 0 0 0 1 0 0 0

对两个字符串的每一项都进行比较，若匹配则该项为1，不匹配则为0。然后求出对角线最长为1的那一段序列，即为最大公共子串。看上面的分开，似乎得使用二维数组了，在两个字符串都较大的情况下不是很划算，是否可以进一步优化？

可以，需要改变一下策略，如果该项匹配，则该项的值为再设为1，而是其对角线a[i-1,j-1](i>1&&j>1)的值+1，这样便可以只使用一个一维数组。

以一个字符串作为“行”，另一个作为“列”，比较两个字符串各项的值，用另外一个变量记录数组的最大值和字符串的起始位置。代码如下：

functionLCS(str1,str2){
if(str1===""||str2===""){
return"";
}
varlen1=str1.length;
varlen2=str2.length;
vara=newArray(len1);
varmaxLen=0;
varmaxPos=0;
for(vari=0;i=0;j--){//列
if(str1.charAt(j)==str2.charAt(i)){
if(i===0||j===0){
a[j]=1;
}else{
a[j]=a[j-1]+1;
}
}else{
a[j]=0;
}
if(a[j]>maxLen){
maxLen=a[j];
maxPos=j;
}
}
}
returnstr1.substr(maxPos-maxLen+1,maxLen);
}

但代码其实并不是最优的，为什么？因为上面的写法必须等待两层循环都完成。有没有相对更快一些的方法呢？

设有字符串a、b，其长度分别为len1、len2，其公共字子串一定是<=Math.min(len1,len2)，而且子串必定连续，且一定是a、b的子串。

functionfindMaxSubStr(s1,s2){
varstr="",
L1=s1.length,
L2=s2.length;
if(L1>L2){
vars3=s1;
s1=s2;
s2=s3;
s3=null;
L1=s2.length;
L2=s1.length;
}
for(vari=L1;i>0;i--){
for(varj=0;j<=L2-i&&j=0){
returnstr;
}
}
}
return"";
}

先比较s1、s2的长度，然后取较短的字符串作为。substr(idex,len)，所以拿较短的串取其子串，然后判断它是否在较长的字符串中存在，如果存中则直接返回，否则再取下一位。

完整示例：




www.nhooo.com

body{background-color:#fff;}




functionLCS(str1,str2){
if(str1===""||str2===""){
return"";
}
varlen1=str1.length;
varlen2=str2.length;
vara=newArray(len1);
varmaxLen=0;
varmaxPos=0;
for(vari=0;i=0;j--){//列
if(str1.charAt(j)==str2.charAt(i)){
if(i===0||j===0){
a[j]=1;
}else{
a[j]=a[j-1]+1;
}
}else{
a[j]=0;
}
if(a[j]>maxLen){
maxLen=a[j];
maxPos=j;
}
}
}
returnstr1.substr(maxPos-maxLen+1,maxLen);
}
functionfindMaxSubStr(s1,s2){
varstr="",
L1=s1.length,
L2=s2.length;
if(L1>L2){
vars3=s1;
s1=s2;
s2=s3;
s3=null;
L1=s2.length;
L2=s1.length;
}
for(vari=L1;i>0;i--){
for(varj=0;j<=L2-i&&j=0){
returnstr;
}
}
}
return"";
}
!(function(){
vartmpArr=[];
for(vari=97;i<97+26;i++){
tmpArr.push(String.fromCharCode(i));
}
vars2=tmpArr.join("");
tmpArr.sort(function(){returnMath.random()>0.7;});
vars1=newArray(600).join(tmpArr.join(""));
vardate=getNow();
alert("消耗时间："+(getNow()-date)+"秒"+LCS(s1,s2));
date=getNow();
alert("消耗时间："+(getNow()-date)+"秒"+findMaxSubStr(s1,s2));
})();
functiongetNow(){
returnnewDate().getTime();
}

更多关于JavaScript相关内容感兴趣的读者可查看本站专题：《JavaScript数学运算用法总结》、《JavaScript数据结构与算法技巧总结》、《JavaScript数组操作技巧总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》

希望本文所述对大家JavaScript程序设计有所帮助。

JavaScript实现求最大公共子串的方法

热门推荐

随机推荐