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 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. .
<!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>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!
Javascript Data Types : Is there any difference between Browser and NodeJs?May 14, 2025 am 12:15 AMJavaScript core data types are consistent in browsers and Node.js, but are handled differently from the extra types. 1) The global object is window in the browser and global in Node.js. 2) Node.js' unique Buffer object, used to process binary data. 3) There are also differences in performance and time processing, and the code needs to be adjusted according to the environment.
JavaScript Comments: A Guide to Using // and /* */May 13, 2025 pm 03:49 PMJavaScriptusestwotypesofcomments:single-line(//)andmulti-line(//).1)Use//forquicknotesorsingle-lineexplanations.2)Use//forlongerexplanationsorcommentingoutblocksofcode.Commentsshouldexplainthe'why',notthe'what',andbeplacedabovetherelevantcodeforclari
Python vs. JavaScript: A Comparative Analysis for DevelopersMay 09, 2025 am 12:22 AMThe main difference between Python and JavaScript is the type system and application scenarios. 1. Python uses dynamic types, suitable for scientific computing and data analysis. 2. JavaScript adopts weak types and is widely used in front-end and full-stack development. The two have their own advantages in asynchronous programming and performance optimization, and should be decided according to project requirements when choosing.
Python vs. JavaScript: Choosing the Right Tool for the JobMay 08, 2025 am 12:10 AMWhether to choose Python or JavaScript depends on the project type: 1) Choose Python for data science and automation tasks; 2) Choose JavaScript for front-end and full-stack development. Python is favored for its powerful library in data processing and automation, while JavaScript is indispensable for its advantages in web interaction and full-stack development.
Python and JavaScript: Understanding the Strengths of EachMay 06, 2025 am 12:15 AMPython and JavaScript each have their own advantages, and the choice depends on project needs and personal preferences. 1. Python is easy to learn, with concise syntax, suitable for data science and back-end development, but has a slow execution speed. 2. JavaScript is everywhere in front-end development and has strong asynchronous programming capabilities. Node.js makes it suitable for full-stack development, but the syntax may be complex and error-prone.
JavaScript's Core: Is It Built on C or C ?May 05, 2025 am 12:07 AMJavaScriptisnotbuiltonCorC ;it'saninterpretedlanguagethatrunsonenginesoftenwritteninC .1)JavaScriptwasdesignedasalightweight,interpretedlanguageforwebbrowsers.2)EnginesevolvedfromsimpleinterpreterstoJITcompilers,typicallyinC ,improvingperformance.
JavaScript Applications: From Front-End to Back-EndMay 04, 2025 am 12:12 AMJavaScript can be used for front-end and back-end development. The front-end enhances the user experience through DOM operations, and the back-end handles server tasks through Node.js. 1. Front-end example: Change the content of the web page text. 2. Backend example: Create a Node.js server.
Python vs. JavaScript: Which Language Should You Learn?May 03, 2025 am 12:10 AMChoosing Python or JavaScript should be based on career development, learning curve and ecosystem: 1) Career development: Python is suitable for data science and back-end development, while JavaScript is suitable for front-end and full-stack development. 2) Learning curve: Python syntax is concise and suitable for beginners; JavaScript syntax is flexible. 3) Ecosystem: Python has rich scientific computing libraries, and JavaScript has a powerful front-end framework.
Hot AI Tools
Undresser.AI Undress
AI-powered app for creating realistic nude photos
AI Clothes Remover
Online AI tool for removing clothes from photos.
Undress AI Tool
Undress images for free
Clothoff.io
AI clothes remover
Video Face Swap
Swap faces in any video effortlessly with our completely free AI face swap tool!
Hot Article
Hot Tools
MantisBT
Mantis is an easy-to-deploy web-based defect tracking tool designed to aid in product defect tracking. It requires PHP, MySQL and a web server. Check out our demo and hosting services.
SecLists
SecLists is the ultimate security tester's companion. It is a collection of various types of lists that are frequently used during security assessments, all in one place. SecLists helps make security testing more efficient and productive by conveniently providing all the lists a security tester might need. List types include usernames, passwords, URLs, fuzzing payloads, sensitive data patterns, web shells, and more. The tester can simply pull this repository onto a new test machine and he will have access to every type of list he needs.
SublimeText3 Chinese version
Chinese version, very easy to use
EditPlus Chinese cracked version
Small size, syntax highlighting, does not support code prompt function
Atom editor mac version download
The most popular open source editor
