代码在这里

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const long long int MAXN=4e6+5;
long long int Len1,Len2,P[MAXN],Next[MAXN]={0};
char Str1[MAXN],Str2[MAXN];
long long int  Match[MAXN],Sum[MAXN],Ans=0;
long long int getSum(long long int b,long long int a){return Sum[a]-Sum[b-1];}
inline void Manacher(){
    long long int R=0,Mid=0;
    for(register long long int i=1;i<=Len1;++i){
        if(i<=R)
            P[i]=min(P[Mid*2-i],R-i+1);
        while(Str1[i+P[i]]==Str1[i-P[i]])
            ++P[i];
        if(i+P[i]>R){
            R=i+P[i]-1;
            Mid=i;
        }
    }
    /* for(long long int i=1;i<=Len1;++i)
        cout<<P[i]<<" "; */
}
inline void getNext(){
    long long int j=0;
    for(register long long int i=2;i<=Len1;++i){
        while(j&&Str2[j+1]!=Str2[i])
            j=Next[j];
        if(Str2[j+1]==Str2[i])
            ++j;
        Next[i]=j;
    }
}
inline void KMP(){
    getNext();
    long long int j=0;
    for(register long long int i=1;i<=Len1;++i){
        while(j&&Str2[j+1]!=Str1[i])
            j=Next[j];
        if(Str2[j+1]==Str1[i])
            ++j;
        if(j==Len2){
            j=Next[j];
            Match[i-Len2+1]=1;
        }
    }
}
int main(){
    scanf("%lld%lld",&Len1,&Len2);
    if(Len1<Len2){
        cout<<"0"<<endl;
        return 0;
    }
    cin>>Str1+1>>Str2+1;
    Str1[0]='~';
    KMP();
    for(register long long int i=1;i<=Len1;++i)Sum[i]=Match[i];
    for(register long long int i=1;i<=Len1;++i)Sum[i]+=Sum[i-1];
    for(register long long int i=1;i<=Len1;++i)Sum[i]+=Sum[i-1];
    Manacher();
    long long int mid=(Len2+1)/2;
    for(register long long int i=mid;i<=Len1;++i){
        if(2*P[i]-1<Len2)continue;
        Ans+=getSum(i-Len2+mid,i-Len2+P[i]);
        Ans-=getSum(i-P[i],i-mid);
    }
    long long int mod=pow(2,32);
    printf("%lld\n",Ans%mod);
    return 0;
}