在JavaScript中如何实现求最大公共子串-js教程-PHP中文网

首页

web前端

js教程

在JavaScript中如何实现求最大公共子串

亚连

Jun 08, 2018 am 10:37 AM

javascript

这篇文章主要介绍了JavaScript实现求最大公共子串的方法,涉及javascript针对字符串的遍历、匹配、运算等相关操作技巧,需要的朋友可以参考下

本文实例讲述了JavaScript实现求最大公共子串的方法。分享给大家供大家参考，具体如下：

求最大公共子串，常见的做法是使用矩阵。假设有字符串：abcdefg和字符串abcd，则可构成如下表所示矩阵。

可以，需要改变一下策略，如果该项匹配，则该项的值为再设为1，而是其对角线a[i-1, j-1](i > 1 && j > 1)的值+1，这样便可以只使用一个一维数组。对两个字符串的每一项都进行比较，若匹配则该项为1，不匹配则为0。然后求出对角线最长为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=&#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>

上面是我整理给大家的，希望今后会对大家有帮助。

在vue.js中使用Nginx来解决跨域

在vue+webpack中如何实现异步组件加载？

以上是在JavaScript中如何实现求最大公共子串的详细内容。更多信息请关注PHP中文网其他相关文章！

声明

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn

Python vs. JavaScript：学习曲线和易用性Apr 16, 2025 am 12:12 AM

Python更适合初学者，学习曲线平缓，语法简洁；JavaScript适合前端开发，学习曲线较陡，语法灵活。1.Python语法直观，适用于数据科学和后端开发。2.JavaScript灵活，广泛用于前端和服务器端编程。

Python vs. JavaScript：社区，图书馆和资源Apr 15, 2025 am 12:16 AM

Python和JavaScript在社区、库和资源方面的对比各有优劣。1)Python社区友好，适合初学者，但前端开发资源不如JavaScript丰富。2)Python在数据科学和机器学习库方面强大，JavaScript则在前端开发库和框架上更胜一筹。3)两者的学习资源都丰富，但Python适合从官方文档开始，JavaScript则以MDNWebDocs为佳。选择应基于项目需求和个人兴趣。

从C/C到JavaScript：所有工作方式Apr 14, 2025 am 12:05 AM

从C/C 转向JavaScript需要适应动态类型、垃圾回收和异步编程等特点。1）C/C 是静态类型语言，需手动管理内存，而JavaScript是动态类型，垃圾回收自动处理。2）C/C 需编译成机器码，JavaScript则为解释型语言。3）JavaScript引入闭包、原型链和Promise等概念，增强了灵活性和异步编程能力。

JavaScript引擎：比较实施Apr 13, 2025 am 12:05 AM

不同JavaScript引擎在解析和执行JavaScript代码时，效果会有所不同，因为每个引擎的实现原理和优化策略各有差异。1.词法分析：将源码转换为词法单元。2.语法分析：生成抽象语法树。3.优化和编译：通过JIT编译器生成机器码。4.执行：运行机器码。V8引擎通过即时编译和隐藏类优化，SpiderMonkey使用类型推断系统，导致在相同代码上的性能表现不同。

超越浏览器：现实世界中的JavaScriptApr 12, 2025 am 12:06 AM

JavaScript在现实世界中的应用包括服务器端编程、移动应用开发和物联网控制：1.通过Node.js实现服务器端编程，适用于高并发请求处理。2.通过ReactNative进行移动应用开发，支持跨平台部署。3.通过Johnny-Five库用于物联网设备控制，适用于硬件交互。

使用Next.js（后端集成）构建多租户SaaS应用程序Apr 11, 2025 am 08:23 AM

我使用您的日常技术工具构建了功能性的多租户SaaS应用程序（一个Edtech应用程序），您可以做同样的事情。首先，什么是多租户SaaS应用程序？多租户SaaS应用程序可让您从唱歌中为多个客户提供服务

如何使用Next.js（前端集成）构建多租户SaaS应用程序Apr 11, 2025 am 08:22 AM

本文展示了与许可证确保的后端的前端集成，并使用Next.js构建功能性Edtech SaaS应用程序。前端获取用户权限以控制UI的可见性并确保API要求遵守角色库

JavaScript：探索网络语言的多功能性Apr 11, 2025 am 12:01 AM

JavaScript是现代Web开发的核心语言，因其多样性和灵活性而广泛应用。1)前端开发：通过DOM操作和现代框架（如React、Vue.js、Angular）构建动态网页和单页面应用。2)服务器端开发：Node.js利用非阻塞I/O模型处理高并发和实时应用。3)移动和桌面应用开发：通过ReactNative和Electron实现跨平台开发，提高开发效率。

See all articles