AC自动机算法分为3步:构造Trie树,构造失败指针和模式匹配过程。
AC自动机原理:http://blog.csdn.net/niushuai666/article/details/7002823
题目:http://acm.hdu.edu.cn/showproblem.php?pid=2222
题目大意:给你很多个单词,然后给你一篇文章,问给出的单词在文章中出现的次数。
#include <iostream> #include <string.h> #include <stdio.h> #include <queue> using namespace std; const int N=500010; char S[1000010]; char keyword[51]; class Trie { public: int count; Trie *fail; Trie *next[26]; Trie() { count=0; fail=NULL; memset(next,NULL,sizeof(next)); } }; Trie *root; queue<Trie*> Q; void Insert(char *S) { int len=strlen(S); Trie *p=root; for(int i=0; i<len; i++) { int id=S[i]-'a'; if(p->next[id]==NULL) p->next[id]=new Trie(); p=p->next[id]; } p->count++; } void Build_AC() { Q.push(root); root->fail=NULL; while(!Q.empty()) { Trie *p=NULL; Trie *tmp=Q.front(); Q.pop(); for(int i=0; i<26; i++) { if(tmp->next[i]) { if(tmp==root) tmp->next[i]->fail=root; else { p=tmp->fail; while(p) { if(p->next[i]) { tmp->next[i]->fail=p->next[i]; break; } p=p->fail; } if(p==NULL) tmp->next[i]->fail=root; } Q.push(tmp->next[i]); } } } } int Query() { Trie *p=root; int index,result=0; int len=strlen(S); for(int i=0; i<len; i++) { index=S[i]-'a'; while(p->next[index]==NULL&&p!=root) p=p->fail; p=p->next[index]; if(p==NULL) p=root; Trie *temp=p; while(temp!=root&&temp->count!=-1) { result+=temp->count; temp->count=-1; temp=temp->fail; } } return result; } int main() { int t,n; scanf("%d",&t); while(t--) { root=new Trie(); scanf("%d",&n); getchar(); while(n--) { gets(keyword); Insert(keyword); } Build_AC(); scanf("%s",S); printf("%d\n",Query()); } return 0; }