wa16,18,铅条

#include<bits/stdc++.h>
using namespace std;
const long long mod=4294967296; 
long long n,m,i,p[3000100],j,pre[3000100],p0,p1,k[3000100],l,r,mid;
long long ans;
string ss1,ss2,s1,s2;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>ss1>>ss2;
	s1.push_back('#');
	s2.push_back('#');
	for(i=n;i>=1;i--){
		s1.push_back(ss1[i-1]);
	}
	for(i=m;i>=1;i--){
		s2.push_back(ss2[i-1]);
	}
	s1.push_back('@');
	s2.push_back('@');
	j=0;
	for(i=1;i<=m;i++){
		while(j>0&&s2[j+1]!=s1[i+1]) j=p[j];
		if(s2[j+1]==s2[i+1]) j++;
		p[i+1]=j;
	}
	j=0;
	for(i=0;i<n;i++){
		while(j>0&&s1[i+1]!=s2[j+1]) j=p[j];
		if(s1[i+1]==s2[j+1]) j++;
		if(j==m){
			pre[i-m+2]=1;
			j=p[j];
		}
	}
	for(i=1;i<=n;i++){
		if(i<p1){
			k[i]=min(p1-i,k[p0*2-i]);
		}
		else{
			k[i]=1;
		}
		while(i-k[i]&&s1[i+k[i]]==s1[i-k[i]]){
			k[i]++;
		}
		if(i+k[i]>p1){
			p0=i;
			p1=i+k[i];
		}
	}
	for(i=1;i<=n;i++){
		pre[i]+=pre[i-1];
	}
	for(i=1;i<=n;i++){
		pre[i]+=pre[i-1];
	}
	for(i=1;i<=n;i++){
		if(2*k[i]-1<m){
			continue;
		}
		l=i-k[i]+1,r=i+k[i]-1;
		l--,r=r-m+1;
		mid=(l+r)>>1;
		ans=(ans+(pre[r]-pre[mid]-pre[((l+r)&1)?mid:mid-1]+pre[l-1]))%mod;
	}
	ans=ans%mod;
	cout<<ans;
	return 0;
}