AC自動機演算法

佇電腦科學當中，Aho–Corasick 演算法是由 Alfred V . Aho 和 Margaret J . Corasick 發明的字串搜揣演算法，就用佇輸入的一串字串內底匹配有限組「字典」著的子串。伊佮普通字串匹配的無仝點是仝時佮所有字典串進行匹配。演算法均攤狀況下具有將近若像線性的時間複雜度，大約字串的長度加所有匹配的數量。毋過需要揣著所有匹配數，若是逐跤皮相匹配（如字典為 a，aa，aaa，aaaa，輸入的字串為 aaaa）， 演算法的時間複雜度會強欲親像匹配的二次函式。

該演算法主要倚靠構造一个有限狀態機（類似佇一个 trie 樹中添加失配指標）來實現。遮的其他的失配指標允准咧走揣字串失敗的時陣來進行回退（譬論講設 Trie 樹的單詞 cat 匹配失敗，猶毋過佇咧 Trie 樹中存在另外一個單詞 cart，失配指標就會指向字條 ca）， 轉來到某字首的其他分支，免於重複匹配字首，提高演算法效率。

做一个字典串集合是已知的 ( 比如講一个電腦病毒庫 ) , 就會當佇離線的方式來共自動機求出並且囥做供日後使用，佇這个情形下，演算法的時間複雜度做輸入字串長度佮匹配數量之和。

UNIX 系統內底的一个命令 fgrep 就是以 AC 自動機演算法做基礎實現的。

看仿

設一个字典內底有如下單詞：{ a , ab , bab , bc , bca , c , caa } .

下跤的圖樣是用 AC 自動機演算法由該詞典構造成的一欉 Trie 樹，其中逐个節點攏有一條對根節點著伊的唯一路徑，代表一个單詞。

佇這種資料結構當中，字捾的每一字都有一个節點來表示（詳見 Trie）。 所以若是（bca）佇字典內底，愛會存在（bca），（bc），（b）和（） 對應的彼个節點。若該節點表示的字串佇字典內底存在，則該節點為一个藍色節點，若無為一个殕色的所在。

樹仔中的烏色有向邊代表起點是終點的「父親」（即起點對應字串增加一字元會當終點對應字葩）， 比如講對（bc）有一條指向（bca）彼烏的有向邊仔。

樹仔的藍色有向邊（字尾節點）代表終點對應字串是起點對應字串的上大嚴格字尾。譬如講對著一个彼个節點（caa）， 伊的嚴格字尾為（aa），（a）和（），其中佇圖中上長的為伊（a）， 所以乎（caa）有一條指向（a）的藍色有向邊仔。一个節點的藍色有向邊仔會當線上性時間內底通過重複遍歷節點父親節點的藍色有向邊仔一直到橫移節點（the traversing node）有一个屬於目標儉字條的囡仔。

樹仔的綠色有向邊仔（字典字尾節點）表終點是起點經過藍色的有向邊到位的第一个藍色的節點（即字典中存在終點對應字串）。 比如講（bca）有一條綠色邊連向（a）， 因為乎（a）是（bca）通過藍色有向邊到位的第一个藍色的節點，路徑為（bca）→（ca）→（a）。 綠色有向邊仔嘛會當線頂性時間內底通過遍歷藍色有向邊仔一直到揣著一个藍色的節點，並用記憶化的方法算。

佇每一步內底，演算法先走揣當前節點的「囡仔節點」，你若無揣著匹配，走揣伊的後綴（suffix）儉點仔的囡仔，若猶原無，紲落去走揣綴節目的後綴節點的囡仔，按呢循環，一直到根結點，若到根節點會猶原揣著匹配則結束。

做演算法走揣著一个節點，則輸出所有結束在拄著前位置的字典項。輸出步驟為首先揣著該節點的字典字尾，然後用遞迴的方式一直執行到節點無字典字首為止。同時，若該節點為一个字典節點，著輸出該節點本身。

輸入 abccab 後演算法的執行步驟之下：

外部連結

• Set Matching and Aho–Corasick Algorithm , lecture slides by Pekka Kilpeläinen
• Aho–Corasick entry in NIST's Dictionary of Algorithms and Data Structures
• Aho-Corasick implementation in C + +
• Aho-Corasick implementation in Go