题解 P3796 【【模板】AC自动机（加强版）】
RicardoShips
·
·
题解
明天放假，今天没什么心思做题，就来水一篇题解
其实也是顺便做一个字符串的小结
前置技能
以下内容绝大多数来自百度百科
典型应用是用于统计，排序和保存大量的字符串
~~感觉说了等于没说~~
简言之，就是把要匹配的字符串变成树形结构再去匹配
$KMP$算法是一种先进的字符串匹配算法
$KMP$算法的关键是利用匹配失败后的信息
尽量减少模式串与主串的匹配次数以达到快速匹配的目的
具体实现就是实现一个$next$函数，函数本身包含了模式串的局部匹配信息
这个$next$函数学名叫失配函数，~~就是匹配失败的时候使用的~~
建立一个$AC$自动机通常需要两个步骤
- 构建$Trie$树
- 对$Trie$树上所有的结点构造失配指针
~~废话讲完了，下面的才是重点~~
**如何构造失配指针？？？**
构建$fail$指针，可以参考$KMP$中构造$next$数组的思想
我们可以考虑用线性递推的方法来构建
具体的操作类似一个$BFS$，构建一个优先队列
然后一层一层去扩展，标记$fail$指针
这里要按照节点是否存在的情况讨论一下，推荐手玩几组样例
代码其实很短，但是理解起来真的很难
[安利一个带$GIF$的博客](https://www.luogu.org/blog/42196/qiang-shi-tu-xie-ac-zi-dong-ji)，~~其实是我讲不清~~
构造之后再回到母串中逐个匹配
用$fail$指针自动跳转到下一个位置
取反是用来判断是否那个点已经经过
这里感觉很像跑图论，其实也就是在跑字典图
~~好像$AC$自动机就这么一点点？？？~~
引用某大神一句话，强行总结一句$AC$自动机的运行原理
**构建字典图实现自动跳转，构建失配指针实现多模式匹配**
因为我代码常数很大，所以实用价值不高，~~但是还是贴一下~~
```cpp
#include<bits/stdc++.h>
using namespace std;
char s[155][75];
char T[1000001];
int sum[1000001];
int val[1000001];
int fail[1000001];
int son[1000001][27];
int ans,mmp,tot,root,N;
inline void insert(char *s,int I)
{
int M=strlen(s+1),now=root;
for(register int i=1;i<=M;++i)
{
int x=s[i]-'a';
if(!son[now][x]) son[now][x]=++tot;
now=son[now][x];
}
val[now]=I;
}
inline void miss()
{
queue < int > Q;
for(register int i=0;i<26;++i)
if(son[root][i]) Q.push(son[root][i]);
while(!Q.empty())
{
int p=Q.front();Q.pop();
for(register int i=0;i<26;++i)
if(!son[p][i]) son[p][i]=son[fail[p]][i];
else fail[son[p][i]]=son[fail[p]][i],Q.push(son[p][i]);
}
}
int main()
{
while(scanf("%d",&N)&&N)
{
memset(s,0,sizeof(s));memset(son,0,sizeof(son));memset(sum,0,sizeof(sum));
memset(val,0,sizeof(val));memset(fail,0,sizeof(fail));
for(register int i=1;i<=N;++i) scanf("%s",s[i]+1),insert(s[i],i);
miss();ans=0;scanf("%s",T+1);int M=strlen(T+1),now=root;
for(register int i=1;i<=M;++i)
{
now=son[now][T[i]-'a'];
for(register int j=now;j;j=fail[j]) if(val[j]) ++sum[val[j]];
}
for(register int i=1;i<=N;++i) ans=max(ans,sum[i]);
printf("%d\n",ans);
for(register int i=1;i<=N;++i)
if(ans==sum[i]) printf("%s\n",s[i]+1);
}
return 0;
}
```