AC自动机简单版

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn=1e6+10;
int trie[maxn][26],k,cnt[maxn],fail[maxn];
void insert(char *s){
    int len=strlen(s),p=0;
    for(int i=0;i<len;i++){
        int c=s[i]-‘a‘;
        if(!trie[p][c])trie[p][c]=++k;
        p=trie[p][c];
    }
    cnt[p]++;
}
void getfail(){
    queue<int>q;
    for(int i=0;i<26;i++)
        if(trie[0][i])q.push(trie[0][i]),fail[trie[0][i]]=0;
    while(!q.empty()){
        int t=q.front();q.pop();
        for(int i=0;i<26;i++){
            if(trie[t][i]){
                fail[trie[t][i]]=trie[fail[t]][i];
                q.push(trie[t][i]);
            }
            else{
                trie[t][i]=trie[fail[t]][i];
            }
        }
    }
}
int query(char *s){
    int len=strlen(s),p=0,ans=0;
    for(int i=0;i<len;i++){
        p=trie[p][s[i]-‘a‘];
        for(int i=p;i&&~cnt[i];i=fail[i]){
            ans+=cnt[i];cnt[i]=-1;
        }
    }
    return ans;
}
int main()
{
    int n;
    scanf("%d",&n);
    char s[maxn];
    while(n--){
        scanf("%s",s);
        insert(s);
    }
    getfail();
    scanf("%s",s);
    printf("%d\n",query(s));
}