本文共 1581 字，大约阅读时间需要 5 分钟。
AC自动机
代码：
#include #include #include #include #include #include #include #include #include #include #include #define LL long longusing namespace std;const int INF=0x3f3f3f3f;const int N=1005;const int M=505;const int K=26;struct nodeTrie{ nodeTrie() { v=0; fail=NULL; for(int i=0;i next[s[i]-'A']==NULL) p->next[s[i]-'A']=new nodeTrie; p=p->next[s[i]-'A']; } (p->v)=k;}void init(int n){ root=new nodeTrie; for(int i=1;i<=n;++i) { gets(s[i]); addWord(root,s[i],i); }}void bfs(nodeTrie *p){ p->fail=root; queue qt; qt.push(p); while(!qt.empty()) { nodeTrie *y; nodeTrie *x=qt.front();qt.pop(); for(int i=0;i next[i]!=NULL) { qt.push(x->next[i]); if(x==root) {x->next[i]->fail=root;continue;} y=x->fail; while(y!=root&&y->next[i]==NULL) y=y->fail; if(y->next[i]!=NULL) x->next[i]->fail=y->next[i]; else x->next[i]->fail=root; } }}int match(nodeTrie *p,char *s){ int wordCount=0; int l=0; while(s[l]!='\0') { if(s[l]<'A'||s[l]>'Z') {p=root;++l;continue;} while(p->next[s[l]-'A']==NULL&&p!=root) p=p->fail; if(p->next[s[l]-'A']!=NULL) p=p->next[s[l]-'A']; ++l; nodeTrie *fp=p; while(fp!=root) { if((fp->v)>0) ++num[fp->v]; fp=fp->fail; } } return wordCount;}int main(){ //freopen("data.in","r",stdin); int n; while(scanf("%d ",&n)!=EOF) { init(n); bfs(root); gets(web); memset(num,0,sizeof(num)); match(root,web); for(int i=1;i<=n;++i) if(num[i]>0) printf("%s: %d\n",s[i],num[i]); } return 0;}
转载于:https://www.cnblogs.com/liulangye/archive/2013/03/22/2975950.html