HDUnbsp;2896nbsp;病毒侵袭（AC自动机）

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

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

AC自动机一枚，不解释，分析看前面文章

附上代码：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<iostream>
using namespace std;

typedef struct point{
int count;
struct point *next[94],*fail;
}*Tree,Node;

int data[3],num;
Tree root;
char str[10001];

int cmp(const void *a,const void *b)
{
return *(int *)a-*(int *)b;
}

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

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

void AC_Automation()
{
int i;
Tree p,temp;
queue<Tree> Q;
Q.push(root);
while(!Q.empty())
{
temp=Q.front();
Q.pop();
p=NULL;
for(i=0;i<94;i++)
{
if(temp->next[i]!=NULL)
{
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.push(temp->next[i]);
}
}
}
}

int search()
{
int k=0,i=0;
Tree p=root,temp;
while(str[i])
{
while(p->next[str[i]-32]==NULL && p!=root)p=p->fail;
p=p->next[str[i]-32];
if(p==NULL)p=root;
temp=p;
while(temp!=root)
{
if(temp->count!=0)
{
data[k++]=temp->count;
}
temp=temp->fail;
}
i++;
}
return k;
}

int main()
{
int i,j,k,n,m,sum;
char ss[201];
while(scanf("%d",&n)!=EOF)
{
root=NEW();
sum=0;
for(i=1;i<=n;i++)
{
scanf("%s",ss);
Build(ss,i);
}
AC_Automation();
scanf("%d",&m);
getchar();
for(i=1;i<=m;i++)
{
gets(str);
k=search();
qsort(data,k,sizeof(data[0]),cmp);
if(k>0)
{
sum++;
printf("web %d:",i);
for(j=0;j<k;j++)
printf(" %d",data[j]);
printf("\n");
}
}
printf("total: %d\n",sum);
}
return 0;
}