【题解】回文匹配

题目传送门：【洛谷】回文匹配

算法1：

有贡献的子串的左端标记1，每次找最大的回文，在左端能遍历的范围内，计算离两边端哪个最近，其距离即贡献值。
\(\sum \limits_{i=l}^{r}\)\(a_i\times(i-l+1)+\sum \limits_{i=l}^{r}a_i\times(r-i+1)\)

通过观察我们只需要维护\(a_i和a_i\times i\)即可

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int N = 3100010;
int n,m,val[N],p[N],ne[N],sum[N],summ[N];
char s[N],str[N],pp[N];

void init()
{
	for(int i=2,j=0;i<=m;i++)
	{
		while(j&&pp[i]!=pp[j+1]) j=ne[j];
		if(pp[i]==pp[j+1]) j++;	
		ne[i]=j;
	}
}
void kmp()
{
	
	for(int i=1,j=0;i<=n;i++)
	{
		while(j&&s[i]!=pp[j+1]) j=ne[j];
		if(s[i]==pp[j+1]) j++;
		if(j==m)
		{
			j=ne[j];
			val[i-m+1]=1;
		}
	}
}
void manacher()
{
	int mid=0,mr=0;
	for(int i=1;i<=n;i++)
	{
		if(i<mr) p[i]=min(p[mid*2-i],mr-i);
		else p[i]=0;
		while(s[i+p[i]+1]==s[i-p[i]-1]&&i-p[i]-1>=1&&i+p[i]+1<=n)
		{
		    ++p[i];
		} 
		if(i+p[i]>mr)
		{
		    mr=i+p[i];
		    mid=i;
		}
 	}
}
void solve()
{
	long long ans=0;
	for(int i=1;i<=n;i++) 
	{
	    sum[i]=sum[i-1]+val[i];
	    summ[i]=summ[i-1]+val[i]*i;	
	}
	int mid,l,r;
	for(int i=1;i<=n;i++)
	{
		l=i-p[i],r=i+p[i]-m+1;
		if(l>r) continue;
		mid=(l+r)>>1;
		ans+=summ[mid]-summ[l-1]-(sum[mid]-sum[l-1])*(l-1);
	
		if(mid!=r) ans+=(sum[r]-sum[mid])*(r+1)- (summ[r]-summ[mid]);//如果在后半段
		
	}
	long long  mod=pow(2,32);
        printf("%lld\n",ans%mod);	
}

int main()
{
	cin>>n>>m;
	cin>>s+1>>pp+1;
	init();
	manacher();

	kmp();
	solve();
	
	
	return 0;
}