首页 > 代码库 > NYOj-1085-数单词改编-KMP
NYOj-1085-数单词改编-KMP
数单词
时间限制:2000 ms | 内存限制:120000 KB
难度:4
- 描述
- 为了能够顺利通过英语四六级考试,现在大家每天早上都会早起读英语。LYH本来以为自己在6月份的考试中可以通过六级,可是没想到,成绩出来以后,居然没有通过。所以他不得不付出更多的时间来学习英语。要想通过六级,最基本的要求就是词汇量。为了能够更快的记住一些陌生单词,LYH有时会找一些英语文章来读。今天早上,LYH又找了一篇文章。读之前,他突然萌生出一个想法:文章中哪些单词出现的次数最多呢?
- 输入
- 第一行输入一个整数T,表示有T组测试数据(1≤T≤200)。
对于每组测试数据,第一行输入一个整数n(1≤n≤150),表示LYH要查询的单词数量(有些单词可能会重复出现)。
接下来n行,每行输入一个单词,长度不大于100。
最后一行包含一个由小写字母组成的英语文章(字符串),长度不大于10^6。 - 输出
- 对于每组数据,第一行输出一个整数,表示单词出现的次数。
然后按照输入顺序,每行输出一个出现次数最多的单词。如果有重复出现的单词,输出最先出现的。 - 样例输入
2 3 good oo one goodafternooneveryone 1 to welcometotopcoder
- 样例输出
oo to
- 来源
原创
Jason Yang
#include <stdio.h> #include <string.h> #include <string> #include <math.h> #include <stdlib.h> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include<queue> #include<stack> using namespace std; char s1[1000010]; char s2[101]; int next[101]; char str[200][200]; void get_next(char *t) { int i,j; i=0; j=-1; next[0]=-1; int len_t=strlen(t); while(i<len_t) { if(j==-1||t[i]==t[j]) { ++i; ++j; if(t[i]==t[j]) next[i]=next[j]; else next[i]=j; } else { j=next[j]; } } } int KMP(char *s,char *t) { get_next(t); int len_s=strlen(s); int len_t=strlen(t); int i,j; i=j=-1; int num=0; while(i<len_s) { if(j==-1||s[i]==s[j]) { ++i; ++j; } else { j=next[j]; } if(j==len_t) { j=next[j]; num++; } } return num; } int main() { int T; scanf("%d",&T); while(T--) { int MAX,now,n; scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%s",str[i]); } scanf("%s",s1); MAX=-1; for(int i=0;i<n;i++) { now=KMP(s1,str[i]); if(now>=MAX) { MAX=now; strcpy(s2,str[i]); } } printf("%s\n",s2); } return 0; }
NYOj-1085-数单词改编-KMP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。