HDU-2896-病毒入侵(AC自动机）

病毒入侵

注意：这个病毒是ASCII码可见字符，不仅仅是小写字母。(卡了半天）

#include<bits/stdc++.h>
using namespace std;
const int M=101000;
int tree[M][128];
int num[M];
int fail[M];
char s[M];
int pos=1;
int vis[M];
priority_queue<int,vector<int>,greater<int> >q;
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)
{
    memset(vis,0,sizeof(vis));
    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])
        {
            if(vis[num[j]]==0)//防止病毒序号重复记录
            {
                q.push(num[j]);
                vis[num[j]]=1;
            }
            
        }
    }
}
int main( )
{
    int n,m,cnt=0;
    scanf("%d",&n);
    getchar( );
    while(n--)
    {
        cnt++;
        scanf("%s",s);
        insert(s,cnt);
    }
    fail[0]=0;
    getfail( );
    scanf("%d",&m);
    getchar( );
    cnt=0;
    int ans=0;
    while(m--)
    {
        cnt++;
        while(!q.empty( ))
        {
            q.pop( );
        }
        scanf("%s",s);
        query(s);
        if(!q.empty( ))
        {
            ans++;
            printf("web %d:",cnt);
            while(!q.empty( ))
            {
                printf(" %d",q.top( ));
                q.pop( );
            }
            printf("\n");
        }
    }
    printf("total: %d\n",ans);
    return 0;
}