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;
}