题目描述
有 (N) 个由小写字母组成的模式串以及一个文本串 (T) 。每个模式串可能会在文本串中出现多次。你需要找出哪些模式串在文本串 (T) 中出现的次数最多。
输入输出格式
输入格式：
输入含多组数据。
每组数据的第一行为一个正整数 (N) ，表示共有 (N) 个模式串， (1 leq N leq 150) 。
接下去 (N) 行，每行一个长度小于等于 (70) 的模式串。下一行是一个长度小于等于 (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
题解
同样的，简单匹配，匹配到有结尾标记的点，就把标记的点的贡献加上
最后取个最大值，找串输出就好了
因为可能存在相同的串，结尾标记用vector存就好了
#include<bits/stdc++.h>
#define ui unsigned int
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
const int MAXN=150+10,MAXS=1000000+10,MAXM=15000+10;
int n,ch[MAXM][30],fail[MAXM],last[MAXM],ed[MAXM],ans[MAXN],cnt;
char s[MAXS],t[MAXN][80];
std::queue<int> q;
std::vector<int> V[MAXM];
template<typename T> inline void read(T &x)
{
T data=0,w=1;
char ch=0;
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();
x=data*w;
}
template<typename T> inline void write(T x,char ch=' ')
{
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
if(ch!=' ')putchar(ch);
}
template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);}
template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);}
template<typename T> inline T min(T x,T y){return x<y?x:y;}
template<typename T> inline T max(T x,T y){return x>y?x:y;}
inline void init()
{
for(register int i=0,lt=strlen(s);i<lt;++i)s[i]-='a'-1;
}
inline void insert(int rk)
{
int x=0;
for(register int i=0,lt=strlen(s);i<lt;++i)
if(!ch[x][s[i]])x=ch[x][s[i]]=++cnt;
else x=ch[x][s[i]];
ed[x]=1;
V[x].push_back(rk);
}
inline void getfail()
{
for(register int i=1;i<=26;++i)
if(ch[0][i])q.push(ch[0][i]);
while(!q.empty())
{
int x=q.front();
q.pop();
for(register int i=1,y,z;i<=26;++i)
if(ch[x][i])
{
y=ch[x][i],z=fail[x];
while(z&&!ch[z][i])z=fail[z];
fail[y]=ch[z][i];
last[y]=ed[fail[y]]?fail[y]:last[fail[y]];
q.push(y);
}
else ch[x][i]=ch[fail[x]][i];
}
}
inline void save(int x)
{
if(x)
{
if(ed[x])
for(register int i=0,lt=V[x].size();i<lt;++i)ans[V[x][i]]++;
save(last[x]);
}
}
inline void match()
{
int x=0;
for(register int i=0,lt=strlen(s);i<lt;++i)x=ch[x][s[i]],save(ed[x]||last[x]?x:0);
}
int main()
{
while(scanf("%d",&n)!=EOF&&n)
{
for(register int i=1;i<=cnt;++i)V[i].clear();
memset(ch,0,sizeof(ch));
memset(ed,0,sizeof(ed));
memset(ans,0,sizeof(ans));
memset(fail,0,sizeof(fail));
memset(last,0,sizeof(last));
cnt=0;
for(register int i=1;i<=n;++i)
{
scanf("%s",s);
memcpy(t[i],s,sizeof(t[i]));
init();insert(i);
}
getfail();
scanf("%s",s);init();match();
int len=0;
for(register int i=1;i<=n;++i)chkmax(len,ans[i]);
write(len,'
');
for(register int i=1;i<=n;++i)
if(ans[i]==len)puts(t[i]);
}
return 0;
}