题目描述
有NN个由小写字母组成的模式串以及一个文本串TT。每个模式串可能会在文本串中出现多次。你需要找出哪些模式串在文本串TT中出现的次数最多。
输入输出格式
输入格式：
输入含多组数据。
每组数据的第一行为一个正整数NN，表示共有NN个模式串，1 \leq N \leq 1501≤N≤150。
接下去NN行，每行一个长度小于等于7070的模式串。下一行是一个长度小于等于10^6106的文本串TT。
输入结束标志为N=0N=0。
输出格式：
对于每组数据，第一行输出模式串最多出现的次数，接下去若干行每行输出一个出现次数最多的模式串，按输入顺序排列。
输入输出样例
输入样例#1：
2
aba
bab
ababababac
6
beta
alpha
haha
delta
dede
tata
dedeltalphahahahototatalpha
0
输出样例#1：
4
aba
2
alpha
haha ac自动机，last指针版
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int maxn = ;
int n;
char s[maxn][];
char ss[maxn*];
int ans=;
struct Aho_Corasick_automato {
int sz;
int ch[maxn][];
int cnt[maxn];
int val[maxn];
int last[maxn];
int fail[maxn];
int num;
void init() {
memset(ch[],,sizeof(ch[]));
memset(cnt,,sizeof(cnt));
sz=;
}
void insert(char *s,int num) {
int len=strlen(s);
int u=;
for(int i=; i<len; ++i) {
int v=(s[i]-'a');
if(!ch[u][v]) {
memset(ch[sz],,sizeof(ch[sz]));
val[sz]=;
ch[u][v]=sz++;
}
u=ch[u][v];
}
val[u]=num;
}
void get_fail() {
fail[]=;
queue<int>que;
for(int i=; i<; i++) {
int u=ch[][i];
if(u) {
fail[u]=;
que.push(u);
}
}
while(!que.empty()) {
int u=que.front();
que.pop();
for(int i=; i<; i++) {
int v=ch[u][i];
if(!v) {
ch[u][i]=ch[fail[u]][i];
continue;
}
que.push(v);
int k=fail[u];
fail[v]=ch[k][i];
last[v]=val[fail[v]] ? fail[v] : last[fail[v]];
}
}
}
void work(int x) {
if(x) {
cnt[val[x]]++;
work(last[x]);
}
}
void find(char *s) {
int len=strlen(s);
int u=;
for(int i=; i<len; i++) {
int v=(s[i]-'a');
if(!ch[u][v])u=fail[u];
while(u&&!ch[u][v])
u=fail[u];
u=ch[u][v];
if(val[u])
work(u);
else if(last[u])
work(last[u]);
}
}
} ac; int main() { while(scanf("%d",&n)==&&n!=) {
ac.init();
for(int i=; i<=n; i++) {
scanf("%s",s[i]);
ac.insert(s[i],i);
}
ac.get_fail();
scanf("%s",ss);
ac.find(ss);
int ans=,r;
for(int i=;i<=n;i++)
if(ac.cnt[i]>ans)ans=ac.cnt[i],r=i;;
printf("%d\n",ans);
for(int r=;r<=n;r++)
if(ac.cnt[r]==ans)
printf("%s\n",s[r]);
}
return ;
}