P6216 回文匹配

芝士一道结合了 Manacher 和 KMP 的好题。

题面

见P6216

思路

由于题目要求只考虑奇回文串，所以我们不需要加入奇奇怪怪的字符来处理偶回文串，先做一遍 KMP，做的时候记录一下每一次成功匹配的左端点，然后再做一遍 Manacher，这样就得到了以每个点为中心的最大奇回文串的长度，但是以这个点为中心的奇回文串不止有最长的那个，还有比它小一点的，可以发现这是两段等差数列，如图：

这些回文串中所有的标记我们都要统计吗？不一定，因为有些标记虽然在回文串内，但是匹配成功的右端点可能就不在标记里了，所以要将这些回文串的右端点同时减去匹配串的长度，如图：

我们只需要统计红线左边的所有点权和。

由于是等差数列，所以可以用前缀和处理。

对于左半部分，答案为 $\sum_{i=l}^{mid}lop_i\times{i-(l-1)}$

对于右半部分，答案为 $\sum_{i=mid+1}^{r}lop_i\times{(r+1-i)}$

显然，我们只需要维护 $\sum_{i=l}^{r}lop_i$ 和 $\sum_{i=l}^{r}lop_i\times{i}$ 即可，

而取模呢？直接用 unsigned int 自然溢出。

代码

#include<bits/stdc++.h>
using namespace std;
typedef unsigned int uint;
const uint N=3e6+10;
uint ans;
char a[N],b[N];
int n,m;
uint pre[N],sum[N];
int nxt[N],d[N];
uint lop[N];
void calc(uint x)
{
    for(uint i=1,j=0;i<x;i++)
    {
        while(j&&b[i]!=b[j]) j=nxt[j-1];
        if(b[i]==b[j]) j++;
        nxt[i]=j;
    }
}
void kmp(uint x,uint y)
{
    for(uint i=0,j=0;i<x;i++)
    {
        while(j&&a[i]!=b[j]) j=nxt[j-1];
        if(a[i]==b[j]) j++;
        if(j==y)
        {
            lop[i-y+1]++;
            j=nxt[j-1];
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    scanf("%s\n%s",a,b);
    calc(m);
    kmp(n,m);
    for(int i=0,l=0,r=-1;(int)i<n;i++)
    {
        int j=l+r-i;
        int dj=j>=0?d[j]:0;
        d[i]=max(min(r-i+1,dj),0);
        if(j-dj+1<=l)
        {
            while(i+d[i]<n&&i-d[i]>=0&&a[i+d[i]]==a[i-d[i]]) d[i]++;
            l=i-d[i]+1,r=i+d[i]-1;
        }
    }
    sum[0]=0;// lop*i前缀和
    pre[0]=lop[0];// lop前缀和
    for(int i=1;(int)i<n;i++)
    {
        sum[i]=sum[i-1]+lop[i]*i;
        pre[i]=pre[i-1]+lop[i];
    }
    for(int i=0;(int)i<n;i++)
    {
        int l=i-d[i]+1,r=i+d[i]-m;
        if(l>r) continue;//被切掉了
        int mid=(l+r)>>1;
        ans+=(sum[mid]-sum[l-1])-(pre[mid]-pre[l-1])*(l-1);
        ans+=(pre[r]-pre[mid])*(r+1)-(sum[r]-sum[mid]);
    }
    printf("%u",ans);
    return 0;
}