数据结构实验之串三:KMP应用
程序员文章站
2022-06-05 22:22:22
...
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int next[1000000];
int s[1000001],p[1000001];
void getnext(int plen)
{
next[0]=-1;
int k=-1,j=0;
while(j<plen-1)
{
if(k==-1||p[k]==p[j])
{
++k;
++j;
if(p[j]!=p[k])
next[j]=k;
else
next[j]=next[k];
}
else
{
k=next[k];
}
}
}
int kmp(int slen,int plen,int x)
{
int i=x,j=0;
while(i<slen&&j<plen)
{
if(j==-1||s[i]==p[j])
{
i++;j++;
}
else
{
j=next[j];
}
}
if(j>=plen) return i-j+1;
else return -1;
}
int main()
{
int n,m,i,x;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&s[i]);
scanf("%d",&m);
for(i=0;i<m;i++)
scanf("%d",&p[i]);
getnext(m);
x=kmp(n,m,0);
if(x==-1) printf("-1");
else
{
if(kmp(n,m,x)==-1) printf("%d %d",x,x+m-1);//注意题目要求为有唯一的匹配串,所以要在判断一次后面是否还有匹配串,这里容易忽略导致WA
else printf("-1");
}
return 0;
}
PS:关于KMP的思路推荐JULY的博客,讲的很详细。
https://blog.csdn.net/v_JULY_v/article/details/7041827