KMP+马拉车

#include<bits/stdc++.h>
using namespace std;
string s,c;
string s2;
vector<int> km;
int lm[400010],rm[400010];
int next[400010];
int p[400010],n,mx = 0,id = 0;
long long a[400010];
long long sigf[4000010];
long long sigs[4000010];
const long long Mo = 4294967296ll;
void KMP(){
	int v1 = -1;
	next[0] = -1;
	for(int i = 0; i < s2.length(); ){
		if(v1==-1||s2[i]==s2[v1]){
			i++,v1++;
			next[i] = v1;
		} else v1 = next[v1];
	}
	v1 = 0;
	for(int i = 0; i < s.length(); ){
		if(v1==-1||s[i]==s2[v1]) i++,v1++;
		else v1 = next[v1];
		if(v1==s2.length()){
			a[i-s2.length()] = 1;
			km.push_back(i-s2.length()+1);
			v1 = next[v1];
		}
	}
}
int r[4000010],pos = 0;
int mein,meik;
int main(){
	cin >> mein >> meik;
	cin >> s >> s2;
	KMP();
	n = s.length();
	c.push_back('!');
	for(int i = 1; i <= n; i++){
		c.push_back('$');
		c.push_back(s[i-1]);
	}
	c.push_back('$');
	c.push_back('@');
	c.push_back('0');
	for(int i = 1; i <= 2*n+3; i++){
		p[i] = (mx>i?min(p[2*id-i],mx-i):1);
		while(i-p[i]>=1&&i+p[i]<=2*n+3&&c.at(i-p[i])==c.at(i+p[i])){
			p[i]++;
		}
		if(i+p[i]>mx){
			mx = i+p[i];
			id = i;
		}
		if(c[i]<='z'&&c[i]>='a'){
			r[pos] = p[i]-1;
			pos++;
		}
	}
	sigf[0] = a[0],sigs[0] = a[0];
	for(int i = 1; i < s.length(); i++){
		sigf[i] = a[i]+sigf[i-1];
		sigs[i] = sigf[i]+sigs[i-1];
	}
	int ans = 0;
	for(int i = 0; i < s.length(); i++){
		int L = i-(r[i]-1)/2,R = i+(r[i]-1)/2-s2.length()+1;
		int dist = (R-L)/2;
		ans = ans+(sigs[R]-sigs[max(0,R-dist-1)]-sigs[max(0,L+dist-1)]+sigs[max(0,L-2)]);
		ans%=Mo;
	}
	printf("%d",ans);
	return 0;
}