求兩個字串的最長共同子串(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
這份實作的策略是「從長到短暴力枚舉」:
程式碼中 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)。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 變數保存左上角的值,避免二維表格的空間消耗。若你更重視可讀性,直接用二維陣列寫也不成問題,對於一般長度的字串效能差異有限。