KMP 演算法的核心有兩個部分:部分比對表(partial match table,也常稱為 next 陣列或最長共同前後綴長度)與回退演算法。以下依序實作。
這張表的每一格記錄的是:對應位置的前綴子字串中,「同時是前綴與後綴的最長長度」。有了它,比對失敗時就知道該退回幾格,而不必從頭再來。
function kmpGetStrPartMatchValue(str) {
var prefix = [];
var suffix = [];
var partMatch = [];
for (var i = 0, j = str.length; i < j; i++) {
var newStr = str.substring(0, i + 1);
if (newStr.length == 1) {
partMatch[i] = 0;
} else {
for (var k = 0; k < i; k++) {
prefix[k] = newStr.slice(0, k + 1);
suffix[k] = newStr.slice(-k - 1);
if (prefix[k] == suffix[k]) {
partMatch[i] = prefix[k].length;
}
}
if (!partMatch[i]) {
partMatch[i] = 0;
}
}
}
prefix.length = 0;
suffix.length = 0;
return partMatch;
}
// demo
var t = "ABCDABD";
console.log(kmpGetStrPartMatchValue(t)); // [0, 0, 0, 0, 1, 2, 0]
這個版本以「枚舉所有前綴與後綴再比對」的方式求解,概念最貼近定義,也容易理解。代價是建表階段的時間複雜度偏高一點,但對於教學與一般長度的字串完全夠用。
function KMP(sourceStr, targetStr) {
var partMatchValue = kmpGetStrPartMatchValue(targetStr);
var result = false;
for (var i = 0, j = sourceStr.length; i < j; i++) {
for (var m = 0, n = targetStr.length; m < n; m++) {
if (targetStr.charAt(m) == sourceStr.charAt(i)) {
if (m == targetStr.length - 1) {
result = true;
break;
} else {
i++;
}
} else {
if (m > 0 && partMatchValue[m - 1] > 0) {
m = partMatchValue[m - 1] - 1;
} else {
break;
}
}
}
if (result) {
break;
}
}
return result;
}
var s = "BBC ABCDAB ABCDABCDABDE";
var t = "ABCDABD";
console.log(KMP(s, t)); // true
最關鍵的一行是 m = partMatchValue[m - 1] - 1。當 targetStr 的第 m 個字元與來源字串對不上時,一般的暴力比對會把 i 退回原點之後一格、m 歸零重來;而 KMP 透過查表得知「已經匹配的前 m 個字元中,前綴與後綴重疊了幾個」,於是只需把 m 退到那個重疊長度,i 完全不必後退。這正是 KMP 能把整體時間複雜度壓到 O(n + m) 的原因。
以 "ABCDABD" 為例,表格 [0,0,0,0,1,2,0] 表示:匹配到第五個字元 "ABCDA" 時,前綴 "A" 與後綴 "A" 重疊,長度為 1;匹配到 "ABCDAB" 時,重疊為 "AB",長度為 2。因此若下一個字元比對失敗,就能直接跳回 "AB" 之後繼續,省下大量重複比較。
這個實作回傳的是布林值(有沒有找到)。若需要知道出現位置,只要在 result 為 true 時回傳 i - targetStr.length + 1 即可;若要找出所有出現位置,則把找到後的狀態改為記錄位置並繼續比對。
另外別忘了,JavaScript 原生的 indexOf() 在現代引擎中已高度優化,一般情境下效能足以應付。真正需要自己實作 KMP 的場合,通常是面試題、教學,或是需要在自建的比對邏輯中插入額外規則(例如忽略某些字元、支援有限回退)的時候。理解它的價值在於那個「不回退主指標」的洞察——這也是字串比對演算法的共同起點。