【模板】AC自动机

AC自动机又称Trie图，是一个确定性有限状态自动机。具体来讲，通过在 trie 上定义一个 fail 转移函数，将 trie 的树形结构变成了一个图的结构。同时，根据 DFA 的性质，对于每个状态节点都要有关于字母表中所有字符的转移方式，在构建 fail 指针的同时，也完成了这个操作。
AC自动机建立的时间复杂度为 \(O(N)\)，匹配的时间复杂度为 \(O(M)\)，其中 N 为所有模式串长度的总和，M 为匹配串长度的总和。
对于代码实现的一些细节如下：

1. 正常来说，应该将所有存在的第二层节点的 fail 指针均指向根节点（类似于kmp算法中的第一个字符的 nxt）。在这里采用将所有的 trie[0][i] 均初始化成根节点，也可以达到类似效果。

代码如下

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

int trie[maxn][26],tot=1,ed[maxn],fail[maxn];
void insert(char *s){
    int now=1,len=strlen(s+1);
    for(int i=1;i<=len;i++){
        int ch=s[i]-'a';
        if(!trie[now][ch])trie[now][ch]=++tot;
        now=trie[now][ch];
    }
    ed[now]++;
}
void build(){
    queue<int> q;
    for(int i=0;i<26;i++)trie[0][i]=1;
    q.push(1);
    while(q.size()){
        int u=q.front();q.pop();
        for(int i=0;i<26;i++){
            if(trie[u][i]){
                fail[trie[u][i]]=trie[fail[u]][i];
                q.push(trie[u][i]);
            }else{
                trie[u][i]=trie[fail[u]][i];
            }
        }
    }
}
int query(char *s){
    int now=1,len=strlen(s+1);
    int ret=0;
    for(int i=1;i<=len;i++){
        now=trie[now][s[i]-'a'];
        for(int j=now;j&&~ed[j];j=fail[j]){
            ret+=ed[j];
            ed[j]=-1;
        }
    }
    return ret;
}
int n;
char s[maxn];

void read_and_parse(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%s",s+1),insert(s);
    scanf("%s",s+1);
}
void solve(){
    build();
    printf("%d\n",query(s));
}
int main(){
    read_and_parse();
    solve();
    return 0;
} 

【模板】AC自动机

原文：https://www.cnblogs.com/wzj-xhjbk/p/10905526.html