JavaScript求最大公共子串的方法详解-js教程-PHP中文网

首页

web前端

js教程

JavaScript求最大公共子串的方法详解

小云云

Feb 05, 2018 am 09:44 AM

javascript js 方法

本文主要和大家介绍JavaScript实现求最大公共子串的方法,涉及javascript针对字符串的遍历、匹配、运算等相关操作技巧,需要的朋友可以参考下，希望能帮助到大家。

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

	a	b	c	d	e	f	g
a	1	0	0	0	0	0	0
b	0	1	0	0	0	0	0
c	0	0	1	0	0	0	0
d	0	0	0	1	0	0	0

对两个字符串的每一项都进行比较，若匹配则该项为1，不匹配则为0。然后求出对角线最长为1的那一段序列，即为最大公共子串。看上面的分开，似乎得使用二维数组了，在两个字符串都较大的情况下不是很划算，是否可以进一步优化？

可以，需要改变一下策略，如果该项匹配，则该项的值为再设为1，而是其对角线a[i-1, j-1](i > 1 && j > 1)的值+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>

登录后复制

热AI工具

热工具

热门话题

gmail邮箱登陆入口在哪里

7700

Java教程

1640

CakePHP 教程

1393

Laravel 教程

1287

PHP教程

1230

显示更多

Related knowledge

怎么在番茄免费小说app中写小说分享番茄小说写小说方法教程 Mar 28, 2024 pm 12:50 PM

　　番茄小说是一款非常热门的小说阅读软件，我们在番茄小说中经常会有新的小说和漫画可以去阅读，每一本小说和漫画都很有意思，很多小伙伴也想着要去写小说来赚取赚取零花钱，在把自己想要写的小说内容编辑成文字，那么我们要怎么样在这里面去写小说呢?小伙伴们都不知道，那就让我们一起到本站本站中花点时间来看写小说的方法介绍吧。分享番茄小说写小说方法教程　　1、首先在手机上打开番茄免费小说app，点击个人中心——作家中心　　2、跳转到番茄作家助手页面——点击创建新书在小说的结

七彩虹主板怎么进入bios？教你两种方法 Mar 13, 2024 pm 06:01 PM

　　七彩虹主板在中国国内市场享有较高的知名度和市场占有率，但是有些七彩虹主板的用户还不清楚怎么进入bios进行设置呢？针对这一情况，小编专门为大家带来了两种进入七彩虹主板bios的方法，快来试试吧！　　方法一：使用u盘启动快捷键直接进入u盘装系统　　七彩虹主板一键启动u盘的快捷键是ESC或F11，首先使用黑鲨装机大师制作一个黑鲨U盘启动盘，然后开启电脑，当看到开机画面的时候，连续按下键盘上的ESC或F11键以后将会进入到一个启动项顺序选择的窗口，将光标移动到显示“USB”的地方，然

微信删除的人如何找回（简单教程告诉你如何恢复被删除的联系人） May 01, 2024 pm 12:01 PM

而后悔莫及、人们常常会因为一些原因不小心将某些联系人删除、微信作为一款广泛使用的社交软件。帮助用户解决这一问题，本文将介绍如何通过简单的方法找回被删除的联系人。1.了解微信联系人删除机制这为我们找回被删除的联系人提供了可能性、微信中的联系人删除机制是将其从通讯录中移除，但并未完全删除。2.使用微信内置“通讯录恢复”功能微信提供了“通讯录恢复”节省时间和精力，用户可以通过该功能快速找回之前被删除的联系人，功能。3.进入微信设置页面点击右下角，打开微信应用“我”再点击右上角设置图标、进入设置页面，，

手机字体大小设置方法（轻松调整手机字体大小） May 07, 2024 pm 03:34 PM

字体大小的设置成为了一项重要的个性化需求，随着手机成为人们日常生活的重要工具。以满足不同用户的需求、本文将介绍如何通过简单的操作，提升手机使用体验，调整手机字体大小。为什么需要调整手机字体大小-调整字体大小可以使文字更清晰易读-适合不同年龄段用户的阅读需求-方便视力不佳的用户使用手机系统自带字体大小设置功能-如何进入系统设置界面-在设置界面中找到并进入"显示"选项-找到"字体大小"选项并进行调整第三方应用调整字体大小-下载并安装支持字体大小调整的应用程序-打开应用程序并进入相关设置界面-根据个人

Win11管理员权限获取方法汇总 Mar 09, 2024 am 08:45 AM

Win11管理员权限获取方法汇总在Windows11操作系统中，管理员权限是非常重要的权限之一，可以让用户对系统进行各种操作。有时候，我们可能需要获取管理员权限来完成一些操作，比如安装软件、修改系统设置等。下面就为大家总结了一些获取Win11管理员权限的方法，希望能帮助到大家。1.使用快捷键在Windows11系统中，可以通过快捷键的方式快速打开命令提

手机版龙蛋孵化方法大揭秘（一步一步教你如何成功孵化手机版龙蛋） May 04, 2024 pm 06:01 PM

手机游戏成为了人们生活中不可或缺的一部分，随着科技的发展。它以其可爱的龙蛋形象和有趣的孵化过程吸引了众多玩家的关注，而其中一款备受瞩目的游戏就是手机版龙蛋。帮助玩家们在游戏中更好地培养和成长自己的小龙，本文将向大家介绍手机版龙蛋的孵化方法。1.选择合适的龙蛋种类玩家需要仔细选择自己喜欢并且适合自己的龙蛋种类，根据游戏中提供的不同种类的龙蛋属性和能力。2.提升孵化机的等级玩家需要通过完成任务和收集道具来提升孵化机的等级，孵化机的等级决定了孵化速度和孵化成功率。3.收集孵化所需的资源玩家需要在游戏中

Oracle版本查询方法详解 Mar 07, 2024 pm 09:21 PM

Oracle版本查询方法详解Oracle是目前世界上最流行的关系型数据库管理系统之一，它提供了丰富的功能和强大的性能，广泛应用于企业中。在进行数据库管理和开发过程中，了解Oracle数据库的版本是非常重要的。本文将详细介绍如何查询Oracle数据库的版本信息，并给出具体的代码示例。查询数据库版本的SQL语句在Oracle数据库中，可以通过执行简单的SQL语句

推荐：优秀JS开源人脸检测识别项目 Apr 03, 2024 am 11:55 AM

人脸检测识别技术已经是一个比较成熟且应用广泛的技术。而目前最为广泛的互联网应用语言非JS莫属，在Web前端实现人脸检测识别相比后端的人脸识别有优势也有弱势。优势包括减少网络交互、实时识别，大大缩短了用户等待时间，提高了用户体验；弱势是：受到模型大小限制，其中准确率也有限。如何在web端使用js实现人脸检测呢？为了实现Web端人脸识别，需要熟悉相关的编程语言和技术，如JavaScript、HTML、CSS、WebRTC等。同时还需要掌握相关的计算机视觉和人工智能技术。值得注意的是，由于Web端的计

See all articles

JavaScript求最大公共子串的方法详解

热AI工具

Undresser.AI Undress

AI Clothes Remover

Undress AI Tool

Clothoff.io

Video Face Swap

热门文章

热工具

记事本++7.3.1

SublimeText3汉化版

禅工作室 13.0.1

Dreamweaver CS6

SublimeText3 Mac版

热门话题