马蜂良好:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<map>
#include<cstring>
#define ULL unsigned long long
using namespace std;
const int b=233,N=1e5+5;
int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
ULL p[N],f[N],g[N];
char s0[N],s[N];
int n,m,T,ans;
int Hash1(int l,int r){return f[r]-f[l-1]*p[r-l+1];}
int Hash2(int l,int r){return g[r]-g[l-1]*p[r-l+1];}
int get_same(int l1,int l2,int r){
int l=1,t=0;
while(l<=r){
int mid=(l+r)/2;
if(Hash1(l1,l1+mid-1)==Hash2(l2,l2+mid-1)) l=mid+1,t=mid;
else r=mid-1;
}
return t;
}
bool init(int x){
int l=x,l0=1,mb=m,r=x+m-1;
for(int i=1;i<=3;i++){
int c=get_same(l,l0,mb);
l0+=c+1,l+=c+1,mb-=c;
if(mb<=0) return 1;
}
return Hash1(l,r)==Hash2(l0,m);
}
signed main(){
T=read();
p[0]=1;
for(int i=1;i<=1e5;i++) p[i]=p[i-1]*b;
while(T--){
ans=0;
scanf("%s",s0+1);
scanf("%s",s+1);
n=strlen(s0+1),m=strlen(s+1);
if(n<m){
cout<<"0"<<endl;
continue;
}
f[0]=g[0]=0;
for(int i=1;i<=n;i++) f[i]=f[i-1]*b+s0[i];
for(int i=1;i<=m;i++) g[i]=g[i-1]*b+s[i];
for(int i=1;i+m-1<=n;i++){
if(init(i))ans++;
}
printf("%d\n",ans);
}
return 0;
}
样例过了但测试点过不了一个(并且下不到测试点),有没有人能帮忙一眼丁真一下我哪错了。