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

    xiaoxiao2025-01-25  9

    题目描述

    有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; }

    转载请注明原文地址: https://ju.6miu.com/read-1295767.html
    最新回复(0)