有n個(gè)小朋友，每個(gè)小朋友手里有一些糖塊，現(xiàn)在這些小朋友排成一排，編號(hào)是由1到n。現(xiàn)在給出m個(gè)數(shù)，能不能唯一的確定一對(duì)值l和r(l <= r)，使得這m個(gè)數(shù)剛好是第l個(gè)小朋友到第r個(gè)小朋友手里的糖塊數(shù)？ Input
首先輸入一個(gè)整數(shù)n，代表有n個(gè)小朋友。下一行輸入n個(gè)數(shù)，分別代表每個(gè)小朋友手里糖的數(shù)量。
之后再輸入一個(gè)整數(shù)m，代表下面有m個(gè)數(shù)。下一行輸入這m個(gè)數(shù)。 Output
如果能唯一的確定一對(duì)l,r的值，那么輸出這兩個(gè)值，否則輸出-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;//存儲(chǔ)對(duì)稱與當(dāng)前字符對(duì)稱的子串的末尾所在位置 while(i++<slen) { j=next[i-1];//取出前一字符所在位置的對(duì)稱信息 while(str[i]!=str[j+1]&&j>=0)//如果這個(gè)字符與前一字符對(duì)應(yīng)對(duì)稱子串的末尾的下一字符不相同， 循環(huán)尋找 { 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存儲(chǔ)的為比較點(diǎn)前面的信息 { if(str[j]==ptr[i+1]) { i++; j++; } else { if(i==-1) { j++; } else { i=next[i];//進(jìn)行該步驟后i仍然為比較點(diǎn)前面的信息 } } 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; }新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
