AC自动机

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN=1000010;
struct AC_automaton{
    int tr[MAXN][26], cnt;                                              //TRIE
    int e[MAXN];                                                        //标记字符串结尾，end标记 
    int fail[MAXN];                                                     //fail指针

    void insert(char * s)                                               //插入模式串
    {
        int p=0;
        for(int i=0; s[i]; i++)                                         //s[i]==''时为false 
        {
            int id=s[i]-'a';
            if(!tr[p][id])  tr[p][id]=++cnt;
            p=tr[p][id];
        }
        e[p]++;                                                         //添加end标记 
    }

    void build(){                                                       //构建fail指针 
        queue<int> q;
        memset(fail, 0, sizeof(fail));
        for(int i=0; i<26; i++) if(tr[0][i]) q.push(tr[0][i]);          //首字符入队，不直接将0入队是为了避免指向自己
        while(!q.empty())
        {
            int k=q.front();
            q.pop();
            for(int i=0;i<26;i++)
            {
                if(tr[k][i])
                {
                    fail[tr[k][i]]=tr[fail[k]][i];                      //构建当前的fail指针
                    q.push(tr[k][i]);
                }
                else tr[k][i]=tr[fail[k]][i];                           //匹配到空字符，则索引到父节点fail指针对应的字符，以供后续指针的构建
                                                                        //类似并差集的路径压缩，把不存在的tr[k][i]全部指向tr[fail[k]][i]
                                                                        //这句话在后面匹配主串的时候也能帮助跳转
            }
        }
    }

    int query(char *t){                                                 //匹配函数 
        int p=0, ans=0;
        for(int i=0; t[i]; i++)
        {
            p=tr[p][t[i]-'a'];
            for(int j=p; j && e[j]!=-1; j=fail[j])						//利用fail指针在同一位置进行多模式匹配
				ans+=e[j], e[j]=-1;										//e[j]置为-1表示这个单词已经出现过了，防止以后再次匹配 
        }
        return ans;
    }
}ac;

int  n;
char s[MAXN], t[MAXN];
int main()
{
    cin>>n;
    for(int i=1; i<=n; i++) cin>>s, ac.insert(s);
    ac.build();
    cin>>t;
    cout<<ac.query(t)<<endl;
    return 0;   
}