JavaScript语言描述的最大公共子串问题

常见的做法是使用矩阵
服务器君一共花费了232.487 ms进行了5次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

求最大公共子串,常见的做法是使用矩阵。假设有字符串: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,这样便可以只使用一个一维数组。

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

function LCS(str1, str2) {
    if (str1 === "" || str2 === "") {
        return "";
    }
    var len1 = str1.length;
    var len2 = str2.length;
    
    var a = new Array(len1);
    var maxLen = 0;
    var maxPos = 0;
    
    for (var i = 0; i < len1; i++) { //行
        for (var j = len2 - 1; j >= 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;
            }
        }
    }
    return str1.substr(maxPos - maxLen + 1, maxLen);
}

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

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

function findMaxSubStr(s1,s2){ 
    var str= "",
        L1=s1.length,
        L2=s2.length; 
    
    if (L1>L2){ 
        var s3=s1;
        s1=s2;
        s2=s3;
        s3 = null;
        L1=s2.length;
        L2 = s1.length;
    }
    
    
    for (var i=L1; i > 0; i--) {
        for (var j= 0; j <= L2 - i && j < L1; j++){ 
            str = s1.substr(j, i);
            if (s2.indexOf(str) >= 0) {
                return str; 
            }
        } 
    }
    
    return ""; 
} 

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

完整示例:

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
 <head>
  <title>www.nowamagic.net</title>
  <style type='text/css'>
	body {background-color:#fff;}
  </style>
 </head>
 <body>
<script type='text/javascript'>
function LCS(str1, str2) {
	if (str1 === "" || str2 === "") {
		return "";
	}
	var len1 = str1.length;
	var len2 = str2.length;
	
	var a = new Array(len1);
	var maxLen = 0;
	var maxPos = 0;
	
	for (var i = 0; i < len1; i++) { //行
		for (var j = len2 - 1; j >= 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;
			}
		}
	}
	return str1.substr(maxPos - maxLen + 1, maxLen);
}
function findMaxSubStr(s1,s2){ 
    var str= "",
	L1=s1.length,
	L2=s2.length; 
	
    if (L1>L2) { 
	var s3=s1;
	s1=s2;
	s2=s3;
	s3 = null;
	L1=s2.length;
	L2 = s1.length;
    }
	
	
    for (var i=L1; i > 0; i--) {
	for (var j= 0; j <= L2 - i && j < L1; j++){ 
            str = s1.substr(j, i);
            if (s2.indexOf(str) >= 0) {
		return str; 
	    }
       } 
    }
	
    return ""; 
} 
    !(function() {
	var tmpArr = [];
	for (var i = 97; i < 97 + 26; i++) {
		tmpArr.push(String.fromCharCode(i));
	}
	
	var s2 = tmpArr.join("");
	tmpArr.sort(function() {return Math.random() > 0.7;});
	var s1 = new Array(600).join(tmpArr.join(""));
	
	
	var date = getNow();
	alert(	"消耗时间:" + (getNow() - date) + "秒  " + LCS(s1, s2));
	date = getNow();
	alert(	"消耗时间:" + (getNow() - date) + "秒  " + findMaxSubStr(s1, s2)	);
   })();
function getNow() {
	return new Date().getTime();
}
</script>
 </body>
</html>

本文地址:http://www.nowamagic.net/librarys/veda/detail/1596,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/1596

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《代码整洁之道》 马丁(Robert C. Martin) (作者), 韩磊 (译者)

软件质量,不但依赖于架构及项目管理,而且与代码质量紧密相关。这一点,无论是敏捷开发流派还是传统开发流派,都不得不承认。《代码整洁之道》提出一种观念:代码质量与其整洁度成正比。干净的代码,既在质量上较为可靠,也为后期维护、升级奠定了良好基础。作为编程领域的佼佼者,《代码整洁之道》作者给出了一系列行之有效的整洁代码操作实践。这些实践在《代码整洁之道》中体现为一条条规则(或称“启示”),并辅以来自现实项目的正、反两面的范例。只要遵循这些规则,就能编写出干净的代码,从而有效提升代码质量。

更多计算机宝库...