JavaScript求最大公共子字串的方法詳解
本文主要和大家介紹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,其公共字子字串一定是<= 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='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中文網其他相關文章!

熱AI工具

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

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

Undress AI Tool
免費脫衣圖片

Clothoff.io
AI脫衣器

Video Face Swap
使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱門文章

熱工具

記事本++7.3.1
好用且免費的程式碼編輯器

SublimeText3漢化版
中文版,非常好用

禪工作室 13.0.1
強大的PHP整合開發環境

Dreamweaver CS6
視覺化網頁開發工具

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

而後悔莫及、人們常常會因為一些原因不小心刪除某些聯絡人、微信作為一款廣泛使用的社群軟體。幫助用戶解決這個問題,本文將介紹如何透過簡單的方法找回被刪除的聯絡人。 1.了解微信聯絡人刪除機制這為我們找回被刪除的聯絡人提供了可能性、微信中的聯絡人刪除機制是將其從通訊錄中移除,但並未完全刪除。 2.使用微信內建「通訊錄恢復」功能微信提供了「通訊錄恢復」節省時間和精力,使用者可以透過此功能快速找回先前刪除的聯絡人,功能。 3.進入微信設定頁面點選右下角,開啟微信應用程式「我」再點選右上角設定圖示、進入設定頁面,,

七彩虹主機板在中國國內市場享有較高的知名度和市場佔有率,但是有些七彩虹主機板的用戶還不清楚怎麼進入bios進行設定呢?針對這一情況,小編專門為大家帶來了兩種進入七彩虹主機板bios的方法,快來試試吧!方法一:使用u盤啟動快捷鍵直接進入u盤裝系統七彩虹主機板一鍵啟動u盤的快捷鍵是ESC或F11,首先使用黑鯊裝機大師製作一個黑鯊U盤啟動盤,然後開啟電腦,當看到開機畫面的時候,連續按下鍵盤上的ESC或F11鍵以後將會進入到一個啟動項順序選擇的窗口,將遊標移到顯示“USB”的地方,然

番茄小說是一款非常熱門的小說閱讀軟體,我們在番茄小說中經常會有新的小說和漫畫可以去閱讀,每一本小說和漫畫都很有意思,很多小伙伴也想著要去寫小說來賺取賺取零用錢,在把自己想要寫的小說內容編輯成文字,那麼我們要怎麼樣在這裡面去寫小說呢?小伙伴們都不知道,那就讓我們一起到本站本站中花點時間來看寫小說的方法介紹。分享番茄小說寫小說方法教學 1、先在手機上打開番茄免費小說app,點擊個人中心——作家中心 2、跳到番茄作家助手頁面——點擊創建新書在小說的結

手機遊戲成為了人們生活中不可或缺的一部分,隨著科技的發展。它以其可愛的龍蛋形象和有趣的孵化過程吸引了眾多玩家的關注,而其中一款備受矚目的遊戲就是手機版龍蛋。幫助玩家們在遊戲中更好地培養和成長自己的小龍,本文將向大家介紹手機版龍蛋的孵化方法。 1.選擇合適的龍蛋種類玩家需要仔細選擇自己喜歡並且適合自己的龍蛋種類,根據遊戲中提供的不同種類的龍蛋屬性和能力。 2.提升孵化機的等級玩家需要透過完成任務和收集道具來提升孵化機的等級,孵化機的等級決定了孵化速度和孵化成功率。 3.收集孵化所需的資源玩家需要在遊戲中

人臉偵測辨識技術已經是一個比較成熟且應用廣泛的技術。而目前最廣泛的網路應用語言非JS莫屬,在Web前端實現人臉偵測辨識相比後端的人臉辨識有優勢也有弱勢。優點包括減少網路互動、即時識別,大大縮短了使用者等待時間,提高了使用者體驗;弱勢是:受到模型大小限制,其中準確率也有限。如何在web端使用js實現人臉偵測呢?為了實現Web端人臉識別,需要熟悉相關的程式語言和技術,如JavaScript、HTML、CSS、WebRTC等。同時也需要掌握相關的電腦視覺和人工智慧技術。值得注意的是,由於Web端的計

Oracle版本查詢方法詳解Oracle是目前世界上最受歡迎的關聯式資料庫管理系統之一,它提供了豐富的功能和強大的效能,廣泛應用於企業。在進行資料庫管理和開發過程中,了解Oracle資料庫的版本是非常重要的。本文將詳細介紹如何查詢Oracle資料庫的版本信息,並給出具體的程式碼範例。查詢資料庫版本的SQL語句在Oracle資料庫中,可以透過執行簡單的SQL語句

Win11管理員權限取得方法匯總在Windows11作業系統中,管理員權限是非常重要的權限之一,可以讓使用者對系統進行各種操作。有時候,我們可能需要取得管理員權限來完成一些操作,例如安裝軟體、修改系統設定等。下面就為大家總結了一些取得Win11管理員權限的方法,希望能幫助大家。 1.使用快捷鍵在Windows11系統中,可以透過快捷鍵的方式快速開啟命令提

字體大小的設定成為了重要的個人化需求,隨著手機成為人們日常生活的重要工具。以滿足不同使用者的需求、本文將介紹如何透過簡單的操作,提升手機使用體驗,調整手機字體大小。為什麼需要調整手機字體大小-調整字體大小可以使文字更清晰易讀-適合不同年齡段用戶的閱讀需求-方便視力不佳的用戶使用手機系統自帶字體大小設置功能-如何進入系統設置界面-在在設定介面中找到並進入"顯示"選項-找到"字體大小"選項並進行調整第三方應用調整字體大小-下載並安裝支援字體大小調整的應用程式-開啟應用程式並進入相關設定介面-根據個人
