2.3　Aho-Corasick自動機

Aho-Corasick自動機（AC自動機）算法在1975年產生于貝爾實驗室，是著名的多模匹配算法之一。一個常見的例子就是給出n個單詞，再給出一段包含m個字符的文章，找出有多少個單詞在文章里出現過。要理解AC自動機，先得有Trie樹（字典樹）和KMP算法的基礎知識。AC自動機算法分為3步：構造一棵Trie樹，構造失敗指針（fail指針），以及模式匹配過程。

2.3.1　Aho-Corasick自動機原理

以典型應用為例，現給定3個單詞“china”“hit”“use”，再給定一段文本“chitchat”，求有多少個單詞出現在文本中。

（1）根據單詞集合{china,hit,use}建立一棵Trie樹，如圖2.4所示。

（2）根據所給文本“chitchat”依次匹配，圖中所示“chi”為匹配成功的字符串，如圖2.5所示。

（3）當匹配到第四個字符時，“t”和“n”匹配失敗，如圖2.6所示。

（4）此時知道已匹配成功的字符串為“chi”。

AC算法的核心就是在所有給定的單詞中，找到這樣的一個單詞，使其與已匹配成功字符串的相同前后綴最長，利用這個最長的相同前后綴實現搜索跳轉。例如，單詞“hit”與已匹配成功字符串“chi”的最長相同前后綴為“hi”，因此下一步從單詞“hit”的“t”開始搜索，如圖2.7所示。

（5）此時“t”是匹配的，在文本“chitchat”中找到一個單詞“hit”。

其實到這里，AC算法的思想已經基本呈現在讀者面前了。剩下的問題就是如何解決所述的“核心”。

AC算法的關鍵：在每個節點里設置一個指針（稱之為fail指針），指向跳轉的位置。

對于跳轉位置的選擇，基于以下兩點：

（1）對于根節點的所有子節點，它們的fail指針都指向根節點；

（2）而對于其他節點，不妨設該節點上的字符為“ch”，沿著它的父節點的fail指針走，直到走到一個節點，它的子節點中也有字符為“ch”的節點，然后把該節點的fail指針指向那個字符為“ch”的節點。如果一直走到根節點都沒找到，則把fail指針指向根節點。

指針跳轉如圖2.8所示。

2.3.2　Aho-Corasick自動機算法的實現

2.3.3　例題講解

例2-3　Keywords Search

Time Limit:2000/1000 ms（Java/Others）　Memory Limit:131072/131072 KB（Java/Others）

題目描述：

給定n個單詞以及1個字符串，問字符串中出現了多少個單詞（如單詞“her”“he”為字符串“aher”中出現了兩個單詞）。

輸入：

第一行輸入測試數據的組數，然后輸入一個整數n（n≤10000），在接下來的n行中每行輸入一個單詞（每個單詞都只包含“a”～“z”，并且單詞長度不超過50），最后輸入一個字符串（長度不超過1000000）。

輸出：

對于每組數據，要輸出一行，包含一個整數，該整數表示在字符串中出現了多少個單詞。

樣例輸入：

1

5

she

he

say

shr

her

yasherhs

樣例輸出：

3

題目來源：HDU 2222。

解題思路：

經典的模板題。