後綴自動機（suffix automaton）

有個令人驚訝的事實：你可以建出一台小機器，它恰好辨認某個給定字串的所有子字串。餵給它任何字元序列，它停在接受狀態，當且僅當那個序列出現在你字串裡的某處。後綴自動機正是這台機器——最小的這種辨認器——而儘管它接受多達 n^2/2 個子字串，它的狀態與邊卻只有線性多個。

形式上，字串 S 的後綴自動機是接受 S 之每個後綴的最小確定有限自動機（因此沿任一路徑走，它辨認 S 的每個子字串）。它的關鍵概念是 'endpos' 集合：兩個子字串被併入同一個狀態，當且僅當它們在 S 中於同一組結束位置出現。如此分組正是讓自動機達到最小的原因，而一個乾淨的定理保證：對長度為 n 的字串，它至多有 2n-1 個狀態、至多 3n-4 條轉移——是線性的，儘管它代表平方多個子字串。它能在常數字母表上以 O(n) 時間線上建構（一次加一個字元），並在成長過程中維護「後綴連結」（一個類比於 KMP 失敗連結的父結構）。檢查模式 P 是否出現，就只是把 P 跑過自動機：O(m) 時間，若從未卡住就成功。

後綴自動機是處理子字串問題的精巧重器。S 的相異子字串數等於對各狀態做一個簡單求和；某子字串出現的次數等於它 endpos 集合的大小（可沿後綴連結傳播計數而得）；兩字串的最長共同子字串，來自把一個字串跑過另一個的自動機。它與後綴樹密切相關（在精確的意義上，S 的後綴自動機對應到 S 反轉後的後綴樹），且常是後綴結構中最容易寫對的，並有極佳的常數。難處在於它的內部機制——endpos 等價與後綴連結——要真正理解並證明需下苦功，所以它回報的是耐心。