未加星标

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

字体大小 | |
[前端(javascript) 所属分类 前端(javascript) | 发布者 店小二04 | 时间 | 作者 红领巾 ] 0人收藏点击收藏

本文实例讲述了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,这样便可以只使用一个一维数组。

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

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.jb51.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>

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

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


您可能感兴趣的文章:JavaScript自定义函数实现查找两个字符串最长公共子串的方法js判断一个字符串是否包含一个子串的方法js判断出两个字符串最大子串的函数实现方法JS使用正则表达式找出最长连续子串长度在JavaScript中访问字符串的子串JavaScript检查子字符串是否在字符串中的方法JavaScript判断一个字符串是否包含指定子字符串的方法javascript查找字符串中出现最多的字符和次数的小例子js中通过split函数分割字符串成数组小例子JavaScript计算字符串中每个字符出现次数的小例子javascript下搜索子字符串的的实现代码(脚本之家修正版)

本文前端(javascript)相关术语:javascript是什么意思 javascript下载 javascript权威指南 javascript基础教程 javascript 正则表达式 javascript设计模式 javascript高级程序设计 精通javascript javascript教程

tags: var,gt,lt,JavaScript,s2,s1,字符串,length,str1,return,maxLen,L1,子串
分页:12
转载请注明
本文标题:JavaScript实现求最大公共子串的方法
本站链接:http://www.codesec.net/view/572190.html
分享请点击:


1.凡CodeSecTeam转载的文章,均出自其它媒体或其他官网介绍,目的在于传递更多的信息,并不代表本站赞同其观点和其真实性负责;
2.转载的文章仅代表原创作者观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,本站对该文以及其中全部或者部分内容、文字的真实性、完整性、及时性,不作出任何保证或承若;
3.如本站转载稿涉及版权等问题,请作者及时联系本站,我们会及时处理。
登录后可拥有收藏文章、关注作者等权限...
技术大类 技术大类 | 前端(javascript) | 评论(0) | 阅读(36)