学步园

题意:

多模式串匹配.

思路:

AC自动机,注意回溯.

优化fail建立过程.

#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN = 240055;
const int MAXL = 1000005;

struct AC_machine
{
    int fail[MAXN];
    int sz;
    int ch[MAXN][26];
    int ID[128];
    int n;
    char str[MAXL];
    int Q[MAXN];
    int v[MAXN];

    void Init()
    {
        sz = 1;
        memset(ch[0],0,sizeof(ch[0]));
        memset(v,0,sizeof(v));
        fail[0] = 0;
        for(int i=0;i<26;i++)  ID[i+'a'] = i;
    }

    void Insert(char s[])
    {
        int cur = 0;
        for(int i=0;s[i];i++)
        {
            int c = ID[s[i]];
            if(!ch[cur][c])
            {
                memset(ch[sz],0,sizeof(ch[sz]));
                ch[cur][c] = sz++;
            }
            cur = ch[cur][c];
        }
        v[cur]++;
    }

    void Input()
    {

        scanf("%d",&n);
        char s[55];
        for(int i=0;i<n;i++)
        {
            scanf("%s",s);
            Insert(s);
        }
        scanf("%s",str);
    }

    void Build()
    {
        int st = 0, en = 0;
        for(int i=0;i<26;i++)
        {
            if(ch[0][i])
            {
                fail[ch[0][i]] = 0;
                Q[en++] = ch[0][i];
            }
        }
        while(st!=en)
        {
            int cur = Q[st++];
            for(int i=0;i<26;i++)
            {
                int &v = ch[cur][i];
                if(v)
                {
                    Q[en++] = v;
                    fail[v] = ch[fail[cur]][i];
                }
                else
                {
                    v = ch[fail[cur]][i];//优化
                }
            }
        }
    }

    void solve()
    {
        int ans = 0,j = 0,tmp;
        for(int i=0;str[i];i++)
        {
            if(ch[j][ID[str[i]]])    j = ch[j][ID[str[i]]];
            else
            {
                while(j && !ch[j][ID[str[i]]])  j = fail[j];
                if(ch[j][ID[str[i]]])   j = ch[j][ID[str[i]]];
            }
            tmp = j;
            while(tmp && v[tmp])
            {
                ans += v[tmp];
                v[tmp] = 0;
                tmp = fail[tmp];
            }
        }
        printf("%d\n",ans);
    }
} AC;

int main()
{
    int T;
    scanf("%d",&T);

    while(T--)
    {
        AC.Init();
        AC.Input();
        AC.Build();
        AC.solve();
    }
}