最近一直在學習字符串之類的算法,感覺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自動機模板
#include#include #include #define kind 26 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;//隊列 頭尾指針 node *root; 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 做標記 } void build_ac_automation(node *root) { head=0; tail=1; q[head]=root; node *temp,*p; while(head next[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]; } } } } 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; } int main() { int i,t,n,ans; scanf("%d",&t); while(t--) { root=(struct node *)malloc(sizeof(struct node)); for(int j=0;j<26;j++) root->next[j]=0; root->fail=0; root->count=0; scanf("%d",&n); getchar(); for(i=0;i