Aho-Corasick
Aho-Corasick（AC 自動機）是多模式字串匹配演算法。
適合在一段長文字中，同時搜尋大量關鍵詞（patterns）。
核心觀念：
- 用 Trie 儲存所有 patterns
- 建立 failure link（失敗跳轉）
- 一次查詢輸出所有匹配
為什麼需要 Aho-Corasick
若有 k 個 pattern，逐一用單模式比對（例如 KMP）會重複掃描 text。
Aho-Corasick 可以把多模式合併成一個自動機，
主字串在攤銷意義下通常只需線性掃描一次。
結構組成
1) Trie
- 每個節點代表一段前綴
- path 對應 pattern 字元序列
- 結尾節點記錄匹配到哪個 pattern
2) Failure Link
當目前字元無法沿 Trie 繼續時，
沿 failure link 跳到最長可用後綴對應節點。
這個想法與 KMP, Knuth-Morris-Pratt 的失敗回退概念相近，
只是從單一 pattern 擴展到整個 Trie。
3) Output
每到一個節點，輸出該節點所對應的所有匹配；
這些匹配可由自身與 failure 鏈繼承而來。
註：有些實作會先把 failure 節點的輸出預先合併到當前節點，
查詢時可直接讀當前 output，不必每次沿 failure 鏈逐層回溯。
搜尋流程（概念）
- 先把所有 pattern 建成 Trie
- 用 BFS 建立每個節點的 failure link
- 掃描 text：
- 若可轉移，前進
- 若不可轉移，沿 failure link 跳轉
- 讀取當前節點 output（可能已含 failure 繼承結果）
複雜度
設：
- N = text 長度
- L = 所有 pattern 長度總和
- Z = 匹配結果總數
常見複雜度：
- 建構：通常可視為接近 O(L)，但實際上會受字元集大小與轉移表實作方式影響
- 查詢：攤銷 O(N + Z)
因此整體常寫成近似線性：
O(N + L + Z)
什麼情境特別適合
- 關鍵詞過濾（敏感詞、黑名單）
- IDS/防毒特徵匹配
- 大量字典詞搜尋（log / 文本分析）
- 同時匹配多個固定詞組
和 KMP 的差異
- KMP, Knuth-Morris-Pratt：單一 pattern 高效匹配
- Aho-Corasick：多個 pattern 同時匹配
若只有一個 pattern，KMP 通常更簡潔；
若 pattern 很多，Aho-Corasick 優勢明顯。
限制與注意事項
- Aho-Corasick 是精確字串匹配，不是語義搜尋
- 不會自動處理同義詞、拼字錯誤、語意近似
- 若 pattern 集合頻繁動態新增或刪除，可能需要重建或額外維護成本