题意
给定两个序列，在第一个序列中找与第二个序列相邻两数之差相同的连续子序列，能找到多少个
思路
先分别对两个子序列相邻两数做差，跑KMP，注意特判第二个序列长度为1的情况
代码
#include <cstdio>
int a[
200001],aa[
200001],b[
200001],bb[
200001],next[
200001];
int n,w;
void makenext()
{
int q,k;
next[
0]=
0;
for(q=
1,k=
0;q<w-
1;q++)
{
while(k>
0&&bb[q]!=bb[k])
k=next[k-
1];
if(bb[q]==bb[k])
k++;
next[q]=k;
}
}
int kmp()
{
int cnt=
0,i,q;
for(i=
0,q=
0;i<n-
1;i++)
{
while(q>
0&&(bb[q]!=aa[i]||q==w-
1))
q=next[q-
1];
if(bb[q]==aa[i])
q++;
if(q==w-
1)
{
cnt++;
}
}
return cnt;
}
int main()
{
scanf(
"%d%d",&n,&w);
for(
int i=
0;i<n;i++)
scanf(
"%d",&a[i]);
for(
int i=
0;i<w;i++)
scanf(
"%d",&b[i]);
for(
int i=
0;i<n-
1;i++)
aa[i]=a[i+
1]-a[i];
for(
int i=
0;i<w-
1;i++)
bb[i]=b[i+
1]-b[i];
makenext();
if(w==
1)
printf(
"%d\n",n);
else printf(
"%d\n",kmp());
return 0;
}
