Number Sequence
点击打开链接kmp,就是问你第二个数组在第一个数组第一次出现的位置,如果没出现返回-1;#include<algorithm>#include<iostream>#include<string.h>#include<string>#include<stdio.h&g
·
kmp,就是问你第二个数组在第一个数组第一次出现的位置,如果没出现返回-1;
#include<algorithm>
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
using namespace std;
int a[1000003];
int b[10003];
int n,m;
void Getnext(int *p,int next[])
{
int k=-1;
int j=0;
next[0]=-1;
while(j<m)
{
if(p[j]==p[k]||k==-1)
{
++j;
++k;
if(p[j]!=p[k])
next[j]=k;
else
next[j]=next[k];
}
else
k=next[k];
}
}
int KMPSearch(int *s,int *p,int next[])
{
int i=0;
int j=0;
while(i<n&&j<m)
{
if(s[i]==p[j]||j==-1)
{
i++;
j++;
}
else
j=next[j];
}
if(j==m)
return i-j+1;
else
return -1;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=0; i<n; i++)
scanf("%d",&a[i]);
for(int i=0; i<m; i++)
scanf("%d",&b[i]);
int next[10003];
memset(next,0,sizeof(next));
Getnext(b,next);
printf("%d\n",KMPSearch(a,b,next));
}
}
更多推荐
所有评论(0)
您需要登录才能发言
查看更多评论
已为社区贡献1条内容