洛谷P6216 回文匹配题解

题意：对于一对字符串 \((s_1,s_2)\)，若 \(s_1\) 的长度为奇数的子串 \((l,r)\) 满足 \((l,r)\) 是回文的，那么 \(s_1\) 的“分数”会增加 \(s_2\) 在 \((l,r)\) 中出现的次数。

现在给出一对 \((s_1,s_2)\)，请计算出 \(s_1\) 的“分数”。

答案对 \(2 ^ {32}\) 取模。

容易发现这就是个Manacher+KMP

Manacher用于找出奇回文串，KMP用于找出 \(s_2\) 在 \((l,r)\) 中的出现位置

难点在于如何计算这个次数

对于每个极大回文串（长度小于 \(|s_2|\) 的不考虑）

它一定包含了在同一回文中心的更小的回文串

如abbba还包含了bbb,b

如果暴力去求解，时间复杂度为 \(O(n^2)\)

于是想到前缀和来加快运算

我们可以在匹配成功时将 \(s_2\) 左端点位置标记为 \(1\)

考虑一个回文串，x为任意字符

str:xxxxxxx
pos:1234567

它对答案的贡献为sum_6-sum_0+sum_5-sum_1+sum_4-sum_2+sum_3-sum_3

即，sum_6+sum_5+sum4+sum_3-(sum3+sum_2+sum_1+sum_0)

注：要从r-m+1开始，否则会出现右边界超出范围的情况

还是个前缀和！

于是我们可以再做一次前缀和（即二次前缀和）

这样时间复杂度就压到 \(O(n)\) 了

代码如下

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN (int)(3e6+25)
int n,m,r,mid;
int fail[MAXN],sum[MAXN],len,p[MAXN];
char a[MAXN],b[MAXN];
unsigned ans;
signed main()
{
    scanf("%lld%lld",&n,&m);
    scanf("%s %s",a+1,b+1);
    a[n+1]=b[m+1]='~'; // 本题的数据有问题所以要手动加个分隔符 QAQ
    for(int i=2,j=0; i<=m; i++)
    {
        while(j&&b[i]!=b[j+1])j=fail[j];
        if(b[i]==b[j+1])++j;
        fail[i]=j;
    }
    for(int i=1,j=0; i<=n; i++)
    {
        while(j&&a[i]!=b[j+1])j=fail[j];
        if(a[i]==b[j+1])++j;
        if(j==m)++sum[i-m+1];
    }
    for(int i=1; i<=n; i++)
        sum[i]+=sum[i-1];
    for(int i=1; i<=n; i++)
        sum[i]+=sum[i-1];
    for(int i=1; i<=n; i++)
    {
        if(i<=r)p[i]=min(p[(mid<<1)-i],r-i+1);
        while(a[i-p[i]]==a[i+p[i]])++p[i];
        if(i+p[i]-1>=r)r=i+p[i]-1,mid=i;
    }
    // ------------------------------------
    for(int i=1; i<=n; i++)
    {
        if(2*p[i]-1<m)continue;
        int r=i+p[i]-1,l=i-p[i]+1;
        l--;r=r-m+1;
        int mid=(l+r)>>1;
        ans+=sum[r]-sum[mid]-sum[((l+r)&1)?mid:mid-1]+sum[l-1];
    }
    printf("%u\n",ans);
    return 0;
}