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

2/10/2017来源:ASP.NET技巧人气:1537

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

5 1 2 3 4 5 3 2 3 4

Example Output

2 4

Hint Author windream

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <bits/stdc++.h> #define N 1010000 int i2, j2; void getnext(int *str, int *next, int slen) { int i=0, j; next[0]=-1;//存储对称与当前字符对称的子串的末尾所在位置 while(i++<slen) { j=next[i-1];//取出前一字符所在位置的对称信息 while(str[i]!=str[j+1]&&j>=0)//如果这个字符与前一字符对应对称子串的末尾的下一字符不相同, 循环寻找 { j=next[j]; } if(str[i]==str[j+1])next[i]=j+1;//如果匹配 else next[i]=-1; } } bool kmp(int *str, int slen, int *ptr , int plen, int *next) { int top=0; int i=-1, j=0; while(j<slen)//next存储的为比较点前面的信息 { if(str[j]==ptr[i+1]) { i++; j++; } else { if(i==-1) { j++; } else { i=next[i];//进行该步骤后i仍然为比较点前面的信息 } } if(i==plen-1) { i2=j-i; j2=j; top++; } } if(top==1)return true; else return false; } int main() { int str[N]={0}; int ptr[N]={0}; int next[N]; int slen, plen; while(~scanf("%d", &slen)) { for(int a=0; a<slen; a++) scanf("%d", &str[a]); scanf("%d", &plen); for(int a=0; a<plen; a++) scanf("%d", &ptr[a]); //slen = strlen( str ); //plen = strlen( ptr ); getnext( ptr, next, plen); if(kmp(str, slen,ptr,plen, next))printf("%d %d\n", i2, j2); else printf("-1\n"); } return 0; }