HDUnbsp;3065nbsp;病毒侵袭持续中（AC自动…

本文主要是介绍HDUnbsp;3065nbsp;病毒侵袭持续中（AC自动…，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3065

分析见上一篇博客

直接附代码：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

typedef struct point{
int count;
struct point *fail,*next[26];
}*Tree,Node;
Tree root,Q[50008];
char str[2000008];
int num[1008];

Tree NEW()
{
int i;
Tree p;
p=(Tree)malloc(sizeof(Node));
for(i=0;i<26;i++)
p->next[i]=NULL;
p->fail=NULL;
p->count=-1;
return p;
}

void Build(char ss[],int u)
{
int i=0;
Tree p,s;
p=root;
while(ss[i])
{
if(p->next[ss[i]-'A']==NULL)
{
s=NEW();
p->next[ss[i]-'A']=s;
p=s;
}
else p=p->next[ss[i]-'A'];
i++;
}
p->count=u;

}

void AC_Automation()
{
int i,front=0,rear=0;
Tree p,temp;
root->fail=NULL;
Q[front++]=root;
while(rear<front)
{
temp=Q[rear++];
p=NULL;
for(i=0;i<26;i++)
{
if(temp->next[i]!=NULL)
{
if(temp==root)temp->next[i]->fail=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[front++]=temp->next[i];
}
}
}
}

void search()
{
int i=0;
Tree p=root,temp;
memset(num,0,sizeof(num));
while(str[i])
{
if(str[i]>='A' && str[i]<='Z')
{
while(p->next[str[i]-'A']==NULL && p!=root)p=p->fail;

p=p->next[str[i]-'A'];
if(p==NULL)p=root;
temp=p;
while(temp!=root)
{
if(temp->count>=0)
num[temp->count]++;
temp=temp->fail;
}
}
else p=root;
i++;
}
}

int main()
{
int n,i;
char ss[1008][55];
while(scanf("%d",&n)!=EOF)
{
root=NEW();
for(i=0;i<n;i++)
{
scanf("%s",ss[i]);
Build(ss[i],i);
}
AC_Automation();
getchar();
gets(str);
search();
for(i=0;i<n;i++)
if(num[i]!=0)
printf("%s: %d\n",ss[i],num[i]);
}
return 0;
}