欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  web前端

JavaScript求最大公共子串的方法详解

程序员文章站 2022-04-10 19:42:45
...
本文主要和大家介绍JavaScript实现求最大公共子串的方法,涉及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>

相关推荐:

详解使用PHP求两个字符串最长公共子串

PHP实现求解最长公共子串思路方法

总结关于公共子串注意点

以上就是JavaScript求最大公共子串的方法详解的详细内容,更多请关注其它相关文章!