题目描述
有N个由小写字母组成的模式串以及一个文本串T。每个模式串可能会在文本串中出现多次。你需要找出哪些模式串在文本串T中出现的次数最多。
输入输出格式
输入格式：
输入含多组数据。
每组数据的第一行为一个正整数N，表示共有N个模式串，1≤N≤150。
接下去N行，每行一个长度小于等于707070的模式串。下一行是一个长度小于等于10^6的文本串T。
输入结束标志为N=0。
输出格式：
对于每组数据，第一行输出模式串最多出现的次数，接下去若干行每行输出一个出现次数最多的模式串，按输入顺序排列。
输入输出样例
输入样例#1：
2
aba
bab
ababababac
6
beta
alpha
haha
delta
dede
tata
dedeltalphahahahototatalpha
0
输出样例#1：
4
aba
2
alpha
haha
题解
以为加强版会卡时间结果连register都没加就很宽裕的过去了QAQ
然后加强版就只是有一丢丢不一样？都说不上有升级叭QAQ
/*
qwerta
P3796 【模板】AC自动机（加强版）
Accepted
100
代码 C++，2.32KB
提交时间 2018-10-07 21:48:13
耗时/内存
2264ms, 3096KB
*/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int lenN=*+;
const int lenT=1e6+;
struct emm{
int fail;
int nxt[];
int tag;
}AC[lenN];//Tree结构体
string s[];
string st,t;
queue<int>q;
struct ahh{
int v,nod;
}b[];
bool cmp(ahh qaq,ahh qwq){
if(qaq.v==qwq.v)return qaq.nod<qwq.nod;
return qaq.v>qwq.v;
}
int main()
{
//freopen("a.in","r",stdin);
ios::sync_with_stdio(false);
cin.tie(false),cout.tie(false);
while()
{
int n;
cin>>n;
if(n==)return ;
memset(AC,,sizeof(AC));
//trie
int cnt=;
for(int w=;w<=n;++w)
{
cin>>st;
int len=st.length();
int now=;
for(int i=;i<len;++i)
{
if(!AC[now].nxt[st[i]-'a'])
AC[now].nxt[st[i]-'a']=++cnt;
now=AC[now].nxt[st[i]-'a'];
}
AC[now].tag=w;//记录是第几个数组的结尾
s[w]=st;
}
//get_fail
{
for(int i=;i<;++i)
if(AC[].nxt[i])
{
AC[AC[].nxt[i]].fail=;
q.push(AC[].nxt[i]);
}
while(!q.empty())
{
int x=q.front();q.pop();
for(int i=;i<;++i)
{
if(AC[x].nxt[i])
{
AC[AC[x].nxt[i]].fail=AC[AC[x].fail].nxt[i];
q.push(AC[x].nxt[i]);
}
else
AC[x].nxt[i]=AC[AC[x].fail].nxt[i];
}
}
}
//run
{
memset(b,,sizeof(b));
for(int i=;i<=n;++i)
b[i].nod=i;
cin>>t;
int len=t.length();
int now=;
for(int i=;i<len;++i)
{
now=AC[now].nxt[t[i]-'a'];
for(int u=now;u;u=AC[u].fail)
if(AC[u].tag)
{
b[AC[u].tag].v++;
}
}
//然后是一些奇奇怪怪的句子来输出答案
sort(b+,b+n+,cmp);
cout<<b[].v<<endl;
int k=;
while(b[k].v==b[].v)
{
cout<<s[b[k].nod]<<endl;
k++;
}
}
}
return ;
}