sdut原題鏈接 bLue的文件查找器 Time Limit: 1000MS Memory Limit: 65536KB
PRoblem Description bLue 的電腦里存了各種各樣的文件，隨著文件越來(lái)越多，查找文件也成了一個(gè)麻煩事。 現(xiàn)在，他想要查找所有指定格式（擴(kuò)展名）的文件，不過(guò)他并不會(huì)使用文件管理器自帶的搜索功能，所以他想求你寫(xiě)一個(gè)文件查找器，來(lái)幫他查找所有指定格式的文件。
Input 輸入數(shù)據(jù)有多組（數(shù)據(jù)組數(shù)不超過(guò) 100），到 EOF 結(jié)束。 對(duì)于每組數(shù)據(jù)： 第一行輸入一個(gè)整數(shù) n (1 <= n <= 100) 和一個(gè)長(zhǎng)度不超過(guò) 5 的字符串 ex，分別表示文件夾內(nèi)的文件數(shù)量和要查找的文件的擴(kuò)展名。 接下來(lái)的 n 行，每行輸入一個(gè)完整文件名。保證文件名不包含空格且長(zhǎng)度不超過(guò) 100。
Output 對(duì)于每組數(shù)據(jù)，按照輸入順序輸出文件夾內(nèi)所有擴(kuò)展名符合查找要求的文件名。
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 文件名后綴前面應(yīng)該有符號(hào)“.”（不帶括號(hào)） 2 Example Input 2 cpp 3717.ccpp 3717.cpp
Example Output 3717.cpp
Author 「2016年第六屆ACM趣味編程循環(huán)賽 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;///靈活溝通配對(duì)起始位置（） ///可以通過(guò)i的初始值靈活溝通配對(duì)起始位置，可以通過(guò)len1的值靈活溝通配對(duì)終點(diǎn)位置 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;///靈活溝通配對(duì)起始位置（） ///可以通過(guò)i的初始值靈活溝通配對(duì)起始位置，可以通過(guò)len1的值靈活溝通配對(duì)終點(diǎn)位置 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 文件的擴(kuò)展名的格式要求
新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
