什么是AC自动机？
AC自动机是一种经典的多模式串匹配算法，它能够在文本中同时查找多个模式串的出现位置，时间复杂度为O(n + m + z)，其中n是文本长度，m是所有模式串总长度，z是匹配到的模式串数量。
为什么需要AC自动机？
假设要在一篇文章中查找1000个词，如果用传统的KMP算法，需要对每个敏感词单独扫描文章，时间复杂度为O(1000 × n)。AC自动机只需要扫描文章一次就能找到所有敏感词！
AC自动机的核心思想
AC自动机 = Trie树 + KMP思想 + 失配指针
1.构建Trie树
首先将所有模式串构建成一棵Trie树，每个节点代表一个字符，从根节点到某个节点的路径构成一个模式串的前缀。
2.构建失配指针（Fail指针）
这是AC自动机的核心！Fail指针指向当前节点匹配失败时应该跳转的位置。
根节点的所有子节点的fail指向根节点
对于其他节点u，假设其父节点为p，通过字符c到达u
如果p->fail有通过c的子节点，则u->fail指向该子节点
3.匹配过程
匹配时，AC自动机在文本串上移动，使用Trie树进行匹配，匹配失败时通过fail指针跳转。
ac acwing1282代码
include<bits/stdc++.h>
using namespace std;
const int N=1e4+10,S=55,M=1e6+10;
int tr[NS][26],cnt[NS],ne[NS],idx,n;
int que[NS];
char str[M];
void insert(){
int p=0;
for(int i=0;str[i];i++){
int u=str[i]-'a';
if(!tr[p][u]) tr[p][u]=++idx;
p=tr[p][u];
}
cnt[p]++;
}
void build(){
int hh=0,tt=-1;
for(int i=0;i<26;i++){
if(tr[0][i]) que[++tt]=tr[0][i];
}
while(hh<=tt){
int ans=que[hh++];
for(int i=0;i<26;i++){
if(tr[ans][i]){
ne[tr[ans][i]]=tr[ne[ans]][i];
que[++tt]=tr[ans][i];
}
else{
tr[ans][i]=tr[ne[ans]][i];
}
}
}
}
int main(){
int t;
cin>>t;
while(t--){memset(cnt,0,sizeof cnt);memset(tr,0,sizeof tr);memset(ne,0,sizeof ne);idx=0;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%s",str);insert();}build();scanf("%s",str);int res=0;for(int i=0,j=0;str[i];i++){int u=str[i]-'a';j=tr[j][u];int p=j;while(p&&cnt[p]!=-1){res+=cnt[p];cnt[p]=-1;p=ne[p];} }printf("%d\n",res);
}
return 0;
}