学步园

#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int MAXNODE = 1000010;
int ch[MAXNODE][26];
int val[MAXNODE],last[MAXNODE],sz;
int f[MAXNODE];
char s[MAXNODE];

int idx(char a) {return a - 'a';}


void init()
{
    sz=1;
    memset(ch[0],0,sizeof(ch[0]));
    memset(last,0,sizeof(last));

}


void insert()
{
    //puts("insert");
    int n=strlen(s),curr=0;

    for(int i=0;i<n;i++)
    {
        int c=idx(s[i]);
        if(!ch[curr][c])
        {
            memset(ch[sz],0,sizeof(ch[sz]));
            val[sz]=0;
            ch[curr][c]=sz++;
        }
        curr=ch[curr][c];
    }
    val[curr]++;
    //puts("insert compelete");
}

void getfail()
{
    //puts("getfail..");


    queue<int> q;
    f[0]=0;
    int u;

    for(int i=0;i<26;i++)
    {
        u=ch[0][i];
        if(u)
        {
            f[u]=0;
            q.push(u);
            last[u]=0;
        }
    }
    while(!q.empty())
    {
        int curr=q.front();
        q.pop();
        for(int i=0;i<26;i++)
        {
            u=ch[curr][i];
            if(!u)
            {
                ch[curr][i]=ch[f[curr]][i];
                continue;
            }
            q.push(u);

            int tmp=f[curr];
            if(tmp && !ch[tmp][i]) tmp=ch[f[tmp]][i];
            f[u]=ch[tmp][i];
            last[u]=val[f[u]]? f[u]:last[f[u]];
        }
    }
    //puts("getfail compelete");
}

int find()
{
    //printf("Find:\n");
    int cnt=0;
    int n=strlen(s),u=0;

    for(int i=0;i<n;i++)
    {
        int c=idx(s[i]);

        u=ch[u][c];
        /*if(val[u])
        {
            //printf("%d %d\n",u,last[u]);
            cnt+=val[u];
            val[u]=0;

        }
        if(last[u]&&val[last[u]])
        {
            cnt+=val[last[u]];
            val[last[u]]=0;

        }*/

        for(int tmp=u;tmp>0&&val[tmp]>0;tmp=f[tmp])
          cnt+=val[tmp],val[tmp]=0;
    }
    //printf("Find complete..");
    return cnt;
}


int main()
{
    int N;
    scanf("%d",&N);
    while(N--)
    {
        int n;

        scanf("%d",&n);
        init();
        for(int i=0;i<n;i++)
        {
            scanf("%s",s);
            insert();
        }
        //puts("All Inserted");
        getfail();
        //for(int i=0;i<sz;i++)
        //    printf("%d\t%d\n",i,last[i]);

        scanf("%s",s);
        printf("%d\n",find());
    }
    return 0;
}

ac自动机模板