数据结构实验之串三：KMP应用
TimeLimit: 1000MS Memory Limit: 65536KB
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 45
3
2 3 4
Example Output
2 4
Hint
Author
windream
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
using namespace std;
int next[2000000],n,m;
/*void qnext(int *p,int next[])
{
next[0] = -1;
int k = -1;//k表示前缀，j表示后缀
int j = 0;
while(j <m - 1)
{
if(k==-1||p[j] == p[k])
{
++j;
++k;
if(p[j]!=p[k])
next[j] = k;
else //因为不能出现p[j] = p[ next[j ]]，
//所以当出现 其 时需要继续递归，k = next[k] = next[next[k]]
next[j] = next[k];
}
else
{
k = next[k];
}
}
}
int kmp(int *s,int *p)
{
int i = 0;
int j = 0;
int slen = strlen(s);
int plen = strlen(p);
while(i < n&& j<m)
{
if(j == -1||s[i]== p[j])//j==-1,表明处于一开始，或者完全失配，此时主串下移一位，模式串归零
{
i++;
j++;
}
else
{
j = next[j];
}
}
if(j == m)
return i-j;
else
return -1;
}
*/
void qnext(int *p,int next[])
{
int i,k;
next[0] = 0;
for(i=1,k=0;p[i];i++)
{
while(k>0&&p[k]!=p[i])k = next[k-1];
if(p[k]==p[i])k++;
next[i] = k;
}
}
int kmp(int *s,int *p)
{
int i,k;
int cnt = 0,temp;
for(i=0,k=0;s[i];i++)
{
while(k>0&&p[k]!=s[i])k = next[k-1];
if(p[k]==s[i])k++;
if(k==m){cnt++;
if(cnt==1)temp = i-k+1;}
}
if(cnt==1) return temp;
else return -1;
}
int main()
{
int i;
int s[2000000],p[2000000];
while(cin>>n)
{
for(i=0;i<n;i++)
{
scanf("%d",&s[i]);
}
cin>>m;
for(i=0;i<m;i++)
{
scanf("%d",&p[i]);
}
qnext(p,next);
int o = kmp(s,p);
if(o==-1)
cout<<o<<endl;
else
cout<<o+1<<' '<<o+m<<endl;
}
return 0;
}
/***************************************************
User name: jk160508孙振强
Result: Wrong Answer
Take time: 48ms
Take Memory: 1148KB
Submit time: 2017-02-07 21:09:43
****************************************************/
/***************************************************
User name: jk160505徐红博
Result: Wrong Answer
Take time: 168ms
Take Memory: 2308KB
Submit time: 2017-02-07 22:15:53
****************************************************/
/***************************************************
User name: jk160505徐红博
Result: Accepted
Take time: 160ms
Take Memory: 2596KB
Submit time: 2017-02-13 19:51:14
****************************************************/
京公网安备 11010502036488号