【模板】ac自动机

本来是真的特别不想写这个的 但是有段时间洛谷天天智推这个可能是我太菜了

然后觉得这个也不难 乘着今早没事写下 来这保存下 方便下次食用

#include <bits/stdc++.h>
using namespace std;
struct Node{int to[26],ed,f;}a[1<<20];
string s;
int pre[1<<20];
int n,pos,tot,t,h,tt,g;
int main(){
    scanf("%d",&n);
    for (register int i=1;i<=n;++i){
        cin>>s;pos=0;
        for (register int j=0;j<s.size();++j){
            tt=s[j]-'a';
            if (!a[pos].to[tt]) a[pos].to[tt]=++tot;
            pos=a[pos].to[tt];
        }
        ++a[pos].ed;
    }
    for (register int i=0;i<26;++i) 
        if (a[0].to[i])
            pre[++t]=a[0].to[i];
    while (h!=t){
        g=pre[++h];
        for (register int i=0;i<26;++i)
            if (a[g].to[i])
                a[a[g].to[i]].f=a[a[g].f].to[i],pre[++t]=a[g].to[i];
            else a[g].to[i]=a[a[g].f].to[i];
    }
    cin>>s;
    pos=tot=0;
    for (register int i=0;i<s.size();++i){
        pos=a[pos].to[s[i]-'a'];
        for (register int j=pos;j&&a[pos].ed;j=a[j].f)
            tot+=a[j].ed,a[j].ed=0;
    }
    printf("%d\n",tot);
    return 0;
}