首先簡要介紹一下AC自動機：Aho-Corasick automation，該算法在1975年產生于貝爾實驗室，是著名的多模匹配算法之一。一個常見的例子就是給出n個單詞，再給出一段包含m個字符的文章，讓你找出有多少個單詞在文章里出現過。要搞懂AC自動機，先得有模式樹（字典樹）Trie和KMP模式匹配算法的基礎知識。AC自動機算法分為3步：構造一棵Trie樹，構造失敗指針和模式匹配過程。
???? 如果你對KMP算法和了解的話，應該知道KMP算法中的next函數（shift函數或者fail函數）是干什么用的。KMP中我們用兩個指針i和j分別表示，A[i-j+ 1..i]與B[1..j]完全相等。也就是說，i是不斷增加的，隨著i的增加j相應地變化，且j滿足以A[i]結尾的長度為j的字符串正好匹配B串的前 j個字符，當A[i+1]≠B[j+1]，KMP的策略是調整j的位置（減小j值）使得A[i-j+1..i]與B[1..j]保持匹配且新的B[j+1]恰好與A[i+1]匹配，而next函數恰恰記錄了這個j應該調整到的位置。同樣AC自動機的失敗指針具有同樣的功能，也就是說當我們的模式串在Tire上進行匹配時，如果與當前節點的關鍵字不能繼續匹配的時候，就應該去當前節點的失敗指針所指向的節點繼續進行匹配。
????? 看下面這個例子：給定5個單詞：say?she?shr?he?her，然后給定一個字符串yasherhs。問一共有多少單詞在這個字符串中出現過。我們先規定一下AC自動機所需要的一些數據結構，方便接下去的編程。
?1?const?int?kind?=?26;?
?2?struct?node{??
?3?????node?*fail;???????//失敗指針
?4?????node?*next[kind];?//Tire每個節點的個子節點（最多個字母）
?5?????int?count;????????//是否為該單詞的最后一個節點
?6?????node(){???????????//構造函數初始化
?7?????????fail=NULL;?
?8?????????count=0;?
?9?????????memset(next,NULL,sizeof(next));?
10?????}?
11?}*q[500001];??????????//隊列，方便用于bfs構造失敗指針
12?char?keyword[51];?????//輸入的單詞
13?char?str[1000001];????//模式串
14?int?head,tail;????????//隊列的頭尾指針

有了這些數據結構之后，就可以開始編程了：
??? 首先，將這5個單詞構造成一棵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++;?????//在單詞的最后一個節點count+1，代表一個單詞
11?}

在構造完這棵Tire之后，接下去的工作就是構造下失敗指針。構造失敗指針的過程概括起來就一句話：設這個節點上的字母為C，沿著他父親的失敗指針走，直到走到一個節點，他的兒子中也有字母為C的節點。然后把當前節點的失敗指針指向那個字母也為C的兒子。如果一直走到了root都沒找到，那就把失敗指針指向root。具體操作起來只需要：先把root加入隊列(root的失敗指針指向自己或者NULL)，這以后我們每處理一個點，就把它的所有兒子加入隊列，隊列為空。

?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?}
??? 從代碼觀察下構造失敗指針的流程：對照圖-2來看，首先root的fail指針指向NULL，然后root入隊，進入循環。第1次循環的時候，我們需要處理2個節點：root->next[‘h’-‘a’](節點h) 和 root->next[‘s’-‘a’](節點s)。把這2個節點的失敗指針指向root，并且先后進入隊列，失敗指針的指向對應圖-2中的(1)，(2)兩條虛線；第2次進入循環后，從隊列中先彈出h，接下來p指向h節點的fail指針指向的節點，也就是root；進入第13行的循環后，p=p->fail也就是p=NULL，這時退出循環，并把節點e的fail指針指向root，對應圖-2中的(3)，然后節點e進入隊列；第3次循環時，彈出的第一個節點a的操作與上一步操作的節點e相同，把a的fail指針指向root，對應圖-2中的(4)，并入隊；第4次進入循環時，彈出節點h(圖中左邊那個)，這時操作略有不同。在程序運行到14行時，由于p->next[i]!=NULL(root有h這個兒子節點，圖中右邊那個)，這樣便把左邊那個h節點的失敗指針指向右邊那個root的兒子節點h，對應圖-2中的(5)，然后h入隊。以此類推：在循環結束后，所有的失敗指針就是圖-2中的這種形式。

??最后，我們便可以在AC自動機上查找模式串中出現過哪些單詞了。匹配過程分兩種情況：(1)當前字符匹配，表示從當前節點沿著樹邊有一條路徑可以到達目標字符，此時只需沿該路徑走向下一個節點繼續匹配即可，目標字符串指針移向下個字符繼續匹配；(2)當前字符不匹配，則去當前節點失敗指針所指向的字符繼續匹配，匹配過程隨著指針指向root結束。重復這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，看一下模式匹配這個詳細的流程，其中模式串為yasherhs。對于i=0,1。Trie中沒有對應的路徑，故不做任何操作；i=2,3,4時，指針p走到左下節點e。因為節點e的count信息為1，所以cnt+1，并且講節點e的count值設置為-1，表示改單詞已經出現過了，防止重復計數，最后temp指向e節點的失敗指針所指向的節點繼續查找，以此類推，最后temp指向root，退出while循環，這個過程中count增加了2。表示找到了2個單詞she和he。當i=5時，程序進入第5行，p指向其失敗指針的節點，也就是右邊那個e節點，隨后在第6行指向r節點，r節點的count值為1，從而count+1，循環直到temp指向root為止。最后i=6,7時，找不到任何匹配，匹配過程結束。

??? 到此為止AC自動機算法的詳細過程已經全部介紹結束，看一道例題： 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 15shehesayshrheryasherhs
Sample Output 3
?1?#include?<iostream>?
?2?using?namespace?std;?
?3???
?4?const?int?kind?=?26;?
?5?struct?node{??
?6?????node?*fail;???????//失敗指針
?7?????node?*next[kind];?//Tire每個節點的26個子節點（最多26個字母）
?8?????int?count;????????//是否為該單詞的最后一個節點
?9?????node(){???????????//構造函數初始化
10?????????fail=NULL;?
11?????????count=0;?
12?????????memset(next,NULL,sizeof(next));?
13?????}?
14?}*q[500001];??????????//隊列，方便用于bfs構造失敗指針
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?}

總結

以上是生活随笔為你收集整理的AC自动机算法详解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。