暴力掃描不肯從中學習的那份浪費
上一篇指南把問題定了型，也替最顯而易見的方法計了時：把長度 m 的模式 P 沿著長度 n 的文字 T 滑動，在大約 n 個起始位置的每一個逐字元比對。當一連串字元都對上、卻在某處對不上時，暴力掃描只是聳聳肩，把模式往右挪一格，再從 P 的第一個字元重新開始比對。這就是暴力比對，其最壞情況為 O(n*m)——以模式 `aaaa...ab` 比對文字 `aaaa...aa`，幾乎每個視窗都得做將近 m 次比對才失敗。
仔細看看什麼被丟掉了。假設 P = `abcab`，而我們在文字中已經比對出 `abca`，接著第五個字元才對不上。暴力掃描此時把 P 往右挪一格，再把那些文字字元從頭重看一遍。但我們其實已經「知道」它們是什麼——它們拼出的是 `abca`，因為它們剛剛與模式對上了。我們即將重讀的那些文字位置並不是謎；它們是 P 的一個已知前綴。重讀它們就是那份浪費，而它之所以可避免，正因為這份資訊住在模式裡，而模式在搜尋開始之前我們就能先研究。
於是克努特-莫里斯-普拉特演算法的整個點子就是一筆交易。先花一點時間單獨分析 P——與任何文字無關——建出一張表，回答一個問題：發生不匹配後，模式可以安全地往前跳多遠，才能保證任何已比對過的文字都不必再被讀一次？有了這張表，文字指標便一路嚴格向前推進，搜尋變成 O(n + m) 時間的精確比對。技藝完全在於如何定義並算出這張表。
邊界：把前綴函數仔細地定義出來
這張表建立在一個概念上：邊界（border）。一個字串的邊界，是一個既是真前綴又是後綴的字串——「真」意指比整個字串短。在 `abcab` 中，前綴 `ab` 等於後綴 `ab`，所以 `ab` 是一個長度為 2 的邊界。空字串是任何字串的邊界（長度 0）。前綴函數（記作 pi）為 P 的每一個前綴記下它「最長」邊界的長度：pi[i] 是 P[0..i]（在位置 i 結束的前綴）最長邊界的長度。
為什麼是邊界？因為邊界正好是模式在不匹配後能夠「不丟失已得進展」就接續下去的地方。假設我們把 P 長度為 L 的前綴與文字對上了，接著第 L+1 個字元失敗。最後 L 個文字字元拼出的是 P[0..L-1]。若 P 有一個長度為 b 的邊界，那麼 P 的前 b 個字元等於那段已比對片段的後 b 個字元——所以那 b 個文字字元「已經」與 P 的開頭對上了。我們可以把 P 往前滑，讓它長度為 b 的前綴對齊到那裡，再從 P 的第 b 個字元繼續比對。最長邊界給出「最小的安全位移」；跳得更遠可能會略過一個真正的出現。
P = a b a b a b c a idx 0 1 2 3 4 5 6 7 pi 0 0 1 2 3 4 0 1 # pi[4]=3: prefix "ababa" has longest border "aba" (len 3) # pi[6]=0: prefix "abababc" has no nonempty border
在線性時間內算出 pi——這張表會自己長出來
美妙之處在於：前綴函數是靠「讓 KMP 拿模式去比對自己」算出來的。我們由左而右建立 pi。維持一個長度 `k` = 當前字元之前那個前綴的最長邊界。要延伸到下一個字元 P[i] 時，我們問：P[k] 是否等於 P[i]？若是，邊界增長一格，故 pi[i] = k + 1。若否，我們得縮短候選邊界——而下一個要試的較短候選，本身正是「某邊界的邊界」，這個我們早已記在 pi[k-1] 裡。我們持續用 k = pi[k-1] 往回退，直到字元對上、或 k 退到 0 為止。
- 設 pi[0] = 0（單一字元的前綴只有空邊界）且 k = 0。讓 i 從 1 走到 m-1。
- 當 k > 0 且 P[k] != P[i] 時，往回退：k = pi[k-1]。這會把「次長的邊界」當成新候選來試，永遠不會從零重掃。
- 若此時 P[k] == P[i]，邊界延伸：k 加一。無論如何，記下 pi[i] = k，然後移到下一個 i。
既然有那個內層回退迴圈，為何這是線性而非平方？用攤還的方式推理。變數 k 在 m 次迭代的每一次至多上升 1，所以整段執行下來它總共至多上升 m。每一次回退都使 k 至少嚴格下降 1。由於 k 從 0 起步、始終非負、且總共只上升了 m，那麼整個計算過程中回退「下降」的「總」次數也至多是 m。因此即使某一次迭代可能回退很多次，迴圈本體整體上仍只執行 O(m) 次。這正是聚合法在做它的本分。
執行搜尋：文字指標永不回頭
有了 pi，搜尋就是同一個迴圈，只是現在讀的是文字。維持一個位置 `q` = 目前已比對的模式字元數。用索引 i 由左而右掃描文字。對每個文字字元 T[i]：當 q > 0 且 P[q] != T[i] 時，回退 q = pi[q-1]（重用邊界！）。若 P[q] == T[i]，q 加一。若 q 達到 m，表示找到了一個在 i 結束的完整出現；記下它，再回退 q = pi[m-1] 以繼續尋找可能重疊的匹配。文字索引 i 永遠只往前移——這正是整件事的關鍵。
走一個極小的例子。P = `aba`，故 pi = [0,0,1]。文字 T = `ababa`。在 i=0,1,2 時我們對上 `aba`：q 達到 3，回報一個在索引 2 結束的匹配，然後回退到 q = pi[2] = 1（邊界 `a` 仍是匹配的）。在 i=3，T[3]=`b` 與 P[1]=`b` 對上，q=2。在 i=4，T[4]=`a` 與 P[2]=`a` 對上，q=3，回報第二個在索引 4 結束的匹配。兩個重疊的出現，在對五個字元的一次向前掃描中就找到了——文字指標從未倒退，而重疊之所以被抓到，正是因為我們從邊界（而非從頭）接續下去。
同樣的攤還論證也界定了搜尋。文字索引 i 恰好前進 n 次。q 每次前進至多上升 1，故總共至多上升 n，而每次回退使它至少下降 1，所以回退總數至多 n。因此搜尋是 O(n)，連同 O(m) 的預處理，整個 KMP 是 O(n + m)——對合併後的輸入規模呈線性，且不暗藏對字母表大小的依賴。下一篇指南的 Z 演算法會以另一條路徑達到這同一套「只向前、絕不重讀」的紀律。
它為何正確，以及哪些地方要保持誠實
正確性建立在搜尋的一個乾淨的迴圈不變量上：處理完 T[0..i] 後，q 等於「既是 P 之前綴、又是 T[0..i] 之後綴」者中最長的長度。把這句讀兩遍——它說的是：給定目前所見的一切，q 是我們仍可能身處其中的最長模式前綴。當 q 達到 m 時，那個最長前綴就是整個 P，所以 P 確實在 i 結束：一個真正的出現，而非誤報。而回退這一步，正是不匹配後重新建立此不變量的關鍵，因為下一個可行的「前綴兼後綴」就是次長的邊界，pi[q-1] 直接把它交給我們。
不變量在每一步都存活下來，本身就是對 i 做歸納法的一個證明，憑藉一個關於邊界的小事實：一個字串的每一個邊界（除了最長的那個）都是它最長邊界的邊界。正是這個事實，讓回退鏈 q、pi[q-1]、pi[pi[q-1]-1]、… 以遞減順序「不漏掉任何一個」地列舉出所有候選前綴長度——所以這個迴圈總能找到真正的最長匹配，且絕不越過一個有效的出現。
兩個誠實的限制。其一，KMP 解的是「由左而右讀的序列上、單一模式的精確比對」；它本身不提供近似比對，也不一次處理多個模式——那是日後 Aho-Corasick 把同一套邊界概念推廣到多個模式之處。其二，KMP 省下的是「比對次數」，不是對 I/O 的魔法加速：常數因子小且可預測，但若你真正的成本是從磁碟讀位元組，那麼任何線性掃描器（包括 Rabin-Karp）付的 I/O 都一樣。KMP 獨特的承諾，是「保證的線性比對次數、且零文字重讀」，而這完全是靠「在碰文字之前就先分析模式」推導出來的。