Aho-Corasick算法對應的資料結構是Aho-Corasick自動機，簡稱AC自動機。
搞程式設計的一般都應該知道自動機FA吧，具體細分為：确定性有限狀态自動機(DFA)和非确定性有限狀态自動機NFA。普通的自動機不能進行多模式比對，AC自動機增加了失敗轉移，轉移到已經輸入成功的文本的字尾，來實作。
1.多模式比對
多模式比對就是有多個模式串P1,P2,P3...，Pm，求出所有這些模式串在連續文本T1....n中的所有可能出現的位置。
例如：求出模式集合{"nihao","hao","hs","hsr"}在給定文本"sdmfhsgnshejfgnihaofhsrnihao"中所有可能出現的位置。
2.Aho-Corasick算法
使用Aho-Corasick算法需要三步：
1.建立模式的Trie
2.給Trie添加失敗路徑
3.根據AC自動機，搜尋待處理的文本
下面說明這三步：
2.1建立多模式集合的Trie樹
Trie樹也是一種自動機。對于多模式集合{"say","she","shr","he","her"}，對應的Trie樹如下，其中紅色标記的圈是表示為接收态：
2.2為多模式集合的Trie樹添加失敗路徑，建立AC自動機
構造失敗指針的過程概括起來就一句話：設這個節點上的字母為C，沿着他父親的失敗指針走，直到走到一個節點，他的兒子中也有字母為C的節點。然後把目前節點的失敗指針指向那個字母也為C的兒子。如果一直走到了root都沒找到，那就把失敗指針指向root。
使用廣度優先搜尋BFS，層次周遊節點來處理，每一個節點的失敗路徑。
特殊處理：第二層要特殊處理，将這層中的節點的失敗路徑直接指向父節點(也就是根節點)。
2.3根據AC自動機，搜尋待處理的文本
從root節點開始，每次根據讀入的字元沿着自動機向下移動。
當讀入的字元，在分支中不存在時，遞歸走失敗路徑。如果走失敗路徑走到了root節點，則跳過該字元，處理下一個字元。
因為AC自動機是沿着輸入文本的最長字尾移動的，是以在讀取完所有輸入文本後，最後遞歸走失敗路徑，直到到達根節點，這樣可以檢測出所有的模式。
3.Aho-Corasick算法代碼示例
模式串集合：{"nihao","hao","hs","hsr"}
待比對文本："sdmfhsgnshejfgnihaofhsrnihao"
代碼：
View Code
輸出：
本文轉自莫水千流部落格園部落格，原文連結：http://www.cnblogs.com/zhoug2020/p/6548845.html，如需轉載請自行聯系原作者