Web Front-endJS TutorialDetailed explanation of how to find the largest common substring in JavaScriptDetailed explanation of how to find the largest common substring in JavaScript
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.
| b | c | d | e | f | g | ||
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 | |
| 0 | 0 | 1 | 0 | 0 | 0 | 0 | |
| 0 | 0 | 0 | 1 | 0 | 0 | 0 |
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 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>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!
Python vs. JavaScript: Community, Libraries, and ResourcesApr 15, 2025 am 12:16 AMPython and JavaScript have their own advantages and disadvantages in terms of community, libraries and resources. 1) The Python community is friendly and suitable for beginners, but the front-end development resources are not as rich as JavaScript. 2) Python is powerful in data science and machine learning libraries, while JavaScript is better in front-end development libraries and frameworks. 3) Both have rich learning resources, but Python is suitable for starting with official documents, while JavaScript is better with MDNWebDocs. The choice should be based on project needs and personal interests.
From C/C to JavaScript: How It All WorksApr 14, 2025 am 12:05 AMThe shift from C/C to JavaScript requires adapting to dynamic typing, garbage collection and asynchronous programming. 1) C/C is a statically typed language that requires manual memory management, while JavaScript is dynamically typed and garbage collection is automatically processed. 2) C/C needs to be compiled into machine code, while JavaScript is an interpreted language. 3) JavaScript introduces concepts such as closures, prototype chains and Promise, which enhances flexibility and asynchronous programming capabilities.
JavaScript Engines: Comparing ImplementationsApr 13, 2025 am 12:05 AMDifferent JavaScript engines have different effects when parsing and executing JavaScript code, because the implementation principles and optimization strategies of each engine differ. 1. Lexical analysis: convert source code into lexical unit. 2. Grammar analysis: Generate an abstract syntax tree. 3. Optimization and compilation: Generate machine code through the JIT compiler. 4. Execute: Run the machine code. V8 engine optimizes through instant compilation and hidden class, SpiderMonkey uses a type inference system, resulting in different performance performance on the same code.
Beyond the Browser: JavaScript in the Real WorldApr 12, 2025 am 12:06 AMJavaScript's applications in the real world include server-side programming, mobile application development and Internet of Things control: 1. Server-side programming is realized through Node.js, suitable for high concurrent request processing. 2. Mobile application development is carried out through ReactNative and supports cross-platform deployment. 3. Used for IoT device control through Johnny-Five library, suitable for hardware interaction.
Building a Multi-Tenant SaaS Application with Next.js (Backend Integration)Apr 11, 2025 am 08:23 AMI built a functional multi-tenant SaaS application (an EdTech app) with your everyday tech tool and you can do the same. First, what’s a multi-tenant SaaS application? Multi-tenant SaaS applications let you serve multiple customers from a sing
How to Build a Multi-Tenant SaaS Application with Next.js (Frontend Integration)Apr 11, 2025 am 08:22 AMThis article demonstrates frontend integration with a backend secured by Permit, building a functional EdTech SaaS application using Next.js. The frontend fetches user permissions to control UI visibility and ensures API requests adhere to role-base
JavaScript: Exploring the Versatility of a Web LanguageApr 11, 2025 am 12:01 AMJavaScript is the core language of modern web development and is widely used for its diversity and flexibility. 1) Front-end development: build dynamic web pages and single-page applications through DOM operations and modern frameworks (such as React, Vue.js, Angular). 2) Server-side development: Node.js uses a non-blocking I/O model to handle high concurrency and real-time applications. 3) Mobile and desktop application development: cross-platform development is realized through ReactNative and Electron to improve development efficiency.
The Evolution of JavaScript: Current Trends and Future ProspectsApr 10, 2025 am 09:33 AMThe latest trends in JavaScript include the rise of TypeScript, the popularity of modern frameworks and libraries, and the application of WebAssembly. Future prospects cover more powerful type systems, the development of server-side JavaScript, the expansion of artificial intelligence and machine learning, and the potential of IoT and edge computing.
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
AI Hentai Generator
Generate AI Hentai for free.
Hot Article
Hot Tools
Zend Studio 13.0.1
Powerful PHP integrated development environment
DVWA
Damn Vulnerable Web App (DVWA) is a PHP/MySQL web application that is very vulnerable. Its main goals are to be an aid for security professionals to test their skills and tools in a legal environment, to help web developers better understand the process of securing web applications, and to help teachers/students teach/learn in a classroom environment Web application security. The goal of DVWA is to practice some of the most common web vulnerabilities through a simple and straightforward interface, with varying degrees of difficulty. Please note that this software
EditPlus Chinese cracked version
Small size, syntax highlighting, does not support code prompt function
SublimeText3 Mac version
God-level code editing software (SublimeText3)
Safe Exam Browser
Safe Exam Browser is a secure browser environment for taking online exams securely. This software turns any computer into a secure workstation. It controls access to any utility and prevents students from using unauthorized resources.
