數據結構實驗之串三：KMP應用

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

51 2 3 4 532 3 4
Example Output
2 4
Hint
Author
windream思路解析：典型的KMP問題，只要將模板寫下，然后根據題意，寫出細節就好了。#include<stdio.h>int a[100000009],b[100000009];int next[100000010],n,m;void Next(){    next[0]=-1;    for(int j=1;j<m;j++)    {        int i=next[j-1];        while(b[j]!=b[i+1]&&i>=0)        {            i=next[i];        }        if(b[j]==b[i+1])            next[j]=i+1;        else            next[j]=-1;    }}int KMP(int a[],int b[]){    Next();   int p=0,s=0;   while(p<m&&s<n)   {       if(a[s]==b[p])       {           s++;           p++;       }       else       {           if(p==0)            s++;           else            p=next[p-1]+1;       }   }   if(p<m)    return -1;   else    return s-m+1;}int main(){    int i, k, t;    while(scanf("%d",&n)!=EOF)    {        for(i=0;i<n;i++)        scanf("%d",&a[i]);        scanf("%d",&m);    for(i=0;i<m;i++)        scanf("%d",&b[i]);    k = KMP(a,b);    if(k!=-1)    {        t = KMP(a+k,b);        if(t==-1)            printf("%d %d/n", k, k+m-1);        else            printf("-1/n");    }    else        printf("-1/n");}  return 0;}