DIV CSS 佈局教程網

用 JavaScript 找出兩個字串的最長共同子串:函數實作與邏輯拆解
編輯:關於JavaScript     

「最長共同子串」是字串處理的經典題目,它要求找出同時出現在兩個字串中、且長度最長的連續片段。這與「最長共同子序列」不同——子串必須是連在一起的,不能跳字。

下面是一個直覺而完整的實作:

 <!DOCTYPE html>
<html>
<head>
<title></title>
</head>
<script type="text/javascript">
function search(str1, str2) {
  var i, j, k, a, jk, kk;
  var m = str1.length;
  var n = str2.length;
  var index = 0;
  var maxlen = 0;
  var str = "";
  var flag = 0;

  for (i = 0; i < n; i++) {
    k = i;
    for (j = 0; j < m; j++) {
      a = 0;
      flag = 0;
      jk = j;
      kk = k;
      while (jk <= m && str1[kk] == str2[jk]) {
        kk++;
        jk++;
        a++;
        flag = 1;
      }
      if (flag == 1) {
        if (a > maxlen) {
          maxlen = a;
          index = jk - a; // 匹配的首項位置
        }
      }
    }
  }

  for (; maxlen > 0; maxlen--) {
    str += str2[index++];
  }
  return str;
}

alert(search("kssd", "ssdfa"));
</script>
<body>
<div>11</div>
</body>
</html>

邏輯拆解

這個解法的核心是三層迴圈。i 遍歷第二個字串的每個起點,j 遍歷第一個字串的每個起點,最內層的 while 則從這兩個起點開始同步往後比對,直到字元不同或其中一個字串走完為止。比對成功的長度記在 a,若大於目前記錄的 maxlen 就更新,並用 index = jk - a 回推這段共同子串在第二個字串中的起始位置。

最後一個迴圈依 maxlen 從 index 開始逐字拼接,組出結果字串。

以 search("kssd", "ssdfa") 為例,兩者共同的最長連續片段是 "ss"。

可以再改進的地方

這個版本勝在直白好懂,但有幾處值得優化。

首先是邊界條件:外層 while 只檢查 jk <= m,卻沒檢查 kk 是否已超出 str1 的長度。當 str2 比 str1 長且起點靠後時,str1[kk] 會得到 undefined,比對結果不可預期。嚴謹的寫法應該是 while (jk < m && kk < n && str1[kk] === str2[jk])。

其次是比較運算子建議改用 === 而非 ==,避免型別轉換帶來的意外。

最後是效能。暴力解法的時間複雜度是 O(m×n×min(m,n)),字串很長時會明顯變慢。若資料量可觀,可以改用動態規劃,用二維表格記錄「以 i、j 結尾的共同子串長度」,轉移方程式為:dp[i][j] = str1[i-1] === str2[j-1] ? dp[i-1][j-1] + 1 : 0,時間複雜度降為 O(m×n),且空間可壓縮為一維滾動陣列。這也是面試中常被追問的延伸方向。

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