KMP算法的初级扩展应用

2019-11-11 04:48:07

字体：大中小

来源：转载

供稿：网友

sdut原题链接 bLue的文件查找器 Time Limit: 1000MS Memory Limit: 65536KB

PRoblem Description bLue 的电脑里存了各种各样的文件，随着文件越来越多，查找文件也成了一个麻烦事。现在，他想要查找所有指定格式（扩展名）的文件，不过他并不会使用文件管理器自带的搜索功能，所以他想求你写一个文件查找器，来帮他查找所有指定格式的文件。

Input 输入数据有多组（数据组数不超过 100），到 EOF 结束。对于每组数据：第一行输入一个整数 n (1 <= n <= 100) 和一个长度不超过 5 的字符串 ex，分别表示文件夹内的文件数量和要查找的文件的扩展名。接下来的 n 行，每行输入一个完整文件名。保证文件名不包含空格且长度不超过 100。

Output 对于每组数据，按照输入顺序输出文件夹内所有扩展名符合查找要求的文件名。

Example Input 6 cpp 3717.cpp xunhuansai_daima.zip xunhuansai_jietibaogao.pdf C.cpp bLue.jpg cyk_de_richang.mp4

Example Output 3717.cpp C.cpp

Hint 1 文件名后缀前面应该有符号“.”（不带括号） 2 Example Input 2 cpp 3717.ccpp 3717.cpp

Example Output 3717.cpp

Author 「2016年第六届ACM趣味编程循环赛 Round #2」bLue

以下为accepted代码

#include <stdio.h>#include <string.h>#define MAXN 140char s[MAXN], p[9];int next[9];void get_next(char *p){ next[0] = -1;///初始化 int i = 0, j = -1; int len = strlen(p); while(i < len-1) { if(j == -1 || p[i] == p[j]) { i++; j++; next[i] = j; } else j = next[j];//失配回溯 }}int kmp(char *s, char *p){ get_next(p); int len1 = strlen(s); int len2 = strlen(p); int i = len1-len2, j = 0;///灵活沟通配对起始位置（） ///可以通过i的初始值灵活沟通配对起始位置，可以通过len1的值灵活沟通配对终点位置 if(s[i-1] != '.') return -1; while(i < len1 && j < len2) { if(j == -1 || s[i] == p[j]) { i++; j++; } else j = next[j];//失配回溯 } if(j == len2) return 1; else return -1;}int main(){ int n; while(scanf("%d %s", &n, p) != EOF) { while(n--) { scanf("%s", s); if(kmp(s, p) == 1) printf("%s/n", s); } } return 0;}/***************************************************User name: jk160630Result: AcceptedTake time: 4msTake Memory: 108KBSubmit time: 2017-02-06 21:14:04****************************************************/

以下为wrong answer代码

#include <stdio.h>#include <string.h>#define MAXN 140char s[MAXN], p[9];int next[9];void get_next(char *p){ next[0] = -1;///初始化 int i = 0, j = -1; int len = strlen(p); while(i < len-1) { if(j == -1 || p[i] == p[j]) { i++; j++; next[i] = j; } else j = next[j];//失配回溯 }}int kmp(char *s, char *p){ get_next(p); int len1 = strlen(s); int len2 = strlen(p); int i = len1-len2, j = 0;///灵活沟通配对起始位置（） ///可以通过i的初始值灵活沟通配对起始位置，可以通过len1的值灵活沟通配对终点位置 while(i < len1 && j < len2) { if(j == -1 || s[i] == p[j]) { i++; j++; } else j = next[j];//失配回溯 } if(j == len2) return 1; else return -1;}int main(){ int n; while(scanf("%d %s", &n, p) != EOF) { while(n--) { scanf("%s", s); if(kmp(s, p) == 1) printf("%s/n", s); } } return 0;}/***************************************************User name: jk160630Result: Wrong AnswerTake time: 4msTake Memory: 108KBSubmit time: 2017-02-06 21:10:04****************************************************/

wrong answer cause: 1 文件的扩展名的格式要求

上一篇：C#多线程与异步的区别

下一篇：C语言低级错误案例