BF 算法失配時模式串固定右移 1 位,導致大量已知匹配信息被浪費。KMP (Knuth-Morris-Pratt) 算法利用模式串內部的前綴-後綴匹配特性,動態計算最大跳躍距離,將時間複雜度從 O(mn) 降至 O(m+n)。
對模式串 P 的每個前綴子串,計算其最長相等前綴後綴長度(不包含整個子串本身)。
P = "aaronaac" 為例| 索引 | 字符 | 前綴集合 | 後綴集合 | 最長公共長度 |
|---|---|---|---|---|
| 0 | a | ∅ | ∅ | 0 |
| 1 | a | {a} | {a} | 1 |
| 2 | r | {a, aa} | {r, ar} | 0 |
| 3 | o | {a, aa, aar} | {o, ro, aro} | 0 |
| 4 | n | {a, aa, aar, aaro} | {n, on, ron, aron} | 0 |
| 5 | a | {a, aa, aar, aaro, aaron} | {a, na, ona, rona, arona} | 1 |
| 6 | a | {a, aa, aar, aaro, aaron, aarona} | {a, aa, naa, onaa, ronaa, aronaa} | 2 |
| 7 | c | {a, aa, aar, aaro, aaron, aarona, aaronaa} | {c, ac, aac, naac, onaac, ronaac, aronaac} | 0 |
得到 next 數組(部分匹配值):[0, 1, 0, 0, 0, 1, 2, 0]
當在位置 j 失配(已匹配 j 個字符)時:
移動位數 = 已匹配字符數 - 部分匹配值 = j - next[j-1]
模式串新的比對起點 = j - next[j-1],主串指針 不回退。
// 計算 next 數組(部分匹配表)
function buildNext(pattern) {
var next = [0];
var j = 0; // 前綴末尾指針
for (var i = 1; i < pattern.length; i++) {
while (j > 0 && pattern[i] !== pattern[j]) {
j = next[j - 1]; // 遞歸回退
}
if (pattern[i] === pattern[j]) j++;
next[i] = j;
}
return next;
}
// KMP 主函數
function kmpSearch(text, pattern) {
if (!pattern.length) return 0;
var next = buildNext(pattern);
var j = 0; // 模式串指針
for (var i = 0; i < text.length; i++) {
while (j > 0 && text[i] !== pattern[j]) {
j = next[j - 1]; // 關鍵:利用 next 跳躍,i 不動
}
if (text[i] === pattern[j]) j++;
if (j === pattern.length) {
return i - j + 1; // 匹配成功,返回起始索引
}
}
return -1;
}
function kmpSearchDynamic(text, pattern) {
var m = pattern.length, n = text.length;
if (m === 0) return 0;
// 動態構建 next 並同時匹配
var next = new Array(m);
next[0] = 0;
var j = 0;
for (var i = 1; i < m; i++) { // 先構建完整 next
while (j > 0 && pattern[i] !== pattern[j]) j = next[j - 1];
if (pattern[i] === pattern[j]) j++;
next[i] = j;
}
j = 0;
for (var i = 0; i < n; i++) { // 匹配階段
while (j > 0 && text[i] !== pattern[j]) j = next[j - 1];
if (text[i] === pattern[j]) j++;
if (j === m) return i - m + 1;
}
return -1;
}

圖中主串 T、模式串 P,第 6 字符失配時:
ababa (5字符),next[4]=1,右移 5-1=4 位,主串指針不動str.charAt(i) 比 str[i] 在舊引擎更快,現代引擎已優化一致pattern.length、text.length 緩存到局部變量var next = new Uint16Array(m) 減少內存佔用(適用超長模式串)if (n < m) return -1;/user/:id/post/:pid)| 算法 | 時間複雜度 | 空間複雜度 | 匹配方向 | JS實現難度 | 適用場景 |
|---|---|---|---|---|---|
| BF | O(mn) | O(1) | 左→右 | ⭐ | 極短模式串、教學 |
| KMP | O(m+n) | O(m) | 左→右 | ⭐⭐⭐ | 通用單模式匹配、流式處理 |
| BM | O(m+n) 最好 O(n/m) | O(σ) | 右→左 | ⭐⭐⭐⭐ | 長模式串、字母表大 |
| Sunday | O(m+n) 最好 O(n/m) | O(σ) | 左→右 | ⭐⭐⭐ | 實際工程常用、比BM簡單 |
σ 為字符集大小
KMP 算法通過預處理模式串構建 next 數組,實現主串指針零回退,是字符串匹配從「暴力」走向「智能」的關鍵一步。JavaScript 實現時注意緩存長度、優化字符訪問、善用類型化數組。掌握 KMP 不僅能應對面試,更能在文本處理、搜索建議、路由匹配等實際業務中發揮核心作用。