Aho-Corasick 演算法

假設你必須在一串文字中掃描成千上萬個禁用詞中的任何一個——垃圾郵件過濾器、比對多個簽章的病毒掃描器，或一個會標出清單中任何關鍵字的搜尋。對每個詞各跑一次單模式比對器，代價會是文字長度乘以詞數。Aho-Corasick 基本上只用一趟掃過文字，就找出所有詞的所有出現，不管你字典裡有多少個詞。

它的做法是先把所有模式建成一棵字典樹（trie）：一棵讓共同前綴共享路徑的樹（所以 "he"、"her"、"his" 在靠近根部處重疊）。接著加上失敗連結，這是 KMP 失敗函數的多模式推廣：從每個 trie 節點，一條失敗連結指向代表「目前已匹配字串的最長真後綴、且同時是某個模式之前綴」的節點。現在一次一個字元掃描文字，當下一個字元符合某條邊時往下走 trie，不符合時沿失敗連結走——和 KMP 完全一樣，只是同時跨越所有模式。每當你經過（或失敗連結到達）一個標示某模式結尾的節點，就回報那次出現。建這個自動機是 O(所有模式的總長度)，掃描是 O(n + 回報的匹配數)。最後那一項很重要：若許多模式在同一處重疊，回報它們是無可避免的工作。

Aho-Corasick 出自 1975 年，是字典比對的標準工具，驅動了 fgrep 這類經典工具以及許多入侵偵測和生物資訊系統。它的大優點是代價幾乎不取決於模式的數量——往字典裡加更多詞會讓自動機變大，但不會拖慢每字元的掃描。值得記住的心智模型是：它是用一棵樹取代一條線的 KMP，其中失敗連結讓單一次文字掃描，同時追蹤每個模式的部分匹配。