题解 P3796 【【模板】AC自动机（加强版）】
做法：AC自动机
如果没有学过AC自动机，看这里AC自动机详细讲解
无疑，作为模板2，这道题的解法也是十分的经典。
我们先来分析一下题目：输入和模板1一样
1、求出现次数最多的次数
2、求出现次数最多的模式串
明显，我们如果统计出每一个模式串在文本串出现的次数，那么这道题就变得十分简单了，那么问题就变成了如何统计每个模式串出现的次数。
做法：AC自动机
首先题目统计的是出现次数最多的字符串，所以有重复的字符串是没有关系的。（因为后面的会覆盖前面的，统计的答案也是一样的）
那么我们就将标记模式串的flag设为当前是第几个模式串。就是下面插入时的变化：
trie[u].flag++;
变为
trie[u].flag=num; //num表示该字符串是第num个输入的求Fail指针没有变化，原先怎么求就怎么求。
查询：我们开一个数组vis，表示第i个字符串出现的次数。
因为是重复计算，所以不能标记为-1了。
我们每经过一个点，如果有模式串标记，就将vis[模式串标记]++。然后继续跳fail。
这样我们就可以将每个模式串的出现次数统计出来。剩下的大家应该都会QwQ！
总代码
//AC自动机加强版
#include<bits/stdc++.h>
#define maxn 1000001
using namespace std;
char s[151][maxn],T[maxn];
int n,cnt,vis[maxn],ans;
struct kkk{
int son[26],fail,flag;
void clear(){memset(son,0,sizeof(son));fail=flag=0;}
}trie[maxn];
queue<int>q;
void insert(char* s,int num){
int u=1,len=strlen(s);
for(int i=0;i<len;i++){
int v=s[i]-'a';
if(!trie[u].son[v])trie[u].son[v]=++cnt;
u=trie[u].son[v];
}
trie[u].flag=num; //变化1：标记为第num个出现的字符串
}
void getFail(){
for(int i=0;i<26;i++)trie[0].son[i]=1;
q.push(1);trie[1].fail=0;
while(!q.empty()){
int u=q.front();q.pop();
int Fail=trie[u].fail;
for(int i=0;i<26;i++){
int v=trie[u].son[i];
if(!v){trie[u].son[i]=trie[Fail].son[i];continue;}
trie[v].fail=trie[Fail].son[i];
q.push(v);
}
}
}
void query(char* s){
int u=1,len=strlen(s);
for(int i=0;i<len;i++){
int v=s[i]-'a';
int k=trie[u].son[v];
while(k>1){
if(trie[k].flag)vis[trie[k].flag]++; //如果有模式串标记，更新出现次数
k=trie[k].fail;
}
u=trie[u].son[v];
}
}
void clear(){
for(int i=0;i<=cnt;i++)trie[i].clear();
for(int i=1;i<=n;i++)vis[i]=0;
cnt=1;ans=0;
}
int main(){
while(1){
scanf("%d",&n);if(!n)break;
clear();
for(int i=1;i<=n;i++){
scanf("%s",s[i]);
insert(s[i],i);
}
scanf("%s",T);
getFail();
query(T);
for(int i=1;i<=n;i++)ans=max(vis[i],ans); //最后统计答案
printf("%d\n",ans);
for(int i=1;i<=n;i++)
if(vis[i]==ans)
printf("%s\n",s[i]);
}
}这样的时间复杂度是多高呢？
O(模式串长度 · 文本串长度)。
想要了解AC自动机的优化，看这里