AC自动机

#include <bits/stdc++.h>
using namespace std;
const int maxn =  2*1e6+9;

int trie[maxn][26]; //字典树
int cntword[maxn];  //记录该单词出现次数
int fail[maxn];     //失败时的回溯指针
int cnt = 0;

void insertWords(string s){ // 简单构建Trie树的过程
    int root = 0;
    for(int i=0;i<s.size();i++){
        int next = s[i] - 'a';
        if(!trie[root][next])
            trie[root][next] = ++cnt;
        root = trie[root][next];
    }
    cntword[root]++;      // 只有当cntword[i]≠0，才表示这个节点有完整单词
}


void getFail(){
    queue <int>q;
    for(int i=0;i<26;i++){      //将第二层所有出现了的字母扔进队列
        if(trie[0][i]){
            fail[trie[0][i]] = 0;
            q.push(trie[0][i]);
        }
    }
    while(!q.empty()){
        int now = q.front();
        q.pop();
        for(int i=0;i<26;i++){
            if(trie[now][i]){ // 让这个节点的失配指针指向他父亲节点的失配指针所指向的那个节点的下一个节点
                fail[trie[now][i]] = trie[fail[now]][i];
                q.push(trie[now][i]);
            }
            else { // 否则就让当前节点的这个子节点指向当前节点fail指针的这个子节点
                trie[now][i] = trie[fail[now]][i];
            }
        }
    }
}


int query(string s){
    int now = 0,ans = 0;
    for(int i=0;i<s.size();i++){    //遍历文本串
        now = trie[now][s[i]-'a'];  //从s[i]点开始寻找
        for(int j=now;j && cntword[j]!=-1;j=fail[j]){ //一直向下寻找,直到匹配失败(失配指针指向根或者当前节点已找过).
            ans += cntword[j];
            cntword[j] = -1;    //将遍历后的节点标记,防止重复计算
        }
    }
    return ans;
}


int main() {
    int n; // 多模式匹配的模式串数量
    string s;
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> s ;
        insertWords(s);
    }
    fail[0] = 0;
    getFail();
    cin >> s ; // 给定一份文本
    cout << query(s) << endl;
    return 0;
}