病毒侵袭 HDU - 2896 【AC自动机】

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
struct Trie
{
    int nxt[210*500][128],fail[210*500],ends[210*500];
    int root,L;
    int newnode()
    {
        rep(i,0,127) nxt[L][i]=-1;
        ends[L++]=-1;
        return L-1;
    }
    void init()
    {
        L=0;
        root=newnode();
    }
    void ins(char s[],int id)
    {
        int len = strlen(s);
        int now = root;
        rep(i,0,len-1)
        {
            if(nxt[now][s[i]]==-1)
            {
                nxt[now][s[i]]=newnode();
            }
            now = nxt[now][s[i]];
        }
        ends[now]=id;
    }
    void build()
    {
        queue<int>q;
        fail[root]=root;
        rep(i,0,127)
        {
            if(nxt[root][i]==-1)
            {
                nxt[root][i] = root;
            }
            else
            {
                fail[nxt[root][i]]=root;
                q.push(nxt[root][i]);
            }
        }
        while(!q.empty())
        {
            int now =q.front();
            q.pop();
            for(int i=0;i<128;i++)
            {
                if(nxt[now][i]==-1)
                {
                    nxt[now][i]=nxt[fail[now]][i];
                }
                else
                {
                    fail[nxt[now][i]]=nxt[fail[now]][i];
                    q.push(nxt[now][i]);
                }
            }
        }
    }
    bool used[510];/*



    */
    bool query(char buf[],int n,int id)
    {
        int len = strlen(buf);
        int now = root;
        memset(used,false,sizeof(used));
        bool flag=false;
        for(int i=0;i<len;i++)
        {
            now = nxt[now][buf[i]];
            int tmp = now;
            while(tmp!=root)
            {
                if(ends[tmp]!=-1)
                {
                    used[ends[tmp]]=true;
                    flag=true;
                }
                tmp = fail[tmp];
            }
        }
        if(!flag) return false;
        printf("web %d:",id);
        rep(i,1,n) if(used[i]) printf(" %d",i);
        printf("\n");
        return true;
    }
};
char buf[10010];
Trie ac;
int n,m;
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        ac.init();
        rep(i,1,n) {scanf("%s",buf);ac.ins(buf,i);};
        ac.build();
        int ans =0;
        scanf("%d",&m);
        rep(i,1,m)
        {
            scanf("%s",buf);
            if(ac.query(buf,n,i)) ans++;
        }
        printf("total: %d\n",ans);
    }

    return 0;
}