Home > Article > Web Front-end > Detailed explanation of how to find the largest common substring in JavaScript

Detailed explanation of how to find the largest common substring in JavaScript

小云云Original: 2018-02-05 09:44:031715browse

This article mainly introduces to you the method of finding the largest common substring in JavaScript, involving JavaScript's traversal, matching, operation and other related operation skills for strings. Friends who need it can refer to it. I hope it can help you.

To find the largest common substring, a common method is to use a matrix. Assuming that there are strings: abcdefg and string abcd, a matrix can be formed as shown in the following table.

##abcdefga1000 000b0100000c 0010000d0001000

#Compare each item of the two strings. If they match, the item is 1, if not, it is 0. Then find the sequence with the longest diagonal of 1, which is the largest common substring. Looking at the above separation, it seems that we have to use a two-dimensional array. This is not very cost-effective when both strings are large. Can it be further optimized?

Yes, you need to change the strategy. If the item matches, the value of the item is set to 1 again, but its diagonal

a[i-1, j-1](i > 1 && j > 1) +1, so that only a one-dimensional array can be used.

Use one string as the "row" and the other as the "column", compare the values of each item of the two strings, and use another variable to record the maximum value of the array and the starting position of the string. The code is as follows:

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);
}

But the code is not actually optimal, why? Because the above writing method must wait for both layers of loops to complete. Is there a relatively faster method?

Suppose strings a and b have lengths of len1 and len2 respectively. Their common substrings must be <= Math.min(len1, len2), and the substrings must be continuous and must be Substrings of a and 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 "";
}

First compare the lengths of s1 and s2, and then take the shorter string.

substr(idex, len), so take the shorter string and take its substring, and then determine whether it exists in the longer string. If it exists, return it directly, otherwise take the next digit. .

Complete example:

<!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=&#39;text/css&#39;>
 body {background-color:#fff;}
 </style>
 </head>
 <body>
<script type=&#39;text/javascript&#39;>
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>

Related recommendations:

Detailed explanation of using PHP to find the longest common substring of two strings

PHP implementation of the idea of finding the longest common substring

Summary of the points to note about common substrings

The above is the detailed content of Detailed explanation of how to find the largest common substring in JavaScript. For more information, please follow other related articles on the PHP Chinese website!

Statement：

The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Previous article：Detailed explanation of JavaScript mediator pattern examplesNext article：Detailed explanation of JavaScript mediator pattern examples

See more

Detailed explanation of how to find the largest common substring in JavaScript

Related articles