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

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

Time Limit: 1000MS Memory limit: 65536K

题目描述

有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 <string.h> #include <stdlib.h> int string1[1000000],string2[1000000]; int next[1000000]; void get_next(int len) {     int i=0,j=-1;     next[0] = -1;     while(i<len)     {         if(j==-1 || string2[i]==string2[j])         {             i++;             j++;             next[i] = j;         }         else         {             j = next[j];         }     } } int Index_KMP(int x,int y,int pos) {     int i=pos,j=0;get_next(y);     while(i<x && j<y)     {         if(j==-1 || string1[i]==string2[j]) //j=-1         {             i++;             j++;         }         else         {             j = next[j];         }     }     if(j==y)     {         return i-j+1;     }     else     {         return -1;     } } int main() {     int n,i,m,x;     while(scanf("%d",&n)!=EOF){         for(i=0;i<n;i++){scanf("%d",&string1[i]);}scanf("%d",&m);for(i=0;i<m;i++){scanf("%d",&string2[i]);}x = Index_KMP(n,m,0);//找到模式串的在主串中的位置if(x!=-1){//此题要唯一确定一对l,r值；理解为确定唯一的子串，即模式串在主串中只出现一次，然后输出匹配模式串在主串中的首位置和末位置int t = Index_KMP(n,m,x+m-1);if(t!=-1){printf("-1\n");}else{printf("%d %d\n",x,x+m-1);}}else{printf("-1\n");}                   }     return 0; }

转载于:https://www.cnblogs.com/CCCrunner/p/6444627.html

相关资源：JAVA上百实例源码以及开源项目