首先簡要介紹一下AC自動機(jī)：Aho-Corasick automation，該算法在1975年產(chǎn)生于貝爾實(shí)驗(yàn)室，是著名的多模匹配算法之一。一個常見的例子就是給出n個單詞，再給出一段包含m個字符的文章，讓你找出有多少個單詞在文章里出現(xiàn)過。要搞懂AC自動機(jī)，先得有模式樹（字典樹）Trie和KMP模式匹配算法的基礎(chǔ)知識。AC自動機(jī)算法分為3步：構(gòu)造一棵Trie樹，構(gòu)造失敗指針和模式匹配過程。
如果你對KMP算法和了解的話，應(yīng)該知道KMP算法中的next函數(shù)（shift函數(shù)或者fail函數(shù)）是干什么用的。KMP中我們用兩個指針i和j分別表示，A[i-j+ 1..i]與B[1..j]完全相等。也就是說，i是不斷增加的，隨著i的增加j相應(yīng)地變化，且j滿足以A[i]結(jié)尾的長度為j的字符串正好匹配B串的前 j個字符，當(dāng)A[i+1]≠B[j+1]，KMP的策略是調(diào)整j的位置（減小j值）使得A[i-j+1..i]與B[1..j]保持匹配且新的B[j+1]恰好與A[i+1]匹配，而next函數(shù)恰恰記錄了這個j應(yīng)該調(diào)整到的位置。同樣AC自動機(jī)的失敗指針具有同樣的功能，也就是說當(dāng)我們的模式串在Tire上進(jìn)行匹配時，如果與當(dāng)前節(jié)點(diǎn)的關(guān)鍵字不能繼續(xù)匹配的時候，就應(yīng)該去當(dāng)前節(jié)點(diǎn)的失敗指針?biāo)赶虻墓?jié)點(diǎn)繼續(xù)進(jìn)行匹配。
看下面這個例子：給定5個單詞：say she shr he her，然后給定一個字符串yasherhs。問一共有多少單詞在這個字符串中出現(xiàn)過。我們先規(guī)定一下AC自動機(jī)所需要的一些數(shù)據(jù)結(jié)構(gòu)，方便接下去的編程。
1 const int kind = 26;
2 struct node{
3 node *fail; //失敗指針
4 node *next[kind]; //Tire每個節(jié)點(diǎn)的個子節(jié)點(diǎn)（最多個字母）
5 int count; //是否為該單詞的最后一個節(jié)點(diǎn)
6 node(){ //構(gòu)造函數(shù)初始化
7 fail=NULL;
8 count=0;
9 memset(next,NULL,sizeof(next));
10 }
11 }*q[500001]; //隊列，方便用于bfs構(gòu)造失敗指針
12 char keyword[51]; //輸入的單詞
13 char str[1000001]; //模式串
14 int head,tail; //隊列的頭尾指針
有了這些數(shù)據(jù)結(jié)構(gòu)之后，就可以開始編程了：
首先，將這5個單詞構(gòu)造成一棵Tire，如圖-1所示。
1 void insert(char *str,node *root){
2 node *p=root;
3 int i=0,index;
4 while(str[i]){
5 index=str[i]-'a';
6 if(p->next[index]==NULL) p->next[index]=new node();
7 p=p->next[index];
8 i++;
9 }
10 p->count++; //在單詞的最后一個節(jié)點(diǎn)count+1，代表一個單詞
11 }
在構(gòu)造完這棵Tire之后，接下去的工作就是構(gòu)造下失敗指針。構(gòu)造失敗指針的過程概括起來就一句話：設(shè)這個節(jié)點(diǎn)上的字母為C，沿著他父親的失敗指針走，直到走到一個節(jié)點(diǎn)，他的兒子中也有字母為C的節(jié)點(diǎn)。然后把當(dāng)前節(jié)點(diǎn)的失敗指針指向那個字母也為C的兒子。如果一直走到了root都沒找到，那就把失敗指針指向root。具體操作起來只需要：先把root加入隊列(root的失敗指針指向自己或者NULL)，這以后我們每處理一個點(diǎn)，就把它的所有兒子加入隊列，隊列為空。
1 void build_ac_automation(node *root){
2 int i;
3 root->fail=NULL;
4 q[head++]=root;
5 while(head!=tail){
6 node *temp=q[tail++];
7 node *p=NULL;
8 for(i=0;i<26;i++){
9 if(temp->next[i]!=NULL){
10 if(temp==root) temp->next[i]->fail=root;
11 else{
12 p=temp->fail;
13 while(p!=NULL){
14 if(p->next[i]!=NULL){
15 temp->next[i]->fail=p->next[i];
16 break;
17 }
18 p=p->fail;
19 }
20 if(p==NULL) temp->next[i]->fail=root;
21 }
22 q[head++]=temp->next[i];
23 }
24 }
25 }
26 }
從代碼觀察下構(gòu)造失敗指針的流程：對照圖-2來看，首先root的fail指針指向NULL，然后root入隊，進(jìn)入循環(huán)。第1次循環(huán)的時候，我們需要處理2個節(jié)點(diǎn)：root->next[‘h’-‘a’](節(jié)點(diǎn)h) 和 root->next[‘s’-‘a’](節(jié)點(diǎn)s)。把這2個節(jié)點(diǎn)的失敗指針指向root，并且先后進(jìn)入隊列，失敗指針的指向?qū)?yīng)圖-2中的(1)，(2)兩條虛線；第2次進(jìn)入循環(huán)后，從隊列中先彈出h，接下來p指向h節(jié)點(diǎn)的fail指針指向的節(jié)點(diǎn)，也就是root；進(jìn)入第13行的循環(huán)后，p=p->fail也就是p=NULL，這時退出循環(huán)，并把節(jié)點(diǎn)e的fail指針指向root，對應(yīng)圖-2中的(3)，然后節(jié)點(diǎn)e進(jìn)入隊列；第3次循環(huán)時，彈出的第一個節(jié)點(diǎn)a的操作與上一步操作的節(jié)點(diǎn)e相同，把a(bǔ)的fail指針指向root，對應(yīng)圖-2中的(4)，并入隊；第4次進(jìn)入循環(huán)時，彈出節(jié)點(diǎn)h(圖中左邊那個)，這時操作略有不同。在程序運(yùn)行到14行時，由于p->next[i]!=NULL(root有h這個兒子節(jié)點(diǎn)，圖中右邊那個)，這樣便把左邊那個h節(jié)點(diǎn)的失敗指針指向右邊那個root的兒子節(jié)點(diǎn)h，對應(yīng)圖-2中的(5)，然后h入隊。以此類推：在循環(huán)結(jié)束后，所有的失敗指針就是圖-2中的這種形式。
1 int query(node *root){
2 int i=0,cnt=0,index,len=strlen(str);
3 node *p=root;
4 while(str[i]){
5 index=str[i]-'a';
6 while(p->next[index]==NULL && p!=root) p=p->fail;
7 p=p->next[index];
8 p=(p==NULL)?root:p;
9 node *temp=p;
10 while(temp!=root && temp->count!=-1){
11 cnt+=temp->count;
12 temp->count=-1;
13 temp=temp->fail;
14 }
15 i++;
16 }
17 return cnt;
18 }
對照圖-2，看一下模式匹配這個詳細(xì)的流程，其中模式串為yasherhs。對于i=0,1。Trie中沒有對應(yīng)的路徑，故不做任何操作；i=2,3,4
時，指針p走到左下節(jié)點(diǎn)e。因?yàn)楣?jié)點(diǎn)e的count信息為1，所以cnt+1，并且講節(jié)點(diǎn)e的count值設(shè)置為-1，表示改單詞已經(jīng)出現(xiàn)過了，防止重復(fù)
計數(shù)，最后temp指向e節(jié)點(diǎn)的失敗指針?biāo)赶虻墓?jié)點(diǎn)繼續(xù)查找，以此類推，最后temp指向root，退出while循環(huán)，這個過程中count增加了
2。表示找到了2個單詞she和he。當(dāng)i=5時，程序進(jìn)入第5行，p指向其失敗指針的節(jié)點(diǎn)，也就是右邊那個e節(jié)點(diǎn)，隨后在第6行指向r節(jié)點(diǎn)，r節(jié)點(diǎn)的
count值為1，從而count+1，循環(huán)直到temp指向root為止。最后i=6,7時，找不到任何匹配，匹配過程結(jié)束。