数据结构实验之串三：KMP应用

题目描述

有n个小朋友，每个小朋友手里有一些糖块，现在这些小朋友排成一排，编号是由1到n。现在给出m个数，能不能唯一的确定一对值l和r(l <= r)，使得这m个数刚好是第l个小朋友到第r个小朋友手里的糖块数？

输入

首先输入一个整数n，代表有n个小朋友。(0

输出

 如果能唯一的确定一对l,r的值，那么输出这两个值，否则输出-1

示例输入

5 1 2 3 4 5 3 2 3 4

示例输出

2 4

#include <stdio.h> #include <stdlib.h> #include<string.h> #define max 1000000 int m,n; int next[max]; int s1[max],s2[max]; void get_next(int s2[],int next[]) {     int i=1;     next[1]=0;     int j=0;     while(i<m)     {         if(j==0||s2[i]==s1[j])         {             i++;j++;             next[i]=j;         }         else             j=next[j];     } } void Index_KMP(int n,int m) {     int pos=1,j=1,k=0,a;     while(pos<=n&&j<=m)     {         if(j==0||s1[pos]==s2[j])         {             pos++;j++;         }         else             j=next[j];             if(j>m)             {                 j=1;k++;                 if(k==1)                 {                     a=pos;                 }             }     }    if(k==1)     {         printf("%d %d\n",a-m,a-1);     }     else         printf("-1\n"); } int main() {    int n,m,i,j;    scanf("%d",&n);    for(i=1;i<=n;i++)     scanf("%d",&s1[i]);    scanf("%d",&m);    for(j=1;j<=m;j++)     scanf("%d",&s2[j]);    get_next(s2,next);    Index_KMP(n,m);     return 0; }