（附有鄙人KMP正解和hash代码）啊啊啊啊啊啊啊啊啊，这题把我双hash都给卡了，出题人是有多巨啊，白名蒟蒻在线请求大佬们用hash试一下，谢谢

KMP正解

#include<cstdio>
#define N 1000010
using namespace std;
int a[N],b[N],n,m;
int nxt[N],ans;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=m;i++)
		scanf("%d",&b[i]);
	for(int i=1;i<n;i++)
		a[i]=a[i+1]-a[i];
	for(int i=1;i<m;i++)
		b[i]=b[i+1]-b[i];
	m--;
	for(int i=2,j=0;i<=m;i++){
		while(j>0&&b[i]!=b[j+1])j=nxt[j];
		if(b[i]==b[j+1])j++;
		nxt[i]=j;
	}
	for(int i=1,j=0;i<=n;i++){
		while(j>0&&(j==m||a[i]!=b[j+1]))j=nxt[j];
		if(a[i]==b[j+1])j++;
		if(j==m)ans++;
	}
//	if(m==0)printf("%d",n+1);
//	else
	printf("%d",ans);
}

hash代码

#include<cstdio>
#define N 1000010
using namespace std;
int a[N],b[N],n,m,ans;
unsigned long long f1[N],f2[N],pf[N],f11[N],f21[N],pf1[N];
const unsigned long long p=13331,p1=10000019,mo=1000000009;
bool check(int i){
   if(f1[i]-f1[i-m]*pf[m]!=f2[m])return 0;
   if((f11[i]-f11[i-m]*pf1[m]%mo+mo)%mo!=f21[m])return 0;
//	for(int j=i-m+1,jj=1;j<=i;j++,jj++)
//		if(a[j]!=b[jj])return 0;
   return 1;
}
int main(){
   pf[0]=1;
   pf1[0]=1;
   scanf("%d%d",&n,&m);
   for(int i=1;i<=n;i++)
   	scanf("%d",&a[i]);
   for(int j=1;j<=m;j++)
   	scanf("%d",&b[j]);
   if(m==1){printf("%d",n);return 0;}
   for(int i=1;i<n;i++)
   	a[i]=a[i+1]-a[i];
   for(int i=1;i<m;i++)
   	b[i]=b[i+1]-b[i];
//	n--,
   m--;
   for(int i=1;i<=n;i++)
   	f1[i]=f1[i-1]*p1+a[i],pf[i]=pf[i-1]*p1,f11[i]=(f11[i-1]*p+a[i])%mo,pf1[i]=pf1[i-1]*p%mo;
   for(int i=1;i<=m;i++)
   	f2[i]=f2[i-1]*p1+b[i],f21[i]=(f21[i-1]*p+b[i])%mo;
   for(int i=m;i<=n;i++)
   	if(check(i))
//		if(f1[i]-f1[i-m]*pf[m]==f2[m]&&f11[i]-f11[i-m]*pf1[m]==f21[m])
   		ans++;
   printf("%d",ans);
   return 0;
}