首先簡要介紹一下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的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中的這種形式。
最后，我們便可以在AC自動機(jī)上查找模式串中出現(xiàn)過哪些單詞了。匹配過程分兩種情況：(1)當(dāng)前字符匹配，表示從當(dāng)前節(jié)點(diǎn)沿著樹邊有一條路徑可以到達(dá)目標(biāo)字符，此時只需沿該路徑走向下一個節(jié)點(diǎn)繼續(xù)匹配即可，目標(biāo)字符串指針移向下個字符繼續(xù)匹配；(2)當(dāng)前字符不匹配，則去當(dāng)前節(jié)點(diǎn)失敗指針?biāo)赶虻淖址^續(xù)匹配，匹配過程隨著指針指向root結(jié)束。重復(fù)這2個過程中的任意一個，直到模式串走到結(jié)尾為止。
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é)束。
到此為止AC自動機(jī)算法的詳細(xì)過程已經(jīng)全部介紹結(jié)束，看一道例題：
http://acm.hdu.edu.cn/showproblem.php?pid=2222
Problem Description
In the modern time, Search engine came into the life of everybody like Google, Baidu, etc.
Wiskey also wants to bring this feature to his image retrieval system.
Every image have a long description, when users type some keywords to find the image, the system will match the keywords with description of image and show the image which the most keywords be matched.
To simplify the problem, giving you a description of image, and some keywords, you should tell me how many keywords will be match.
Input
First line will contain one integer means how many cases will follow by.
Each case will contain two integers N means the number of keywords and N keywords follow. (N <= 10000)
Each keyword will only contains characters 'a'-'z', and the length will be not longer than 50.
The last line is the description, and the length will be not longer than 1000000.
Output
Print how many keywords are contained in the description.
Sample Input
1
5
she
he
say
shr
her
yasherhs
Sample Output
1 #include <iostream>
2 using namespace std;
3
4 const int kind = 26;
5 struct node{
6 node *fail; //失敗指針
7 node *next[kind]; //Tire每個節(jié)點(diǎn)的26個子節(jié)點(diǎn)（最多26個字母）
8 int count; //是否為該單詞的最后一個節(jié)點(diǎn)
9 node(){ //構(gòu)造函數(shù)初始化
10 fail=NULL;
11 count=0;
12 memset(next,NULL,sizeof(next));
13 }
14 }*q[500001]; //隊列，方便用于bfs構(gòu)造失敗指針
15 char keyword[51]; //輸入的單詞
16 char str[1000001]; //模式串
17 int head,tail; //隊列的頭尾指針
18
19 void insert(char *str,node *root){
20 node *p=root;
21 int i=0,index;
22 while(str[i]){
23 index=str[i]-'a';
24 if(p->next[index]==NULL) p->next[index]=new node();
25 p=p->next[index];
26 i++;
27 }
28 p->count++;
29 }
30 void build_ac_automation(node *root){
31 int i;
32 root->fail=NULL;
33 q[head++]=root;
34 while(head!=tail){
35 node *temp=q[tail++];
36 node *p=NULL;
37 for(i=0;i<26;i++){
38 if(temp->next[i]!=NULL){
39 if(temp==root) temp->next[i]->fail=root;
40 else{
41 p=temp->fail;
42 while(p!=NULL){
43 if(p->next[i]!=NULL){
44 temp->next[i]->fail=p->next[i];
45 break;
46 }
47 p=p->fail;
48 }
49 if(p==NULL) temp->next[i]->fail=root;
50 }
51 q[head++]=temp->next[i];
52 }
53 }
54 }
55 }
56 int query(node *root){
57 int i=0,cnt=0,index,len=strlen(str);
58 node *p=root;
59 while(str[i]){
60 index=str[i]-'a';
61 while(p->next[index]==NULL && p!=root) p=p->fail;
62 p=p->next[index];
63 p=(p==NULL)?root:p;
64 node *temp=p;
65 while(temp!=root && temp->count!=-1){
66 cnt+=temp->count;
67 temp->count=-1;
68 temp=temp->fail;
69 }
70 i++;
71 }
72 return cnt;
73 }
74 int main(){
75 int n,t;
76 scanf("%d",&t);
77 while(t--){
78 head=tail=0;
79 node *root=new node();
80 scanf("%d",&n);
81 getchar();
82 while(n--){
83 gets(keyword);
84 insert(keyword,root);
85 }
86 build_ac_automation(root);
87 scanf("%s",str);
88 printf("%d\n",query(root));
89 }
90 return 0;
91 }
PS：原創(chuàng)，轉(zhuǎn)載請注明出處