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

病毒侵袭持续中

num数组记录的还是病毒id，vis数组记录的是病毒出现的次数,多组输入。字典树的大小是字符长度乘以个数 （搞了半天超内存）

#include<bits/stdc++.h>
using namespace std;
const int M=50005;
char s[1010][60];
int tree[M][128];
int num[M];
int fail[M];
int pos;
int vis[1100];
char str[2000100];
void insert(char *s,int cnt)
{
    int len=strlen(s);
    int root=0;
    for(int i=0; i<len; i++)
    {
        int x=s[i];
        if(!tree[root][x])
        {
            tree[root][x]=pos;
            pos++;
        }
        root=tree[root][x];
    }
    num[root]=cnt;
}
void getfail( )
{
    queue<int>qu;
    for(int i=0; i<128; i++)
    {
        if(tree[0][i])
        {
            fail[tree[0][i]]=0;
            qu.push(tree[0][i]);
        }
    }
    while(!qu.empty( ))
    {
        int u=qu.front( );
        qu.pop( );
        for(int i=0; i<128; i++)
        {
            if(tree[u][i])
            {
                fail[tree[u][i]]=tree[fail[u]][i];
                qu.push(tree[u][i]);
            }
            else
            {
                tree[u][i]=tree[fail[u]][i];
            }

        }
    }
}
void query(char *s)
{
    int len=strlen(s);
    int root=0;
    for(int i=0; i<len; i++)
    {
        int x=s[i];
        root=tree[root][x];
        for(int j=root; j&&num[j]; j=fail[j])
        {
            vis[num[j]]++;
        }
    }
}
int main( )
{
    int n;
    while(~scanf("%d",&n))
    {
        pos=1;
        memset(fail,0,sizeof(fail));
        memset(tree,0,sizeof(tree));
        memset(vis,0,sizeof(vis));
        memset(num,0,sizeof(num));
        for(int i=1; i<=n; i++)
        {
           scanf("%s",s[i]);
            insert( s[i] , i);
        }
        fail[0]=0;
        getfail( );
        scanf("%s",str);
        query(str);
        for(int i=1; i<=n; i++)
        {
            if(vis[i]!=0)
            {
                printf("%s: %d\n",s[i],vis[i]);
            }
        }
    }
    return 0;

}