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

2019-11-19 14:25:23

字体：大中小

来源：转载

供稿：网友

本文实例讲述了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.VeVB.COm</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设计模式之调停者模式实例详解

下一篇：Node.js实现mysql连接池使用事务自动回收连接的方法示例