WA #6 #10 #15 #16 #19 #20

真的不会了/kk

#include<iostream>
#include<cstdio>
using namespace std;
namespace INPUT{
	char buf[1<<20],*p1,*p2;
	#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
}
using namespace INPUT;
template<typename T>
T read(){
	T x=0,p=1;
	char ch=gc();
	for(;ch<'0'||ch>'9';ch=gc())
		if(ch=='-') p=-1;
	for(;'0'<=ch&&ch<'9';ch=gc())
		x=(x<<3)+(x<<1)+(ch^48);
	return x*p;
}
#define ll long long
const ll mod=(1ll<<32);
ll ans;
const int N=6e6+5;
int n,m;
char str[N],s[N];
int r[N];
void manacher(){
	str[0]='#',str[n+1]='~';
	int mid=0,R=0;
	for(int i=1;i<=n;i++){
		if(i<=R) r[i]=min(r[mid*2-i],R-i);
		else r[i]=1;
		while(str[i+r[i]]==str[i-r[i]]) r[i]++;
		if(i+r[i]-1>R) R=i+r[i]-1,mid=i;
	}
}
int fail[N];
void build_fail(){
	for(int j=0,i=2;i<=m;i++){
		while(j&&s[i]!=s[j+1]) j=fail[j];
		if(s[i]==s[j+1]) j++;
		fail[i]=j;
	}
}
bool match[N];
ll sum[N],ssum[N];
void init(){
	for(int j=0,i=1;i<=n;i++){
		while(j&&str[i]!=s[j+1]) j=fail[j];
		if(str[i]==s[j+1]) j++;
		if(j==m){
			match[i]=true;
			j=fail[j];
		}
	}
	for(int i=1;i<=n;i++) sum[i]=(sum[i-1]+match[i])%mod;
	for(int i=1;i<=n;i++) ssum[i]=(ssum[i-1]+sum[i])%mod;
}
int main(){
	// freopen("P6216.in","r",stdin);
	// freopen("P6216.out","w",stdout);
	n=read<int>(),m=read<int>();
	char ch=gc();
	while(ch<'a'||ch>'z') ch=gc();
	for(int i=1;i<=n;i++) str[i]=ch,ch=gc();
	while(ch<'a'||ch>'z') ch=gc();
	for(int i=1;i<=m;i++) s[i]=ch,ch=gc();
	manacher(),build_fail();
	init();
	auto get_ssum=[](int x){
		return x>0?ssum[x]:0;
	};
	for(int i=1;i<=n;i++){
		int L=i-r[i]+1,R=i+r[i]-1;
		if(R-L+1-m<0) continue;
		int H=(R-L+1-m)/2;
		// for(int j=0;j<=H;j++){
		// 	if(sum[R-j]-sum[L+j-1]){
		// 		cout<<"pos:"<<L+j<<' '<<R-j<<endl;
		// 		cout<<sum[R-j]-sum[L+m-2+j]<<endl;
		// 	}
		// }
		ans+=(get_ssum(R)-get_ssum(R-H-1))%mod
			-(get_ssum(L+m-2+H)-get_ssum(L+m-2-1))%mod;
		ans%=mod;
		// cout<<i<<' '<<L<<' '<<R<<' '
		// 	<<(ssum[R]-ssum[R-H-1])-(ssum[L+m-2+H]-ssum[L+m-2-1])<<endl;
	}
	printf("%lld\n",(ans+mod)%mod);
}
/*
R-L=(i+r[i]-1)-(i-r[i]+1)-1
   =2*r[i]-3

\sum_{j=0}^{r[i]}
	{[L+j,R-j]} [(R-j)-(L+j)+1>=m]

对于限制[(R-j)-(L+j)+1>=m]可化为
1.[(R-j)-(L+j)+1>=m]=[2*j<=R-L+1-m]

2.[R-L-2*j+1>=m]=[2*r[i]-2*j-2>=m]=[2*r[i]-2-m>=2*j]
=[2*j<=2*r[i]-2-m]=[j<=(2*r[i]-2-m+1)/2]

令H=(2*r[i]-2-m+1)/2或(R-L+1-m)/2;
\sum_{j=0}^{H}  {sum[R-j]-sum[L+j-1]} :错误
				{sum[R-j]-sum[L+j+m-1-1]}
				{sum[R-j]-sum[L+m-2+j]}
(ssum[R]-ssum[R-H-1])-(ssum[L+m-2+H]-ssum[L+m-2-1])
*/