本文主要和大家介紹JavaScript實現求最大公共子字串的方法,涉及javascript針對字符串的遍歷、匹配、運算等相關操作技巧,需要的朋友可以參考下,希望能幫助到大家。
求最大公共子字串,常見的做法是使用矩陣。假設有字串:abcdefg和字串abcd,則可構成如下表所示矩陣。
a | b | c | ##de | f | g | ||
#1 | ##0 | ##00 | 0 | 0 | 0 | #b | |
1 | 0 | 0 | 0 | 0 | #0 | ##c | |
0 | 1 | 0 | 0 | 0 | 0 | #d | |
0 | 0 | #1 | 0 | ##00 | 將兩個字串的每一項都進行比較,若符合則該項為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,其公共字子字串一定是
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='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>
相關推薦:
詳解使用PHP求兩個字串最長公用子字串
以上是JavaScript求最大公共子字串的方法詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章!

去掉重复并排序的方法:1、使用“Array.from(new Set(arr))”或者“[…new Set(arr)]”语句,去掉数组中的重复元素,返回去重后的新数组;2、利用sort()对去重数组进行排序,语法“去重数组.sort()”。

本篇文章给大家带来了关于JavaScript的相关知识,其中主要介绍了关于Symbol类型、隐藏属性及全局注册表的相关问题,包括了Symbol类型的描述、Symbol不会隐式转字符串等问题,下面一起来看一下,希望对大家有帮助。

怎么制作文字轮播与图片轮播?大家第一想到的是不是利用js,其实利用纯CSS也能实现文字轮播与图片轮播,下面来看看实现方法,希望对大家有所帮助!

本篇文章给大家带来了关于JavaScript的相关知识,其中主要介绍了关于对象的构造函数和new操作符,构造函数是所有对象的成员方法中,最早被调用的那个,下面一起来看一下吧,希望对大家有帮助。

本篇文章给大家带来了关于JavaScript的相关知识,其中主要介绍了关于面向对象的相关问题,包括了属性描述符、数据描述符、存取描述符等等内容,下面一起来看一下,希望对大家有帮助。

方法:1、利用“点击元素对象.unbind("click");”方法,该方法可以移除被选元素的事件处理程序;2、利用“点击元素对象.off("click");”方法,该方法可以移除通过on()方法添加的事件处理程序。

本篇文章给大家带来了关于JavaScript的相关知识,其中主要介绍了关于BOM操作的相关问题,包括了window对象的常见事件、JavaScript执行机制等等相关内容,下面一起来看一下,希望对大家有帮助。

foreach不是es6的方法。foreach是es3中一个遍历数组的方法,可以调用数组的每个元素,并将元素传给回调函数进行处理,语法“array.forEach(function(当前元素,索引,数组){...})”;该方法不处理空数组。


熱AI工具

Undresser.AI Undress
人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover
用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool
免費脫衣圖片

Clothoff.io
AI脫衣器

AI Hentai Generator
免費產生 AI 無盡。

熱門文章

熱工具

DVWA
Damn Vulnerable Web App (DVWA) 是一個PHP/MySQL的Web應用程序,非常容易受到攻擊。它的主要目標是成為安全專業人員在合法環境中測試自己的技能和工具的輔助工具,幫助Web開發人員更好地理解保護網路應用程式的過程,並幫助教師/學生在課堂環境中教授/學習Web應用程式安全性。 DVWA的目標是透過簡單直接的介面練習一些最常見的Web漏洞,難度各不相同。請注意,該軟體中

PhpStorm Mac 版本
最新(2018.2.1 )專業的PHP整合開發工具

SublimeText3 Mac版
神級程式碼編輯軟體(SublimeText3)

MinGW - Minimalist GNU for Windows
這個專案正在遷移到osdn.net/projects/mingw的過程中,你可以繼續在那裡關注我們。 MinGW:GNU編譯器集合(GCC)的本機Windows移植版本,可自由分發的導入函式庫和用於建置本機Windows應用程式的頭檔;包括對MSVC執行時間的擴展,以支援C99功能。 MinGW的所有軟體都可以在64位元Windows平台上運作。

ZendStudio 13.5.1 Mac
強大的PHP整合開發環境