首页 > 代码库 > HDU 3065 病毒侵袭持续中 (AC自动机)
HDU 3065 病毒侵袭持续中 (AC自动机)
中文题不解释
Sample Input
3 AA BB CC ooxxCC%dAAAoen....END
Sample Output
AA: 2 CC: 1
#include<stdio.h> #include<string.h> #include<queue> #include<algorithm> #include<iostream> using namespace std; const int kind = 26; const int M = 1005; struct node { node *fail; node *next[kind]; int count; node() { fail = NULL; count = 0; memset(next,0,sizeof(next)); } }*q[50*M]; char keyword[1005][55],str[2000010]; int head,tail; void insert(char *str,node *root,int num) { node *p=root; int i=0,index; while(str[i]) { index = str[i] - 'A'; if(p->next[index]==NULL) p->next[index] = new node(); p = p->next[index]; i++; } p->count=num; } void build_ac(node *root) { int i; root->fail=NULL; q[head++]=root; while(head!=tail) { node *temp = q[tail++]; node *p=NULL; for(i=0;i<kind;i++) { if(temp->next[i]!=NULL) { if(temp==root) temp->next[i]->fail=root;//失败指针指向root else { p = temp->fail; while(p!=NULL) { if(p->next[i]!=NULL) { temp->next[i]->fail=p->next[i]; break; } p=p->fail; } if(p==NULL) temp->next[i]->fail=root; } q[head++]=temp->next[i]; } } } } int vis[1005]; void query(char *str,node *root) { int i=0,cnt=0,index,len=strlen(str); node *p=root; while(str[i]) { if(str[i]<'A'||str[i]>'Z') { p=root; i++; continue; } index = str[i]-'A'; while(p->next[index]==NULL&&p!=root) p = p->fail; p=p->next[index]; p=(p==NULL)?root:p; node *temp = p; while(temp!=root) { vis[temp->count]++; temp=temp->fail; } i++; } } int main() { int n,m; while(~scanf("%d",&n)) { head=tail=0; node *root = new node(); getchar(); for(int i=1;i<=n;i++) { gets(keyword[i]); insert(keyword[i],root,i); } build_ac(root); scanf("%s",str); memset(vis,0,sizeof(vis)); query(str,root); for(int i=1;i<=n;i++) if(vis[i]) printf("%s: %d\n",keyword[i],vis[i]); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。