题目描述
有个由小写字母组成的模式串以及一个文本串
。每个模式串可能会在文本串中出现多次。你需要找出哪些模式串在文本串
中出现的次数最多。
输入输出格式
输入格式：
输入含多组数据。
每组数据的第一行为一个正整数，表示共有
个模式串，
。
接下去行，每行一个长度小于等于
的模式串。下一行是一个长度小于等于
的文本串
。
输入结束标志为。
输出格式：
对于每组数据，第一行输出模式串最多出现的次数，接下去若干行每行输出一个出现次数最多的模式串，按输入顺序排列。
输入输出样例
输入样例#1：
2
aba
bab
ababababac
6
beta
alpha
haha
delta
dede
tata
dedeltalphahahahototatalpha
0
输出样例#1：
4
aba
2
alpha
haha 个人认为没有什么特别大的变化，记录一下，然后简单运用一下，就ok了,纯裸题，不过用c++自带的queue貌似有些慢，
应该可以优化一下。
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std; int n,cnt=,fzy[];
char s[][];
struct Node
{
int c[],suf,flag,mark;
void init()
{
suf=flag=mark=;
memset(c,,sizeof(c));
}
}tree[]; void init()
{
memset(fzy,,sizeof(fzy));
for (int i=;i<=cnt;i++)
tree[i].init();
cnt=;
}
void Ins(int num)
{
int head=,l=strlen(s[num]);
for (int i=;i<l;i++)
{
int now=s[num][i]-'a';
if (!tree[head].c[now]) tree[head].c[now]=++cnt;
head=tree[head].c[now];
}
tree[head].flag++,tree[head].mark=num;
}
void Make_AC()
{
for (int i=;i<;i++) tree[].c[i]=;
int head=,tail=;
queue<int>q;
while (!q.empty()) q.pop();
tree[].suf=;
q.push();
while (!q.empty())
{
int u=q.front();
q.pop();
for (int i=;i<;i++)
if (tree[u].c[i])
{
tree[tree[u].c[i]].suf=tree[tree[u].suf].c[i];
q.push(tree[u].c[i]);
}
else tree[u].c[i]=tree[tree[u].suf].c[i];
}
}
void Solve()
{
char s1[];
scanf("%s",s1);
int head=,len=strlen(s1);
for (int i=;i<len;i++)
{
int now=s1[i]-'a';
head=tree[head].c[now];
for (int j=head;j&&tree[j].flag!=-;j=tree[j].suf)
fzy[tree[j].mark]+=tree[j].flag;
}
int x=fzy[];
for (int i=;i<=n;i++)
if (x<fzy[i]) x=fzy[i];
printf("%d\n",x);
for (int i=;i<=n;i++)
if (x==fzy[i]) printf("%s\n",s[i]);
}
int main()
{
while (scanf("%d",&n)&&n)
{
init();
for (int i=;i<=n;i++)
{scanf("%s",s[i]);Ins(i);}
Make_AC();
Solve();
}
}