KMP 是經典的字串搜尋演算法,重點在於利用已匹配資訊減少回溯。與暴力搜尋相比,它能避免主串指標大幅倒退,提高效率。

KMP 的核心是 next 陣列。它記錄模式串每個位置之前,前綴與後綴相同的最長長度。當比對失敗時,可根據這個表移動模式串,而不必從頭開始。
function buildNext(pattern) {
const chars = Array.from(pattern);
const next = [0];
let j = 0;
for (let i = 1; i !== chars.length; i++) {
while (j > 0 && chars[i] !== chars[j]) {
j = next[j - 1];
}
if (chars[i] === chars[j]) {
j++;
}
next[i] = j;
}
return next;
}
比對時,若目前字元相同,主串與模式串指標同時前進;若不同,則依 next 陣列調整模式串指標。當模式串指標等於模式串長度,即代表找到匹配位置。
KMP 的時間複雜度通常為線性,適合作為長文字搜尋與演算法學習的基礎。