F08【模板】AC自动机

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
char s[N];
int ch[N][26],id,ed[N],pre[N];
 
void ins(char *s)//建字典树
{
    int p=0;
    for(int i=0;s[i];i++)
    {
        int j=s[i]-'a';
        if(ch[p][j]==0) ch[p][j]=++id;
        p=ch[p][j];
    }
    ed[p]++;
}
void build()//建AC自动机
{
    queue<int> Q;
    for(int i=0;i<26;i++)if(ch[0][i])Q.push(ch[0][i]);//确保单词第一个字母转移和回跳到0点 
    while(!Q.empty())
    {
        int x=Q.front();Q.pop();
        for(int i=0;i<26;i++)
        {
            int &y=ch[x][i];
            if(y==0)     y=ch[pre[x]][i];//(x认虚儿子)转移边 
            else    pre[y]=ch[pre[x]][i], Q.push(y);//（y认自己的后缀替身）回跳边，且y进入队列 
        }
    }
}
int query(char *s)
{
    int ans=0,p=0;ed[0]=-1; 
    for(int i=0;s[i];i++)
    {
        p=ch[p][s[i]-'a'];
        for(int j=p;j && ed[j]!=-1;j=pre[j])//此处不能写 ed[j]>0
            ans+=ed[j], ed[j]=-1;//此处ed[j]=0也是对的，就是以后路过的人浪费时间多些
    }
	return ans;
}
int main()
{
    int n;scanf("%d",&n);
    id=0;memset(ch,0,sizeof(ch));memset(ed,0,sizeof(ed)); 
    for(int i=1;i<=n; i++)scanf("%s",s),ins(s);
    memset(pre,0,sizeof(pre));build();
    
    scanf("%s",s);
    printf("%d\n",query(s) );
    return 0;
}