题解：P3805 【模板】manacher

__O_v_O__ · 2025-05-17 08:41:40 · 题解

简介

Manacher 可以做到时间复杂度 O(n) 求最长回文子串及相关问题。

Manacher 的思想是利用前面求出的东西加速后面的计算。它产生的原因主要是因为回文串的特殊性：如果求出了 i-1 处的最长回文半径，那么这个回文串有可能延伸到 i 后面，可以帮助 i 的计算。

算法流程

首先，奇回文和偶回文不好处理，我们在每两个字符间加上 #，这样所有回文串都是奇回文了。

我们记录现在已知回文子串的最大右端点 R，和它对应的回文中心 C（为了最大限度利用已知条件）。假设第 x 位的最长回文半径为 p_x。

假设现在处理到第 i 位。我们有两种情况：

• 若 i>R，这时已有的条件无法帮助处理，暴力扩展即可。

• 若 i\le R，我们发现，i' 的回文区域是我们已经求过的，于是我们就可以加速处理，放一张图：\ \ 我们需要分三种情况考虑：

  • 若 i' 的回文区域在 [L,R] 内：\ \ 这时因为回文串翻转后还是回文串，而 i' 已经无法扩展了，于是 p_i=p_{i'}。

  • 若 i' 的回文区域超过了 L：\ \ 这时，显然 3 为 1 的反转，而 4 又为 3 的反转，所以 4 和 1 相同。\ 但是 2 一定不与 1 的反转相同（否则 [L,R] 可以扩展），也就是说 2 一定不与 4 的反转相同，那么 i 只能扩展到 R，即 p_i=R-i+1。

  • 若 i' 的回文区域左端点刚好为 L：\ \ 此时 2 是否等于 4 的反转未知，于是还是需要暴力扩展。

至此，Manacher 的流程已讲解完毕。但我们一定有一个疑问：算法中有这么多暴力扩展，为什么复杂度还是 O(n) 呢？

时间复杂度

使 Manacher 复杂度正确的东西主要是这个 R：显然，它只增不减。但只有这一点还不够，我们需要说明每次操作要么是 R 加一，要么复杂度为 O(1)。我们对于每种情况考虑：

• 若 i>R，显然扩展会使 R 增加。

• 若 i\le R：前两种情况显然复杂度为 O(1)。对于第三种情况：若无法扩展，则复杂度为 O(1)；若可以扩展，则会使 R 增加。

于是总复杂度为 O(n)。

AC code:

#include<bits/stdc++.h>
using namespace std;
int n,p[22000002],mi,r,an,le;
char s[11000002],t[22000002];
signed main(){
    ios::sync_with_stdio(0);
    scanf("%s",s+1),le=strlen(s+1);
    t[++n]='$',t[++n]='#';
    for(int i=1;i<=le;i++)
        t[++n]=s[i],t[++n]='#';
    t[++n]='!';
    for(int i=2;i<n;i++){
        if(i<=r)p[i]=min(p[2*mi-i],r-i+1);
        else p[i]=1;
        while(t[i-p[i]]==t[i+p[i]])p[i]++;
        if(i+p[i]>r)mi=i,r=i+p[i]-1;
        an=max(an,p[i]);
    }
    printf("%d",an-1);
    return 0;
}