KMP的应用

数据结构实验之串三：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;}