AC自动机（模式串最多出现的次数）
Whiteying
2018-10-17 19:02:55
from：https://www.cnblogs.com/cjyyb/p/7196308.html
模板：
```cpp
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;
struct Tree //字典树
{
int fail;//失配指针
int vis[26];//子节点的位置
int end;//标记有几个单词以这个节点结尾
}AC[1000000];//Trie树
int cnt=0;//Trie的指针
struct Result
{
int pos;
int num;
}Ans[1000000];
bool operator <(Result a,Result b)
{
if(a.num!=b.num)
return a.num>b.num;
else
return a.pos<b.pos;
}
char s[1000000][75];
char T[1000005];
inline void Clean(int x)
{
memset(AC[x].vis,0,sizeof(AC[x].vis));
AC[x].fail=0;
AC[x].end=0;
}
inline void Build(string s,int Num)
{
int l=s.length();
int now=0;//字典树的当前指针
for(int i=0;i<l;++i)//构造Trie树
{
if(AC[now].vis[s[i]-'a']==0)//Trie树没有这个子节点
{
AC[now].vis[s[i]-'a']=++cnt;//构造出来
Clean(cnt);
}
now=AC[now].vis[s[i]-'a'];//向下构造
}
AC[now].end=Num;//标记单词结尾
/*
在这里的操作对于不同的题目一般有3种不同的操作。
1：s[ind].count++;
这个是在解决出现总次数的时候是这样处理的。
2：s[ind],count=1;
这个是在ac自动机上进行dp的时候经常用的。
3.新加一个标记id。
这个是在处理有哪些单词出现过。
*/
}
void Get_fail()//构造fail指针
{
queue<int> Q;//队列
for(int i=0;i<26;++i)//第二层的fail指针提前处理一下
{
if(AC[0].vis[i]!=0)
{
AC[AC[0].vis[i]].fail=0;//指向根节点
Q.push(AC[0].vis[i]);//压入队列
}
}
while(!Q.empty())//BFS求fail指针
{
int u=Q.front();
Q.pop();
for(int i=0;i<26;++i)//枚举所有子节点
{
if(AC[u].vis[i]!=0)//存在这个子节点
{
AC[AC[u].vis[i]].fail=AC[AC[u].fail].vis[i];
//子节点的fail指针指向当前节点的
//fail指针所指向的节点的相同子节点
Q.push(AC[u].vis[i]);//压入队列
}
else//不存在这个子节点
AC[u].vis[i]=AC[AC[u].fail].vis[i];
//当前节点的这个子节点指向当
//前节点fail指针的这个子节点
}
}
}
int AC_Query(string s)//AC自动机匹配
{
int l=s.length();
int now=0,ans=0;
for(int i=0;i<l;++i)
{
now=AC[now].vis[s[i]-'a'];//向下一层
for(int t=now;t;t=AC[t].fail)//循环求解
{
Ans[AC[t].end].num++;
}
}
return ans;
}
int main()
{
int n;
while(~scanf("%d",&n)&&n)
{
cnt=0;
Clean(0);
for(int i=1;i<=n;++i)
{
scanf("%s",s[i]);
Ans[i].num=0;
Ans[i].pos=i;
Build(s[i],i);
}
AC[0].fail=0;//结束标志
Get_fail();//求出失配指针
scanf("%s",T);//文本串
AC_Query(T);
sort(&Ans[1],&Ans[n+1]);
printf("%d\n",Ans[1].num);
printf("%s\n",s[Ans[1].pos]);
for(int i=2;i<=n;i++)
{
if(Ans[i].num==Ans[1].num)
printf("%s\n",s[Ans[i].pos]);
else
break;
}
}
return 0;
}
```