有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; }新聞熱點
疑難解答
