上一篇講的 BF 算法勝在直白,弱點也同樣直白:失配就回退,已比較過的信息全部作廢。KMP 正是針對這一點而生的優化方案。本文用「已匹配信息能否再利用」這條主線,把 KMP 的核心——部分匹配表(next 數組)——一步步推導出來,並給出兩種 JavaScript 實現。
KMP 與 BM 是兩大經典算法,分別代表前綴匹配與後綴匹配。二者的區別只在比較順序:
顯然 BF 屬於前綴匹配。KMP 是它的優化版本,名字取自三位作者 Knuth、Morris、Pratt 的姓氏首字母。

對比 BF 與 KMP 的移動距離可以發現:在文本串 T 中匹配模式串 P,當比較到第 6 個字符 c 時失配,BF 的做法是把整個模式串右移一位,KMP 則移動了兩位。
為什麼是兩位,而不是一位或三位?關鍵信息在於:模式串 P 的 ababa 這一段是匹配成功的。KMP 的核心思想就是——不要丟棄這段成功信息,不要把主串指針移回已經比較過的位置,而是利用它算出下一個合理的起點。
KMP 的作者們給出了公式:
移動位數 = 已匹配的字符數 − 對應的部分匹配值
要特別注意:這個偏移量只與模式串(子串)有關,與文本串完全無關。這意味著部分匹配表可以預先算好、反覆使用。
T : abababaabab P : ababacb
模式串中前綴 ababa 匹配成功,到 c 處失配,因此已匹配字符數為 5。這一步很直觀。
這是最難理解的部分。先看一個例子:
T:aaronaabbcc P:aaronaac
如果在匹配到 c 時出錯,按上一段的結構來看,模式串應該往哪裡移最合理?
aaronaabbcc
aaronaac
也就是說:如果模式串內部某段字符「頭尾相同」,那麼移動時就可以跳過這一段。這個思路顯然是合理的,因為頭尾相同意味著移動後這些字符仍然能對上。
要把上面的直覺變成可計算的規則,需要兩個概念:
部分匹配值 = 前綴與後綴的最長共有元素的長度。
以 aaronaac 為例,BF 的移動劃分是 a, aa, aar, aaro, aaron, aarona, aaronaa, aaronaac,而 KMP 需要為每一個已匹配字符計算前綴與後綴的最長共有長度,最終得到部分匹配表:
a a r o n a a c [0, 1, 0, 0, 0, 1, 2, 0]
把每一位的計算過程列出來,規律就一目了然(p 表示前綴集合,n 表示後綴集合,r 表示結果):
a p=>[] n=>[] r = 0 aa p=>[a] n=>[a] r = 1 aar p=>[a, aa] n=>[r, ar] r = 0 aaro p=>[a, aa, aar] n=>[o, ro, aro] r = 0 aaron p=>[a, aa, aar, aaro] n=>[n, on, ron, aron] r = 0 aarona p=>[a, aa, aar, aaro, aaron] n=>[a, na, ona, rona, arona] r = 1 aaronaa p=>[..., aarona] n=>[a, aa, naa, onaa, ronaa, ...] r = 2 aaronaac p=>[..., aaronaa] n=>[c, ac, aac, naac, ...] r = 0
可以看到 aa 的前後綴都是 a,長度 1;aaronaa 的最長共有元素是 aa,長度 2;其餘位置沒有共有元素,記為 0。
KMP 與 BF 最大的差別就在這張表——沒有表就是 BF,加上表就是 KMP。
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;
}
}
return partMatch;
}
回退環節幾乎可以照搬 BF,唯一要改的是:BF 失配時主串指針 i 直接回退一位,KMP 則依據匹配表算出應該移動的距離。
// 子循環核心片段
for (var j = 0; j < searchLength; j++) {
if (searchStr.charAt(j) == sourceStr.charAt(i)) {
if (j == searchLength - 1) { result = i - j; break; } // 匹配完成
else { i++; } // 主串指針前進
} else {
// 失配:利用部分匹配表跳過無用比較
if (j > 1 && part[j - 1] > 0) {
i += (i - j - part[j - 1]);
} else {
i = (i - j); // 沒有可複用的前綴,退回起點下一位
}
break;
}
}
完整版本把匹配表生成、主循環、結果返回串在一起即可,測試時可以拿 "BBC ABCDAB ABCDABCDABDE" 與 "ABCDABD" 對比原生 indexOf 的結果,並用 Date 差值打印耗時。
第一種實現預先把整張表算出來,屬於典型的空間換時間。第二種思路是「用到哪算到哪」:不生成完整數組,只針對當前已成功匹配的前綴即時計算部分匹配值。
function next(str) {
var prefix = [];
var suffix = [];
var partMatch;
var i = str.length;
var newStr = str.substring(0, i + 1);
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 = prefix[k].length;
}
if (!partMatch) partMatch = 0;
return partMatch;
}
與匹配表版本的邏輯完全一致,只是去掉了外層遍歷,直接定位到當前已匹配的串。在主循環的失配分支中改為:
} else {
if (j > 1) {
i += i - next(searchStr.slice(0, j));
} else {
i = (i - j);
}
break;
}
理解 KMP 的門檻不在代碼,而在「為什麼可以移動兩位」。一旦接受了「前綴與後綴重合的部分可以跳過」這個前提,剩下的都是工程實現細節。後續若接觸 BM 算法,會發現它的優化邏輯換到了另一側——從後往前比較,同樣值得一看。