首页 > 代码库 > HDU 2222 Keywords Search
HDU 2222 Keywords Search
题意:要你求出给定的单词表在一个字符串中出现了几个单词
思路:没学AC自动机之前,用KMP做了一下,果断超时。后来问了一下朋友,才知道要用AC自动机。涨姿势了
http://blog.csdn.net/u012313382/article/details/38541509
本题就是一道AC自动机的模板题
AC代码:
#include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #include<queue> using namespace std; struct node { node *next[26],*fail; int count; node() { fail=NULL; count=0; memset(next,0,sizeof(next)); } }; queue<node*> q; char word[60],str[1000002]; int ins(char *str,node *root) { node *p=root; int i=0,index; while(str[i]) { index=str[i]-'a'; if(!p->next[index]) p->next[index]=new node(); p=p->next[index]; i++; } p->count++; return 0; } int build(node *root) { root->fail=NULL; q.push(root); while (!q.empty()) { node *p=NULL; node *temp=q.front(); q.pop(); for(int i=0;i<26;i++) if(temp->next[i]) { if(temp==root) temp->next[i]->fail=root; else { p=temp->fail; 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.push(temp->next[i]); } } return 0; } int query(node *root) { int i=0,cut=0,index; node *p=root; while(str[i]) { index=str[i]-'a'; while (!p->next[index] && p!=root) p=p->fail; p=p->next[index]; p=(p==NULL)?root:p; node *temp=p; while(temp!=root && temp->count!=-1) { cut+=temp->count; temp->count=-1; temp=temp->fail; } i++; } return cut; } int main() { int t; scanf("%d",&t); while(t--) { node *root=new node(); int n; scanf("%d\n",&n); for(int i=1;i<=n;i++) { gets(word); ins(word,root); } build(root); scanf("%s",str); printf("%d\n",query(root)); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。