How to find the largest common substring in JavaScript

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

Examples of this article Implemented the method of finding the largest common substring in JavaScript. Share it with everyone for your reference, the details are as follows:

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.

Yes, you need to change the strategy. If the item matches, the value of the item will be set to 1 again, but its diagonal a[i-1, j-1](i > 1 && j > 1), so that only a one-dimensional array can be used. Each item of the two strings is compared, and if it matches, it is 1, if it does not match, it is 0. Then find the sequence with the longest diagonal of 1, which is the largest common substring. Looking at the separation above, 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?

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 actually not 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:

The above is what I compiled for everyone. I hope it will be helpful to everyone in the future.

Related articles:

Use Nginx in vue.js to solve cross-domain issues

Use Nginx in vue.js to solve the problem Cross-domain

How to implement asynchronous component loading in vue webpack?

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