测试点情况 代码：

#include <bits/stdc++.h>
using namespace std;
const int N=3e6+5;
int n,m,nxt[N],book[N],d[N],c[N],sum[N],ans;
char s1[N],s2[N];
void kmp()
{
	for(int i=2,j=0;i<=m;i++)
	{
		while(j && s2[i]!=s2[j+1])
			j=nxt[j];
		if(s2[i]==s2[j+1])
			j++;
		nxt[i]=j;
	}
	for(int i=1,j=0;i<=n;i++)
	{
		while(j && s1[i]!=s2[j+1])
			j=nxt[j];
		if(s1[i]==s2[j+1])
			j++;
		if(j==m)
		{
			book[i-m+1]=1; 
			j=nxt[j];
		}
	}
}
void manacher()
{
	for(int i=1,l,r=1;i<=n;i++)
	{
		if(i<=r)
			d[i]=min(d[r-i+l],r-i+1);
		while(s1[i-d[i]]==s1[i+d[i]])
			d[i]++;
		if(2*d[i]-1>=m)
		{
			c[i-d[i]+1]++;
			if(m&1)
				c[(2*d[i]-1-m)/2+i-d[i]+2]-=2;
			else
			{
				c[(2*d[i]-1-m)/2+i-d[i]+2]--;
				c[(2*d[i]-1-m)/2+i-d[i]+3]--;
			}
			c[i+d[i]-m+2]++;
		}
		if(i+d[i]-1>r)
			l=i-d[i]+1,r=i+d[i]-1;
	}
}
int main()
{
	scanf("%d%d%s%s",&n,&m,s1+1,s2+1);
	kmp();
	manacher();
	for(int i=1;i<=n;i++)
	{
		c[i]+=c[i-1];
		sum[i]=sum[i-1]+c[i];
		ans+=sum[i]*book[i];
	}
	printf("%d",ans);
	return 0;
}