病毒侵袭持续中 HDU - 3065（AC自动机求串出现次数）

思路：和上一个病毒侵袭差不多，用个vis记录一下第几个病毒，在insert的时候初始化子节点。

#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[26];
         int fail,cnt;

    }stateTable[M];
    int siz;

    void init()
    {
        while(!que.empty())que.pop();
        memset(stateTable[0].nex,0,sizeof stateTable[0].nex);
        stateTable[0].fail=0;
        stateTable[0].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-'A'])
            {
                stateTable[now].nex[c-'A']=siz++;
                memset(stateTable[stateTable[now].nex[c-'A']].nex,0,sizeof stateTable[stateTable[now].nex[c-'A']].nex);
                stateTable[stateTable[now].nex[c-'A']].fail=stateTable[stateTable[now].nex[c-'A']].cnt=0;
            }
            now=stateTable[now].nex[c-'A'];
        }
        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<26;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 res=0;
        while(u)
        {


            if(stateTable[u].cnt)
            {

                rz[vis[u]]++;
            }
            u=stateTable[u].fail;
        }
       // return res;
    }
    void match(char *s)
    {
        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-'A'])
            {
                now=stateTable[now].nex[c-'A'];
            }
            else
            {
                int p=stateTable[now].fail;
                while(p!=-1&& stateTable[p].nex[c-'A']==0) p=stateTable[p].fail;
                if(p==-1)now=0;
                else now=stateTable[p].nex[c-'A'];

            }
            if(stateTable[now].cnt)
            {
                Get(now);
            }


        }

    }


}aho;


char s[N],tmp[N],mp[1005][55];

int main()
{

        int n;

        while(~scanf("%d",&n))
        {
            aho.siz=1;
            aho.init();
            memset(rz,0,sizeof rz);
        for(int i=0;i<n;i++)
        {
          scanf("%s",mp[i]);
          aho.insert(mp[i],i+1);
        }
        aho.build();
        scanf("%s",s);
        int len=strlen(s);
        int pos=0;
        for(int i=0;i<=len;i++)//要等于len不然最后一个字符串不会匹配
        {
            if(s[i]>='A'&&s[i]<='Z')
                tmp[pos++]=s[i];
            else
            {
                tmp[pos]='\0';
                aho.match(tmp);
                pos=0;
            }
        }
        for(int i=1;i<=n;i++)
        {
            if(rz[i])printf("%s: %d\n",mp[i-1],rz[i]);
        }

        }


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