/**
链接:http://vjudge.net/problem/UVALive-4670
详见lrj训练指南P216
*/
#include<bits/stdc++.h>
using namespace std;
#define P pair<int,int>
#define ms(x,y) memset(x,y,sizeof x)
#define LL long long
const int maxn = ;
const int mod = 1e9+;
const int maxnode = *;
const int sigma_size = ;
map<string,int> mp;
int cnt[];
struct AhoCorasickAutomata
{
int ch[maxnode][sigma_size];
int val[maxnode];
int sz;
int f[maxnode];
int last[maxnode];
void clear(){sz = ; memset(ch[],,sizeof ch[]); }
int idx(char c){return c-'a'; } void insert(char *s,int v)
{
int u = , n = strlen(s);
for(int i = ; i < n; i++){
int c = idx(s[i]);
if(!ch[u][c]){
memset(ch[sz], , sizeof ch[sz]);
val[sz] = ;
ch[u][c] = sz++;
}
u = ch[u][c];
}
val[u] = v;
} void find(char *T){
int n = strlen(T);
int j = ;
for(int i = ; i < n; i++){
int c = idx(T[i]);
//while(j&&!ch[j][c]) j = f[j];
j = ch[j][c];
if(val[j]) print(j);
else if(last[j]) print(last[j]);
}
} void print(int j)
{
if(j){
cnt[val[j]]++;
print(last[j]);
}
} void getFail(){
queue<int> q;
f[] = ;
for(int c = ; c < sigma_size; c++){
int u = ch[][c];
if(u){f[u] = ; q.push(u); last[u] = ;}
} while(!q.empty()){
int r = q.front(); q.pop();
for(int c = ; c < sigma_size; c++){
int u = ch[r][c];
if(!u){
ch[r][c] = ch[f[r]][c]; continue;
}//if(!u) continue;
q.push(u);
int v = f[r];
while(v&&!ch[v][c]) v = f[v];
f[u] = ch[v][c];
last[u] = val[f[u]] ? f[u] : last[f[u]];
}
}
} } ac ;
char a[][];
char s[];
int main()
{
int n;
while(scanf("%d",&n)==&&n)
{
ac.clear();
mp.clear();
memset(cnt, , sizeof cnt);
for(int i = ; i <= n; i++){
scanf("%s",a[i]);
ac.insert(a[i],i);
mp[string(a[i])] = i;
}
scanf("%s",s);
ac.getFail();
ac.find(s);
int mas = ;
for(int i = ; i <= n; i++){
if(cnt[i]>mas){mas = cnt[i];}
}
printf("%d\n",mas);
for(int i = ; i <= n; i++){
if(cnt[mp[string(a[i])]]==mas){
printf("%s\n",a[i]);
}
}
}
return ;
}

最新文章

  1. 第五章 springboot + mybatis(转载)
  2. TP框架实现分页
  3. nginx正向代理,反向代理,透明代理(总结)
  4. php parallel
  5. HW5.28
  6. bootstrap和jQuery.Gantt的css冲突问题
  7. lua的几个时间相关处理函数
  8. 贴片方式COB COF COG
  9. Class类对象的三种实例化方法
  10. MFC常用控件CListCtrl 、CSliderCtrl、CToolTipCtrl、CTreeCtrl的自绘
  11. Java异常处理机制以及try-catch-finally-return执行顺序
  12. JAVA通过Gearman实现MySQL到Redis的数据同步(异步复制)
  13. PHP生成验证码
  14. P1361 小M的作物
  15. 网络协议 17 - HTTPDNS:私人定制的 DNS 服务
  16. jquery的优良继承方法
  17. python3 线程池-threadpool模块与concurrent.futures模块
  18. HDFS 异构储存配置及基本命令操作
  19. Faster RCNN代码解析
  20. 清理tomcat缓存

热门文章

  1. Java虚拟机学习 - 内存调优 ( 9 )
  2. 简单的WPS二次开发脚本
  3. eclipse3.7之后,在引入的jquery的js文件打红叉
  4. 使用SplashScreenManager控件定制程序加载页面
  5. ntp服务的细节全解析
  6. [Mongodb] 借mongodb被入侵勒索事件,谈下Linux服务器端口安全问题
  7. jvm 性能调优 经验总结---转
  8. python学习之itsdangerous模块
  9. USB设备驱动程序学习笔记(一)
  10. java.util.logging.Logger日志生成过程浅析 (转)