视频链接：

P3808 【模板】AC 自动机（简单版）

#include 
#include 
#include 
#include 
using namespace std;

const int N=1000010;
int tr[N][26],cnt[N],idx,ne[N];
int n; char str[N];

void insert(char *s){ // 建Trie
    int p=0;
    for(int i=0; s[i]; i++){
        int e=s[i]-'a';
        if(!tr[p][e]) tr[p][e]=++idx;
        p=tr[p][e];
    }
    cnt[p]++;
}

void build(){ // 建AC自动机
    queue<int> q;
    for(int i=0; i<26; i++)
        if(tr[0][i]) 
            ne[tr[0][i]]=0,
            q.push(tr[0][i]);
    while(q.size()){
        int u=q.front(); q.pop();
        for(int i=0; i<26; i++){
            int v=tr[u][i];
            if(v) ne[v]=tr[ne[u]][i],
                  q.push(v);
            else tr[u][i]=tr[ne[u]][i];
        }
    }
}

int query(char *s){
    int ans=0;
    for(int c=0, i=0; s[c]; c++){
        i=tr[i][s[c]-'a'];
        for(int j=i; j&&~cnt[j]; j=ne[j])
            ans+=cnt[j], cnt[j]=-1;
    }
    return ans;
}

int main(){
    cin >> n;
    for(int i=0; i < n; i ++)
        cin >> str, insert(str);
    build();
    cin >> str;
    cout << query(str) << endl;
    return 0;
}