前綴（失敗）函數（prefix / failure function）

有些詞會折回到自己身上。在 "ababab" 中，開頭的 "abab" 在結尾重現；在 "aaaa" 中，每個前綴同時也是後綴。前綴函數正是用來度量這種自我重疊。對模式中的每個位置，它記錄：在模式開頭、且恰好結束於此處的、最長的相同片段有多長？這一張表就是驅動 KMP 演算法的引擎。

形式上，對模式 P，前綴函數 pi[i] 是 P[0..i] 的最長真前綴中，同時也是 P[0..i] 之後綴者的長度（「真」表示不是整段）。以 P = "ababaca" 為例：pi[0]=0（單一字元沒有真邊界），pi[1]=0（"ab"），pi[2]=1（"aba"：開頭的 "a" 對上結尾的 "a"），pi[3]=2（"abab"："ab" 重現），pi[4]=3（"ababa"："aba" 重現），pi[5]=0（"ababac"），pi[6]=1（"ababaca"）。它由一個優美的自我參照迴圈在 O(m) 內算出：要把一個已知邊界延長一個字元，你把下一個字元拿去對 P[目前的 pi]；若失敗就退回該位置的 pi 再試——這個函數被用來計算它自己。它選擇退回而非重來，所憑藉的洞見和 KMP 完全相同，只是套用在模式對自己做比對上。

為什麼 KMP 信任這個數字？假設 KMP 已匹配模式前 k 個字元而第 k+1 個不合。任何越過「模式前綴等於已匹配後綴」位置的位移，都可能漏掉一個真正的出現；而 pi[k-1] 正是最長的這種重疊，所以移動以重新對齊它，就是最大的安全位移。因此前綴函數不是啟發式猜測——它可被證明是 KMP 可以前進的精確量。同一個陣列也立刻解決相關難題：計算字串的邊界如何層層巢套、找出字串的最短週期、以及檢查一個字串是否為某個較小區塊的重複。