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****************************************************/新聞熱點
疑難解答
