有n个小朋友，每个小朋友手里有一些糖块，现在这些小朋友排成一排，编号是由1到n。现在给出m个数，能不能唯一的确定一对值l和r(l <= r)，使得这m个数刚好是第l个小朋友到第r个小朋友手里的糖块数？ Input
首先输入一个整数n，代表有n个小朋友。下一行输入n个数，分别代表每个小朋友手里糖的数量。
之后再输入一个整数m，代表下面有m个数。下一行输入这m个数。 Output
如果能唯一的确定一对l,r的值，那么输出这两个值，否则输出-1 Example Input
51 2 3 4 532 3 4Example Output
2 4Hint Author windream
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <bits/stdc++.h> #define N 1010000 int i2, j2; void getnext(int *str, int *next, int slen) { int i=0, j; next[0]=-1;//存储对称与当前字符对称的子串的末尾所在位置 while(i++<slen) { j=next[i-1];//取出前一字符所在位置的对称信息 while(str[i]!=str[j+1]&&j>=0)//如果这个字符与前一字符对应对称子串的末尾的下一字符不相同， 循环寻找 { j=next[j]; } if(str[i]==str[j+1])next[i]=j+1;//如果匹配 else next[i]=-1; } } bool kmp(int *str, int slen, int *ptr , int plen, int *next) { int top=0; int i=-1, j=0; while(j<slen)//next存储的为比较点前面的信息 { if(str[j]==ptr[i+1]) { i++; j++; } else { if(i==-1) { j++; } else { i=next[i];//进行该步骤后i仍然为比较点前面的信息 } } if(i==plen-1) { i2=j-i; j2=j; top++; } } if(top==1)return true; else return false; } int main() { int str[N]={0}; int ptr[N]={0}; int next[N]; int slen, plen; while(~scanf("%d", &slen)) { for(int a=0; a<slen; a++) scanf("%d", &str[a]); scanf("%d", &plen); for(int a=0; a<plen; a++) scanf("%d", &ptr[a]); //slen = strlen( str ); //plen = strlen( ptr ); getnext( ptr, next, plen); if(kmp(str, slen,ptr,plen, next))printf("%d %d/n", i2, j2); else printf("-1/n"); } return 0; }新闻热点
疑难解答
