洛谷P3796 【模板】AC 自动机（加强版） 题解
题意： $T$ 组数据，每组 $N$ 个模式串 $s_i$ ，要求输出这些模式串在文本串 $S$ 中出现次数最多的模式串以及它们的出现次数，按输入顺序输出
可以发现这是个AC自动机的裸题
那怎么处理出现次数呢？
我们只需要把匹配过程中所有可能产生的字符串都次数+1
例如在匹配到she的时候，可以发现它的任意后缀都可能成为其他模式串的前缀
那我们只要将（如果有的话）she,he,e这三个都加上1
这个过程不就是沿着当前结点的fail指针往上跳吗？（上指结点深度小的，根节点深度为0）
还有，多组数据一定要清空哦！
char数组不一定要，因为在读取的时候会在最后加一个\0的，一般不影响
到此为止，一些题解就直接贴代码了
我们来分析一下单次询问的时间复杂度
AC自动机的时间复杂度 $O(\sum|s_i|+|S|)$
而我们统计的时候是暴力跳fail指针，那么最坏时间复杂度 $O(S\times \max\{|s_i|\})$
所以整个算法的时间复杂度 $O(T|S|\max\{|s_i|\})$
然后我们发现它的数据范围 $T\le50,S\le10^6,s_i\le70$ ，时间有 $3$ 秒
而且这道题也没有故意卡这个，那我们就可以水过去了（别急着关掉这个网页啊！）
先贴一下代码：qwq
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N (int)(155)
#define S (int)(75)
#define SZ (int)(155*75)
#define L (int)(1e6+5)
char t[L],s[N][S];
int n,cnt[N],e[SZ],val[SZ];
int trie[SZ][32],tot,fail[SZ];
void init()
{
memset(fail,0,sizeof(fail));
memset(cnt,0,sizeof(cnt));
memset(e,0,sizeof(e));
memset(trie,0,sizeof(trie));
memset(val,0,sizeof(val));
tot=0;
}
void insert(int l,char *s,int id)
{
int u=0;
for(int i=1; i<=l; i++)
{
int c=s[i]-'a';
if(!trie[u][c])trie[u][c]=++tot;
u=trie[u][c];
}
e[u]=id;
}
queue<int>q;
void build()
{
for(int i=0; i<26; i++)
if(trie[0][i])q.push(trie[0][i]);
while(!q.empty())
{
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 AC(int l,char *t)
{
int u=0,res=0;
for(int i=1; i<=l; i++)
{
u=trie[u][t[i]-'a'];
for(int j=u; j; j=fail[j])
++val[j];
}
for(int i=1; i<=tot; i++) if(e[i])
{
res=max(res,val[i]);
cnt[e[i]]=val[i];
}
return res;
}
signed main()
{
while(scanf("%lld",&n)&&n)
{
init();
for(int i=1; i<=n; i++)
{
scanf("%s\n",s[i]+1);
insert(strlen(s[i]+1),s[i],i);
}
scanf("%s\n",t+1);
build();
int mx=AC(strlen(t+1),t);
printf("%lld\n",mx);
for(int i=1; i<=n; i++)
if(cnt[i]==mx)printf("%s\n",s[i]+1);
}
return 0;
}那么问题来了，这题为什么不卡呢？
因为还有个 P5357 【模板】AC 自动机（二次加强版）
题解在此
