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

2019-11-14 10:47:23

字体：大中小

来源：转载

供稿：网友

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 1998414int 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: jk160630Result: AcceptedTake time: 152msTake Memory: 6284KBSubmit time: 2017-02-04 16:02:35****************************************************/

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

#include <stdio.h>#include <string.h>#include <stdlib.h>#define MAXN 1998414int 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: jk160630Result: AcceptedTake time: 160msTake Memory: 6288KBSubmit time: 2017-02-04 15:59:14****************************************************/

上一篇：1045. Favorite Color Stripe (30)

下一篇：大型网站架构之分布式消息队列