思路是前缀和维护前缀和，sum[0][i]维护的是以i为右端点的s2出现次数，sum[1]维护的是sum[0]的前缀和。求调错 or hack

#include<bits/stdc++.h>
#define rep(a,b,c) for(int a=b;a<=c;a++)
using namespace std;
typedef long long ll;
const int MAXN=3e6+5;
int n,m,mid,mr,p[MAXN],nxt[MAXN];
ll sum[2][MAXN];
string a,b;
unsigned int ans;
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	cin>>a>>b;
	n=a.length(),m=b.length();
	a=' '+a,b=' '+b;
	int j=0;
	rep(i,2,m){
		while(j&&b[j+1]!=b[i])j=nxt[j];
		if(b[j+1]==b[i])j++;
		nxt[i]=j;
	}
	j=0;
	rep(i,1,n){
		while(j&&b[j+1]!=a[i])j=nxt[j];
		if(b[j+1]==a[i])j++;
		sum[0][i]=sum[0][i-1];
		if(j==m)sum[0][i]++,j=0;
	}
	rep(i,1,n)sum[1][i]=sum[1][i-1]+sum[0][i];
	
	rep(i,1,n){
		if(i<=mr)p[i]=min(mr-i+1,p[mid*2-i]);
		while(a[i-p[i]]==a[i+p[i]])p[i]++;
		if(i+p[i]>mr)mr=i+p[i]-1,mid=i;
		p[i]--;
	}
	rep(i,1,n){
		if(p[i]*2+1<m)continue;
		ans+=sum[1][min(i+p[i],n)]-sum[1][max(i+m/2-1,0)]-(sum[1][max(i-m/2+m-2,0)]-sum[1][max(i-p[i]+m-3,0)]);
		//cout<<i<<' '<<ans<<endl;
		//cout<<"xx  "<<sum[1][i+p[i]]<<' '<<sum[1][i+m/2-1]<<' '<<sum[1][i-m/2+m-2]<<' '<<sum[1][i-p[i]+m-2]<<endl;
	}
//	cout<<endl;
//	rep(i,1,n)cout<<sum[0][i]<<' ';
//	cout<<endl;
//	rep(i,1,n)cout<<sum[1][i]<<' ';
//	cout<<endl;
	cout<<ans<<endl;
	return 0;
}