数据结构实验之串三:KMP应用

2/10/2017来源:ASP.NET技巧人气:396

think: 1、下午一直在做这个题,因为自己对KMP算法并不理解,自己错了一遍又一遍,感觉自己的心态以及迎难而上的决心并不坚决,希望自己能够尽快克服自己的情绪战胜自己对一些因素的懦弱。最后自己想写一组数据,自己认为后台判定应该加入这类数据,希望大家在下方讨论区留下自己对这组数据的见解,谢谢。 example input: 6 1 2 3 3 3 3 3 3 3 3 example output: -1

2、审题需要反思(忽略题意中唯一的确定的这一重要信息,导致反复错误)。 3、样本数据能力需要提高

sdut原题链接

数据结构实验之串三:KMP应用 Time Limit: 1000MS Memory Limit: 65536KB

PRoblem Description 有n个小朋友,每个小朋友手里有一些糖块,现在这些小朋友排成一排,编号是由1到n。现在给出m个数,能不能唯一的确定一对值l和r(l <= r),使得这m个数刚好是第l个小朋友到第r个小朋友手里的糖块数?

Input 首先输入一个整数n,代表有n个小朋友。下一行输入n个数,分别代表每个小朋友手里糖的数量。 之后再输入一个整数m,代表下面有m个数。下一行输入这m个数。

Output 如果能唯一的确定一对l,r的值,那么输出这两个值,否则输出-1

Example Input 5 1 2 3 4 5 3 2 3 4

Example Output 2 4

Hint Author windream

以下为accepted代码—建议参考

#include <stdio.h> #include <string.h> #include <stdlib.h> #define MAXN 1998414 int next[MAXN], n, m; int s[MAXN], p[MAXN]; void get_next(int p[]) { int i = 0, j = -1; next[0] = -1; while(i < m-1) { if(j == -1 || p[i] == p[j]) { i++; j++; next[i] = j; } else j = next[j]; } } int kmp(int s[], int p[], int x) { if(m == 0 || n == 0) return -1; int i = x, j = 0; memset(next, 0, sizeof(next)); get_next(p); while(i < n && j < m) { if(j == -1 || s[i] == p[j]) { i++; j++; } else j = next[j]; } if(j == m) return i-m+1; else return -1; } int main() { int i, y1, y2; while(scanf("%d", &n) != EOF) { for(i = 0; i < n; i++) { scanf("%d", &s[i]); } scanf("%d", &m); for(i = 0; i < m; i++) { scanf("%d", &p[i]); } y1 = kmp(s, p, 0); if(y1 != -1) { y2 = kmp(s, p, y1); if(y2 == -1) printf("%d %d\n", y1, y1+m-1); else printf("-1\n"); } else printf("-1\n"); } return 0; } /*************************************************** User name: jk160630 Result: Accepted Take time: 152ms Take Memory: 6284KB Submit time: 2017-02-04 16:02:35 ****************************************************/

以下为accepted代码—不符合最上方举例数据

#include <stdio.h> #include <string.h> #include <stdlib.h> #define MAXN 1998414 int next[MAXN], n, m; int s[MAXN], p[MAXN]; void get_next(int p[]) { int i = 0, j = -1; next[0] = -1; while(i < m-1) { if(j == -1 || p[i] == p[j]) { i++; j++; next[i] = j; } else j = next[j]; } } int kmp(int s[], int p[], int x) { if(m == 0 || n == 0) return -1; int i = x, j = 0; memset(next, 0, sizeof(next)); get_next(p); while(i < n && j < m) { if(j == -1 || s[i] == p[j]) { i++; j++; } else j = next[j]; } if(j == m) return i-m+1; else return -1; } int main() { int i, y1, y2; while(scanf("%d", &n) != EOF) { for(i = 0; i < n; i++) { scanf("%d", &s[i]); } scanf("%d", &m); for(i = 0; i < m; i++) { scanf("%d", &p[i]); } y1 = kmp(s, p, 0); if(y1 != -1) { y2 = kmp(s, p, y1+m-1); if(y2 == -1) printf("%d %d\n", y1, y1+m-1); else printf("-1\n"); } else printf("-1\n"); } return 0; } /*************************************************** User name: jk160630 Result: Accepted Take time: 160ms Take Memory: 6288KB Submit time: 2017-02-04 15:59:14 ****************************************************/