HDU 3065 病毒侵袭持续中 AC自动机

#include<cstdio>
#include<cstring>
#define N 55
#define M 2000005
using namespace std;
inline void read(char *s)
{
    char ch=getchar();
    while(ch<'A'||ch>'Z')ch=getchar();
    int len=0;
    while(ch>='A'&&ch<='Z')
    {
      s[len++]=ch;
      ch=getchar();
    }
}
char c[1005][N];
char w[M];
int n;
int sum[1005];
struct Trie
{
    Trie *ch[26],*last,*fail;
    int who;
    Trie()
    {
      memset(ch,0,sizeof(ch));
      last=fail=NULL;
      who=0;
    }
}*root,*q[1005*N];
inline void insert(char *s,int x)
{
    Trie *now=root;
    int len=strlen(s);
    for(int i=0;i<len;i++)
    {
      if(now->ch[s[i]-'A']==NULL)
       now->ch[s[i]-'A']=new Trie();
      now=now->ch[s[i]-'A'];
    }
    now->who=x;
}
inline void build()
{
    q[0]=root;
    for(int i=0,j=0;i<=j;i++)
     for(int l=0;l<26;l++)
      if(q[i]->ch[l])
      {
         Trie *now=q[i]->fail;
         while(now&&!now->ch[l])now=now->fail;
         q[++j]=q[i]->ch[l];
         q[j]->fail=now?now->ch[l]:root;
         q[j]->last=q[j]->fail->who?q[j]->fail:q[j]->fail->last;
      }
      else
       q[i]->ch[l]=q[i]==root?root:q[i]->fail->ch[l];
}
inline void pre()
{
    root=new Trie();
    memset(sum,0,sizeof(sum));
    for(int i=1;i<=n;i++)
    {
      scanf("%s",c[i]);
      insert(c[i],i);
    }
    build();
}
inline void work()
{
    scanf("%s",w);
    int len=strlen(w);
    Trie *now=root;
    for(int i=0;i<len;i++)
    {
       if(w[i]<'A'||w[i]>'Z')
       {
          now=root;
          continue;
       }
       now=now->ch[w[i]-'A'];
       if(now->who)sum[now->who]++;
       for(Trie *Now=now->last;Now;Now=Now->last)
        sum[Now->who]++;
    }
}
inline void print()
{
   for(int i=1;i<=n;i++)
   {
     if(!sum[i])continue;
     printf("%s: %d
",c[i],sum[i]);
   }
}
int main()
{
   while(scanf("%d",&n)==1)
   {
       pre();
       work();
       print();
   }
   return 0;
}