「最長共同子串」是字串處理的經典題目,它要求找出同時出現在兩個字串中、且長度最長的連續片段。這與「最長共同子序列」不同——子串必須是連在一起的,不能跳字。
下面是一個直覺而完整的實作:
<!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),且空間可壓縮為一維滾動陣列。這也是面試中常被追問的延伸方向。