最近一直在學習字符串之類的算法，感覺BF算法，雖然很容易理解，但是容易超時，所有就想學習其他的一些字符串算法來提高一下，最近學習了一下AC自動機，雖然感覺有所收獲，但是還是有些朦胧的感覺，在此總結一下，希望大家指教。
一、AC自動機的原理：
Aho-Corasick automaton，該算法在1975年產生於貝爾實驗室，是著名的多模匹配算法之一。一個常見的例子就是給出N個單詞，在給出一段包含m個字符的文章，讓你找出有多少個單詞在這文章中出現過，。要搞懂AC自動機，先的有字典樹和KMP模式匹配算法的基礎知識。
二、AC自動機算法的實現步驟（三步）
AC自動機的存儲數據結構
const int MAXN = 10000000;
struct node
{
int count; //是否為單詞最後一個節點
node *next[26];//Trie每個節點的26個子節點
node *fail; //失敗指針
};
node *q[MAXN]; //隊列，采用bfs 構造失敗指針
char keyword[55];//輸入單詞 模式串
char str[1000010];// 需要查找的 主串
int head,tail;//隊列 頭尾指針
1、構造一棵Trie樹
首先我們需要建立一棵Trie。但是這棵Trie不是普通的Trie，而是帶有一些特殊的性質。
首先會有3個重要的指針，分別為p, p->fail, temp。
1.指針p，指向當前匹配的字符。若p指向root，表示當前匹配的字符序列為空。（root是Trie入口，沒有實際含義）。
2.指針p->fail，p的失敗指針，指向與字符p相同的結點，若沒有，則指向root。
3.指針temp，測試指針（自己命名的，容易理解！~），在建立fail指針時有尋找與p字符匹配的結點的作用，在掃描時作用最大，也最不好理解。
對於Trie樹中的一個節點，對應一個序列s[1...m]。此時，p指向字符s[m]。若在下一個字符處失配，即p->next[s[m+1]] == NULL，則由失配指針跳到另一個節點(p->fail)處，該節點對應的序列為s[i...m]。若繼續失配，則序列依次跳轉直到序列為空或出現匹配。在此過程中，p的值一直在變化，但是p對應節點的字符沒有發生變化。在此過程中，我們觀察可知，最終求得得序列s則為最長公共後綴。另外，由於這個序列是從root開始到某一節點，則說明這個序列有可能是某些序列的前綴。
再次討論p指針轉移的意義。如果p指針在某一字符s[m+1]處失配(即p->next[s[m+1]] == NULL)，則說明沒有單詞s[1...m+1]存在。此時，如果p的失配指針指向root，則說明當前序列的任意後綴不會是某個單詞的前綴。如果p的失配指針不指向root，則說明序列s[i...m]是某一單詞的前綴，於是跳轉到p的失配指針，以s[i...m]為前綴繼續匹配s[m+1]。
對於已經得到的序列s[1...m]，由於s[i...m]可能是某單詞的後綴，s[1...j]可能是某單詞的前綴，所以s[1...m]中可能會出現單詞。此時，p指向已匹配的字符，不能動。於是，令temp = p，然後依次測試s[1...m], s[i...m]是否是單詞。
構造的Trie為：
實現代碼：
void insert(char *word,node *root)
{
int index,len;
node *p = root,*newnode;
len = strlen(word);
for(int i=0 ;i < len ; i++ )
{
index=word[i]-'a';
if(!p->next[index])//該字符節點不存在，加入Trie樹中
{
// 初始化 newnode 並 加入 Trie 樹
newnode=(struct node *)malloc(sizeof(struct node));
for(int j=0;j<26;j++)
newnode->next[j]=0;
newnode->count=0;
newnode->fail=0;
p->next[index]=newnode;
}
p=p->next[index];//指針移動至下一層
}
p->count++; //單詞結尾 節點 count + 1 做標記
}
2、構造失敗指針
構造失敗指針的過程概括起來就一句話：設這個節點上的字母為x，沿著他父親的失敗指針走，直到走到一個節點，他的兒子中也有字母為x的節點。然後把當前節點的失敗指針指向那個字符也為x的兒子。如果一直走到了root都沒找到，那就把失敗指針指向root。
有兩個規則：
root的子節點的失敗指針都指向root。
節點(字符為x)的失敗指針指向：從X節點的父節點的fail節點回溯直到找到某節點的子節點也是字符x，沒有找到就指向root。
如下圖
實現代碼：
void build_ac_automation(node *root)
{
head=0;
tail=1;
q[head]=root;
node *temp,*p;
while(headnext[i])//判斷實際存在的節點
{
// root 下的第一層 節點 的 失敗指針都 指向root
if(temp==root)
temp->next[i]->fail=root;
else
{
//依次回溯 該節點的父節點的失敗指針
//直到某節點的next[i]與該節點相同，則
//把該節點的失敗指針指向該next[i]節點
//若回溯到 root 都沒有找到，則該節點
//的失敗指針 指向 root
p=temp->fail;//temp 為節點的父指針
while(p)
{
if(p->next[i])
{
temp->next[i]->fail=p->next[i];
break;
}
p=p->fail;
}
if(!p)temp->next[i]->fail=root;
}
//每處理一個點，就把它的所有兒子加入隊列，
//直到隊列為空
q[tail++]=temp->next[i];
}
}
}
}
3、模式匹配過程
從root節點開始，每次根據讀入的字符沿著自動機向下移動。當讀入的字符，在分支中不存在時，遞歸走失敗路徑。如果走失敗路徑走到了root節點， 則跳過該字符，處理下一個字符。因為AC自動機是沿著輸入文本的最長後綴移動的，所以在讀取完所有輸入文本後，最後遞歸走失敗路徑，直到到達根節點， 這樣可以檢測出所有的模式。
搜索的步驟:
從根節點開始一次搜索；
取得要查找關鍵詞的第一個字符，並根據該字符選擇對應的子樹並轉到該子樹繼續進行檢索；
在相應的子樹上，取得要查找關鍵詞的第二個字符,並進一步選擇對應的子樹進行檢索。
迭代過程……
在某個節點處，關鍵詞的所有字符已被取出，則讀取附在該節點上的信息，即完成查找。
匹配模式串中出現的單詞。當我們的模式串在Trie上進行匹配時，如果與當前節點的關鍵字不能繼續匹配的時候，
就應該去當前節點的失敗指針所指向的節點繼續進行匹配。
匹配過程出現兩種情況：
當前字符匹配，表示從當前節點沿著樹邊有一條路徑可以到達目標字符， 此時只需沿該路徑走向下一個節點繼續匹配即可 ，目標字符串指針移向下個字符繼續匹配；
當前字符不匹配，則去當前節點失敗指針所指向的字符繼續匹配，匹配過程隨著指針指向root結束。
重復這2個過程中的任意一個，直到模式串走到結尾為止。
實現代碼：
int query(node *root)//類似於 kmp算法。
{//i為主串指針，p為匹配串指針
int i,cnt=0,index,len=strlen(str);
node *p=root;
for(i=0; i < len ;i ++)
{
index=str[i]-'a';
//由失敗指針回溯尋找，判斷str[i]是否存在於Trie樹中
while( !p->next[index] && p != root)
{
p=p->fail;
}
p=p->next[index];//找到後 p 指向該節點
//指針回為空，則沒有找到與之匹配的字符
if(!p)
{
p=root;//指針重新回到根節點root，下次從root開始搜索Trie樹
}
node *temp=p;//匹配該節點後，沿其失敗指針回溯，判斷其他節點是否匹配
while(temp != root )//匹配 結束控制
{
if(temp->count>=0)//判斷 該節點是否被訪問
{
//統計出現的單詞個數cnt，由於節點不是單詞結尾時count為0，
//故 cnt+=temp->count; 只有 count >0時才真正統計了單詞個數
cnt+=temp->count;
temp->count=-1; //標記已訪問
}
else
break;//節點已訪問，退出循環
temp=temp->fail;//回溯失敗指針繼續尋找下一個滿足條件的節點
}
}
return cnt;
}
三、AC自動機模板
