概述

AC 自动机是 以 Trie 的结构为基础，结合 KMP 的思想 建立的。
简单来说，建立一个 AC 自动机有两个步骤：

1. 基础的 Trie 结构：将所有的模式串构成一棵 Trie。
2. KMP 的思想：对 Trie 树上所有的结点构造失配指针。

AC自动机：可以直接求一组模板串中有多少个模板串在主串中出现过。

kmp复习

ne[i] 表示在p[]中p[i]结尾的后缀，能够匹配的从1开始的非平凡的前缀的最大长度。

for(int i = 2; i <= n; i ++)
{
    int j = ne[i - 1]; // 每次用到上一个字符的next
    while(j && p[i] != p[j] + 1)j = ne[j];
    if(p[i] == p[j + 1])j ++;
    next[i] = j;
}

trie图上做KMP

1. 首先我们先建立一个Trie图，就以单词she,he,say,shr,her为例
   
   凡是有绿点的都表示有单词结尾

2. 类比 KMP 的 next[i] trie里的next数组代表最长的trie"相同前后缀"，如果不存在相同前缀则next[i]指向0。
   比如是she中在trie树中最长存在相同前缀的后缀为he,其前缀和her的he
   此时 she 的 e 通过next指向 her的e。
   
   

完整的AC自动机的图

如何写代码：

自动机在trie中则是先求前i-1层的信息,再求第i层的信息，那么逐层向下就可以用BFS来做

模板例题：搜索关键词

#include<bits/stdc++.h>

using namespace std;

const int N=1e4+100,S=55,M=1e6+100;

int trie[N*S][26];
int tot=0;
int cnt[N*S];//标记单词
int nxt[N*S];//失配指针
char str[M];

void insert(){
    int n=strlen(str);
    int p=0;
    for(int i=0;i<n;i++){
        int c=str[i]-'a';
        if(!trie[p][c]) trie[p][c]=++tot;
        p=trie[p][c];
    }
    cnt[p]++;
}

void build(){
    queue<int> q;
    for(int i=0;i<26;i++)
        if(trie[0][i]) q.push(trie[0][i]); //第一层直接入队
    while(!q.empty()){
        int t=q.front();q.pop();
        for(int i=0;i<26;i++){
            int p=trie[t][i];
            if(!p) trie[t][i]=trie[nxt[t]][i];
            else{
                nxt[p]=trie[nxt[t]][i]; //利用上层信息更新现在的节点信息
                q.push(p);
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t;cin>>t;
    while(t--){
        memset(trie,0,sizeof(trie));
        memset(nxt,0,sizeof(nxt));
        memset(cnt,0,sizeof(cnt));
        tot=0;
        
        int n;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>str;
            insert();
        }
        
        build();// 在trie图上做KMP
        int ans=0;
        cin>>str;
        int len=strlen(str);
        for(int i=0,j=0;i<len;i++){
            int c=str[i]-'a'; //遍历到当前结果
            j=trie[j][c];
            int p=j;
            while(p){
                ans+=cnt[p]; //更新答案
                cnt[p]=0; //统计出现的种类，所以清空标记
                p=nxt[p];  //向上跳，不漏答案
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}