HDU 3065 病毒侵袭持续中（AC自动机（每个模式串出现次数））

http://acm.hdu.edu.cn/showproblem.php?pid=3065

题意：
求每个模式串出现的次数。

思路：

不难，把模板修改一下即可。

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<vector>

 #include<stack>

 #include<queue>

 #include<cmath>

 #include<map>

 #include<set>

 using namespace std;

 typedef long long ll;

 const int INF = 0x3f3f3f3f;

 const int maxn=+;

 int n;

 int num;

 char str[][];

 char s[];

 int ans[];

 struct Trie

 {

     int son[];

     int cnt;

     int id;

     int fail;

 }t[*+];

 void init(int x)

 {

     t[x].cnt=t[x].fail=;

     memset(t[x].son,,sizeof(t[x].son));

 }

 void trie(char *s, int id)

 {

     int n=strlen(s);

     int x=;

     for(int i=;i<n;i++)

     {

         int c=s[i]-'A'+;

         if(!t[x].son[c])

         {

             num++;

             init(num);

             t[x].son[c]=num;

         }

         x=t[x].son[c];

     }

     t[x].cnt++;

     t[x].id=id;

 }

 void buildAC()

 {

     queue<int> Q;

     for(int i=;i<=;i++)  if(t[].son[i])  Q.push(t[].son[i]);

     while(!Q.empty())

     {

         int x=Q.front(); Q.pop();

         int fail=t[x].fail;

         for(int i=;i<=;i++)

         {

             int y=t[x].son[i];

             if(y)

             {

                 t[y].fail=t[fail].son[i];

                 Q.push(y);

             }

             else t[x].son[i]=t[fail].son[i];

         }

     }

 }

 void query(char *s)

 {

     int n=strlen(s);

     int x=;

     for(int i=;i<n;i++)

     {

         if(!(s[i]>='A' && s[i]<='Z'))  {x=;continue;}

         int c=s[i]-'A'+;

         while(x && !t[x].son[c])  x=t[x].fail;

         x=t[x].son[c];

         int tmp=x;

         while(tmp)  //回到0就不需要再计数了

         {

             if(t[tmp].cnt!=) ans[t[tmp].id]++;

             tmp=t[tmp].fail;

         }

     }

 }

 int main()

 {

     //freopen("in.txt","r",stdin);

     while(~scanf("%d",&n))

     {

         num=;

         init();

         scanf("%d",&n);

         for(int i=;i<=n;i++)

         {

             ans[i]=;

             scanf("%s",str[i]);

             trie(str[i],i);

         }

         buildAC();

         scanf("%s",s);

         query(s);

         for(int i=;i<=n;i++)

         {

             if(ans[i]) printf("%s: %d\n",str[i],ans[i]);

         }

     }

     return ;

 }