AC自動機是一種多模式匹配的算法。大概過程如下：

• 首先所有模式串構造一棵Trie樹，Trie樹上的每個非根結點都代表一個從根出發到該點路徑的字符串。

• 然后每個結點都計算出其fail指針的值，這個fail指針就指向這個結點所表示字符串的最長存在的后綴所對應的結點，如果不存在就指向根：計算每個結點的fail用BFS，比如當前結點u出隊要拓展并計算其孩子結點的fail，v是其第k個孩子，fail[v]的值就是某個fail[fail[fail...[u]]]存在第k孩子結點其第k個孩子結點，如果不存在fail[v]就等于root。

• 最后主串就往Trie樹上跑，在某個Trie樹結點失配了就跳轉到這個結點fail指針所指的結點繼續跑——不過如果匹配了某個模式串這時可能某個模式串的后綴串被忽略了，所以需要用到temp指針，去檢查是否有遺漏后綴沒匹配。

?

而這題大概就是給幾個模式串，一個主串，問有幾個模式串被主串匹配。

AC自動機的模板題。有個可以優化的地方就是某個模式串被匹配了，下一次經過這兒就可以跳過了temp指針的過程了。

?

代碼參考自kuangbin巨的博客，太簡潔了（300+ms）：

1 #include<cstdio> 2 #include<cstring> 3 #include<queue> 4 using namespace std; 5 int tn,ch[510000][26],cnt[510000],fail[510000]; 6 void insert(char *s){ 7 int x=0; 8 for(int i=0; s[i]; ++i){ 9 int y=s[i]-'a'; 10 if(ch[x][y]==0) ch[x][y]=++tn; 11 x=ch[x][y]; 12 } 13 ++cnt[x]; 14 } 15 void init(){ 16 memset(fail,0,sizeof(fail)); 17 queue<int> que; 18 for(int i=0; i<26; ++i){ 19 if(ch[0][i]) que.push(ch[0][i]); 20 } 21 while(!que.empty()){ 22 int x=que.front(); que.pop(); 23 for(int i=0;i<26;++i){ 24 if(ch[x][i]) que.push(ch[x][i]),fail[ch[x][i]]=ch[fail[x]][i]; 25 else ch[x][i]=ch[fail[x]][i]; 26 } 27 } 28 } 29 int query(char *s){ 30 int x=0,res=0; 31 for(int i=0; s[i]; ++i){ 32 int tmp=x=ch[x][s[i]-'a']; 33 while(tmp){ 34 if(cnt[tmp]>=0){ 35 res+=cnt[tmp]; 36 cnt[tmp]=-1; 37 }else break; 38 tmp=fail[tmp]; 39 } 40 } 41 return res; 42 } 43 char S[1100000],T[55]; 44 int main(){ 45 int t,n; 46 scanf("%d",&t); 47 while(t--){ 48 tn=0; 49 memset(ch,0,sizeof(ch)); 50 memset(cnt,0,sizeof(cnt)); 51 scanf("%d",&n); 52 while(n--){ 53 scanf("%s",T); 54 insert(T); 55 } 56 init(); 57 scanf("%s",S); 58 printf("%d\n",query(S)); 59 } 60 return 0; 61 }

?

?

另外之前學的指針版本的，指針版本跑得更快（200+ms）：

1 #include<cstdio> 2 #include<cstring> 3 #include<queue> 4 using namespace std; 5 typedef struct Node *pNode; 6 struct Node{ 7 int cnt; 8 pNode fail,nxt[26]; 9 Node(){ 10 cnt=0; fail=NULL; 11 for(int i=0;i<26;++i) nxt[i]=NULL; 12 } 13 }; 14 pNode root; 15 char S[1000100]; 16 void insert(char *s){ 17 pNode p=root; 18 for(int i=0;s[i];++i){ 19 int index=s[i]-'a'; 20 if(p->nxt[index]==NULL){ 21 p->nxt[index]=new Node; 22 } 23 p=p->nxt[index]; 24 } 25 ++p->cnt; 26 } 27 void init(){ 28 queue<pNode> que; 29 que.push(root); 30 while(que.size()){ 31 pNode y=que.front(); que.pop(); 32 for(int i=0;i<26;++i){ 33 if(y->nxt[i]==NULL) continue; 34 if(y==root){ 35 y->nxt[i]->fail=root; 36 que.push(y->nxt[i]); 37 continue; 38 } 39 pNode x=y->fail; 40 while(x&&x->nxt[i]==NULL) x=x->fail; 41 if(x==NULL) y->nxt[i]->fail=root; 42 else y->nxt[i]->fail=x->nxt[i]; 43 que.push(y->nxt[i]); 44 } 45 } 46 } 47 int query(){ 48 int res=0; 49 pNode x=root; 50 for(int i=0;S[i];++i){ 51 int index=S[i]-'a'; 52 while(x->nxt[index]==NULL&&x!=root) x=x->fail; 53 x=x->nxt[index]; 54 if(x==NULL) x=root; 55 pNode y=x; 56 while(y!=root){ 57 if(y->cnt>=0){ 58 res+=y->cnt; 59 y->cnt=-1; 60 }else break; 61 y=y->fail; 62 } 63 } 64 return res; 65 } 66 int main(){ 67 int t,n; 68 char s[55]; 69 scanf("%d",&t); 70 while(t--){ 71 root=new Node; 72 scanf("%d",&n); 73 for(int i=0;i<n;++i){ 74 scanf("%s",s); 75 insert(s); 76 } 77 scanf("%s",S); 78 init(); 79 printf("%d\n",query()); 80 } 81 return 0; 82 }

?

轉載于:https://www.cnblogs.com/WABoss/p/5164457.html

總結

以上是生活随笔為你收集整理的HDU2222 Keywords Search（AC自动机模板）的全部內容，希望文章能夠幫你解決所遇到的問題。

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