Knuth-Morris-Pratt 演算法
/ kuh-NOOTH MOR-iss PRATT /
當樸素比對在一次比較進行到一半時失敗，它只把模式向前滑一格，並忘掉學到的一切。但想想看：你剛讀了幾個文字字元，而它們匹配了你模式的開頭。那是關於文字的、得來不易的真實資訊。KMP 的整個構想，就是保留這份資訊，並用它在安全的前提下把模式向前滑超過一格，於是它永遠不必重讀已經消耗過的文字字元。
它的運作如下。KMP 先只從模式本身建出一個前綴（失敗）函數，回答這個問題：如果我已匹配了模式的前 k 個字元而下一個失敗了，那麼同時是「已匹配部分之後綴」的「模式前綴」中最長的是哪個？這個數字精確告訴 KMP，它能把模式向前移多遠而不漏掉任何可能的匹配。接著它用一個永不後退的指標由左到右掃描文字：匹配時同時推進模式指標和文字指標；不匹配時查詢失敗函數，把模式指標（而非文字指標）退到下一個有希望的位置，再繼續。由於文字指標只會往前走，而模式指標的後退總量有界，掃描是 O(n)，建失敗函數是 O(m)，總計 O(n+m)。
KMP 由 Donald Knuth、James Morris 與 Vaughan Pratt 於 1977 年發表，是第一個保證最壞情況線性時間的比對演算法，至今仍是基石。它留下的功課比字串搜尋本身更大：先預處理模式以了解它內部的自我重疊，再在掃描時利用這些重疊，使失敗的工作永不浪費。同樣的失敗函數構想推廣到多模式（Aho-Corasick），也是許多後來字串演算法的基礎。請注意，KMP 永遠保證線性時間，而 Boyer-Moore 在實務上往往更快，但沒有 KMP 那種乾淨的最壞情況保證。
P = "abcab"，T = "abcabd..."。我們匹配了 a、b、c、a、b（5 個字元），接著下一個文字字元 d 對上 P 的 'c' 失敗。樸素法會回到文字位置 1 重來。KMP 知道已匹配的後綴 "ab" 等於某個模式前綴，於是把模式移動以重新對齊那個 "ab"，並從 P[2] 接著比較——文字指標從未後退，沒有任何字元被重讀。
不匹配時，KMP 透過失敗函數移動模式，而非重置文字指標。
KMP 的文字指標永不後退——光是這一點就換來了 O(n+m)。一個常見混淆：KMP 的加速完全來自模式的自我結構，所以它無法像 Boyer-Moore 那樣在文字中「往前跳」；它只是避免重讀。