(附有鄙人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;
}