病毒侵袭 HDU - 2896（AC自动机）

思路：在建树的时候吧每个病毒的编号加进去，在match的时候找到对应的值，因为最多3个病毒，所以找到3个直接退出。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include<iostream>
#include<vector>
#include<queue>
//#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define SIS std::ios::sync_with_stdio(false)
#define space putchar(' ')
#define enter putchar('\n')
#define lson root<<1
#define rson root<<1|1
typedef pair<int,int> PII;
const int mod=1e9+7;
const int N=2e6+10;
const int M=1e5+10;
const int inf=0x7f7f7f7f;
const int maxx=2e5+7;

ll gcd(ll a,ll b)
{
    return b==0?a:gcd(b,a%b);
}

ll lcm(ll a,ll b)
{
    return a*(b/gcd(a,b));
}

template <class T>
void read(T &x)
{
    char c;
    bool op = 0;
    while(c = getchar(), c < '0' || c > '9')
        if(c == '-')
            op = 1;
    x = c - '0';
    while(c = getchar(), c >= '0' && c <= '9')
        x = x * 10 + c - '0';
    if(op)
        x = -x;
}
template <class T>
void write(T x)
{
    if(x < 0)
        x = -x, putchar('-');
    if(x >= 10)
        write(x / 10);
    putchar('0' + x % 10);
}
ll qsm(int a,int b,int p)
{
    ll res=1%p;
    while(b)
    {
        if(b&1) res=res*a%p;
        a=1ll*a*a%p;
        b>>=1;
    }
    return res;
}
int vis[M],check[M],rz[M];
int cnt=0,flag=0,al=0;
queue<int> que;
struct Aho
{
    struct state{
         int nex[130];
         int fail,cnt;

    }stateTable[M];
    int siz;

    void init()
    {
        while(!que.empty())que.pop();
        for(int i=0;i<M;i++)
        {
            memset(stateTable[i].nex,0,sizeof stateTable[i].nex);
            stateTable[i].fail=stateTable[i].cnt=0;
        }
        siz=1;
    }
    void insert(char *s,int index)
    {
        int n=strlen(s);
        int now=0;
        for(int i=0;i<n;i++)
        {
            char c=s[i];
            if(!stateTable[now].nex[c])
            {
                stateTable[now].nex[c]=siz++;
            }
            now=stateTable[now].nex[c];
        }
        stateTable[now].cnt++;
        vis[now]=index;
    }
    void build()
    {
        stateTable[0].fail=-1;
        que.push(0);
        while(!que.empty())
        {
            int u=que.front();
            que.pop();
            for(int i=0;i<130;i++)
            {
                if(stateTable[u].nex[i]){
                    if(u==0) stateTable[stateTable[u].nex[i]].fail=0;
                    else
                    {
                        int v=stateTable[u].fail;
                        while(v!=-1)
                        {
                            if(stateTable[v].nex[i])
                            {
                                stateTable[stateTable[u].nex[i]].fail=stateTable[v].nex[i];
                                break;
                            }
                            v=stateTable[v].fail;
                        }
                        if(v==-1)stateTable[stateTable[u].nex[i]].fail=0;


                    }
                    que.push(stateTable[u].nex[i]);
                }
            }
        }
    }
    void Get(int u,int index)
    {
        int res=0;
        while(u&&check[u]!=index)
        {
            check[u]=index;
            if(stateTable[u].cnt)
            {

                rz[al++]=vis[u];
            }
            u=stateTable[u].fail;
        }
       // return res;
    }
    void match(char *s,int index)
    {
        int n=strlen(s);
        int res=0,now=0;
        al=0;
        for(int i=0;i<n;i++)
        {
            char c=s[i];
            if(stateTable[now].nex[c])
            {
                now=stateTable[now].nex[c];
            }
            else
            {
                int p=stateTable[now].fail;
                while(p!=-1&& stateTable[p].nex[c]==0) p=stateTable[p].fail;
                if(p==-1)now=0;
                else now=stateTable[p].nex[c];

            }
            if(stateTable[now].cnt)
            {
                Get(now,index);
            }
            if(al>=3)break;

        }
        if(al!=0)
        {
            cnt++;
            printf("web %d:",index);
            sort(rz,rz+al);
            for(int i=0;i<al;i++)
                printf(" %d",rz[i]);
            printf("\n");
        }
      //  return res;
    }


}aho;


char s[N];
int main()
{

        int n;
        //aho.init();
        scanf("%d",&n);
        aho.siz=1;
        for(int i=0;i<n;i++)
        {
          scanf("%s",s);
          aho.insert(s,i+1);
        }
        aho.build();
        int k;
        scanf("%d",&k);
         cnt=0;
        for(int i=0;i<k;i++)
        {
            //memset(vis,0,sizeof vis);
            scanf("%s",s);

            aho.match(s,i+1);



        }

        printf("total: %d\n",cnt);
        //printf("%d\n",aho.match(s));




    return 0;
}
/*
1
3 2
1 1 2 3 4
1 0 1 2 3
2 1 2 3 4
*/