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