AC自动机

Trie+Kmp=AC自动机

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N=1e6+5;
struct Trie{
    int fail;
    int vis[30];
    int tail;
}tree[MAX_N];

int cnt=0;

inline void Build(string s)         //用所有子串建立字典树
{
    int l=s.length();
    int now=0;
    for(int i=0;i<l;i++)
    {
        if(tree[now].vis[s[i]-'a']==0){
            tree[now].vis[s[i]-'a']=++cnt;
        }
        now=tree[now].vis[s[i]-'a'];
    }
    tree[now].tail+=1;
}

void Get_fail(){                //用BFS求失配指针
    queue<int> que;
    for(int i=0;i<26;i++){
        if(tree[0].vis[i]!=0){
            tree[tree[0].vis[i]].fail=0;
            que.push(tree[0].vis[i]);
        }
    }
    while(que.size()){
        int u=que.front();
        que.pop();
        for(int i=0;i<26;i++){
            if(tree[u].vis[i]!=0){
                tree[tree[u].vis[i]].fail=tree[tree[u].fail].vis[i];
                que.push(tree[u].vis[i]);
            }
            else{
                tree[u].vis[i]=tree[tree[u].fail].vis[i];
            }
        }
    }
}

int query(string s){            //查询
    int l=s.length();
    int now=0,ans=0;
    for(int i=0;i<l;i++){
        now=tree[now].vis[s[i]-'a'];
        for(int t=now;t&&tree[t].tail!=-1;t=tree[t].fail){
            ans+=tree[t].tail;
            tree[t].tail=-1;
        }
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(0);
    int n;
    string s;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s;
        Build(s);
    }
    tree[0].fail=0;
    Get_fail();
    cin>>s;
    cout<<query(s)<<endl;
    return 0;
}