DIV CSS 佈局教程網

自製 JS 函式求兩字串的最長共同子串
編輯:關於JavaScript     

求兩個字串的最長共同子串(Longest Common Substring)是字串處理的經典題目。以下用一個自製函式實作,思路直覺且易於理解。

實作

// 查找兩個字串的最長共同子串
function findSubStr(s1, s2){
  var S = sstr = "", L1 = s1.length, L2 = s2.length;
  if (L1 > L2){
    var s3 = s1; s1 = s2; s2 = s3; L1 = s2.length;
  }
  for (var j = L1; j > 0; j--)
    for (var i = 0; i <= L1 - j; i++){
      sstr = s1.substr(i, j);
      if (s2.indexOf(sstr) >= 0) return sstr;
    }
  return "";
}

document.writeln(findSubStr("aaa3333", "baa333cc"));              // aa333
document.writeln(findSubStr("aaaX3333--", "baa333ccX3333333x"));  // X3333

思路解析

這份實作的策略是「從長到短暴力枚舉」:

  1. 先讓 s1 是較短的那個字串,減少外層迴圈的次數。
  2. 外層 j 從最大可能長度遞減,代表正在嘗試的子串長度。
  3. 內層 i 滑動起點,取出每個長度為 j 的子串。
  4. 用 indexOf 檢查該子串是否存在於 s2;一旦找到,因為 j 是由大到小,第一個命中就必定最長,直接回傳。

程式碼中 swap 那段有個小瑕疵:L1 = s2.length 在交換之後才取值,此時 s2 已是原本較長的字串,因此 L1 反而變大,並未真正達到縮短迴圈的目的。正確應寫成 L1 = s1.length。

複雜度與更好的做法

這個暴力解法的時間複雜度約為 O(m × n × min(m,n)),字串稍長就會明顯變慢。若要處理大量資料,可考慮:

  • 動態規劃:建立二維表格,dp[i][j] 表示以 s1 第 i 字元與 s2 第 j 字元結尾的共同子串長度,時間複雜度降為 O(m × n)。若只需長度不需內容,還能用一維滾動陣列把空間壓到 O(n)。
  • 字尾陣列(Suffix Array):把兩字串拼接後建字尾陣列與 LCP 陣列,可在 O(n log n) 內求解,適合超大規模資料。
  • 呼叫內建方法:ES6 以後 includes() 語意比 indexOf() >= 0 更清楚,效果相同。

動態規劃版本參考

function longestCommonSubstr(a, b){
  var m = a.length, n = b.length, max = 0, end = 0;
  var dp = new Array(n + 1).fill(0);
  for (var i = 1; i <= m; i++){
    var prev = 0;
    for (var j = 1; j <= n; j++){
      var temp = dp[j];
      if (a[i - 1] === b[j - 1]) {
        dp[j] = prev + 1;
        if (dp[j] > max) { max = dp[j]; end = i; }
      } else {
        dp[j] = 0;
      }
      prev = temp;
    }
  }
  return a.slice(end - max, end);
}

console.log(longestCommonSubstr("aaaX3333--", "baa333ccX3333333x")); // X3333

這裡刻意用一維陣列搭配 prev 變數保存左上角的值,避免二維表格的空間消耗。若你更重視可讀性,直接用二維陣列寫也不成問題,對於一般長度的字串效能差異有限。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved