P6216 回文匹配

· · 题解

传送门

题目大意

给两个字符串 s 和 t，求对于 s 的 每个 回文串，t 出现的次数之和。

Solution

这题有点坑，n,m 输入与 s,t 的长度并不符合……

所以需要在字符串最后手动加一个终止符，比如 美元符号什么的。

但是这题的做法非常简单，大概只要会马拉车和 KMP 就可以了。

首先先找出 t 在 s 中出现的位置，然后一个自然的想法就是对于每个位置求出 t 的起点在这个位置之前的匹配数，也就是匹配的前缀和，这很容易想到。

然后写写写，写完一个马拉车，然后非常 naive 地在马拉车每次扩展的时候加上答案。但这是会 GG 的，因为我试过这样会把马拉车优化的部分对答案的贡献丢掉。

所以正确的做法是对于每个回文串都算一下答案，注意到回文串的个数是 n^2 级别的，于是得到了 O(n^2) 的优秀复杂度。

那我们怎么优化这个东西呢？考虑求这个东西的式子。假设 x 是任意字符：

对于这样一个回文串：

str: xxxxxxx
pos: 1234567

如果前面的前缀和数组是 pre，t 的长度是 2，那么这个回文串的贡献应该是：pre_6-pre_0+pre_5-pre_1+\dots+pre_3-pre_3。我们对它进行一个重新的排列：pre_6+pre_5+pre_4-(pre_2+pre_1+pre_0)。不难发现，在原来的基础上再做一次前缀和，就可以快速得到这个东西了。

所以我们做 二次前缀和 就可以了。

然后对于每个 极大 回文串就可以 O(1)，总体复杂度就是 O(n) 了。

Code

// Problem: P6216 回文匹配
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P6216
// Memory Limit: 500 MB
// Time Limit: 1000 ms
// Author: ZCETHAN
// Time: 2021-11-02 17:58:03

#include<bits/stdc++.h>
#define ll long long
#define inf (1<<30)
#define INF (1ll<<60)
using namespace std;
const int MAXN=3e6+10;
char s[MAXN],t[MAXN];
int nxt[MAXN],pre[MAXN];
int rd[MAXN];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    scanf("%s%s",s+1,t+1);
    nxt[1]=0;int k=0;s[n+1]=t[m+1]='$';
    for(int i=2;i<=m;i++){
        while(k&&t[k+1]!=t[i]) k=nxt[k];
        if(t[k+1]==t[i]) k++;nxt[i]=k;
    }k=0;
    for(int i=1;i<=n;i++){
        while(k&&t[k+1]!=s[i]) k=nxt[k];
        if(t[k+1]==s[i]) k++;
        if(k==m){pre[i-m+1]++;k=nxt[k];}
    }
    for(int i=1;i<=n;i++) pre[i]+=pre[i-1];
    for(int i=1;i<=n;i++) pre[i]+=pre[i-1];
    int mx=0,R=0;unsigned int ans=0;
    for(int i=1;i<=n;i++){
        rd[i]=(i<R?min(R-i,rd[mx*2-i]):1);
        while(s[i+rd[i]]==s[i-rd[i]])
            rd[i]++;
        if(R<i+rd[i]) mx=i,R=i+rd[i];
    }//这上面都是板子，KMP+Manacher
    for(int i=1;i<=n;i++){
        if(2*rd[i]-1<m) continue;
        int r=i+rd[i]-1,l=i-rd[i]+1;
        l--;r=r-m+1;
        int mid=(l+r)>>1;//注意一下奇偶，特判一下就可以了
        ans+=(pre[r]-pre[mid]-pre[((l+r)&1)?mid:mid-1]+pre[l-1]);
    }
    printf("%u\n",ans);
    return 0;
}