在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，其公共字子字串一定是

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 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實現跨平台開發，提高開發效率。