题解：P3805 【模板】manacher

Motonic_queues · 2025-05-04 19:07:26 · 题解

算法简介

Manacher 在 1975 年发明了一个算法，可以在 O(n) 的时间复杂度内寻找一个字符串的所有回文串，因此这种算法以他的名字冠名（中文谐音马拉车）。

算法思想

主要是靠回文串的“对称”性质，优化大量不必要的计算，先来看个例子：

对于一个字符串，如果我们要找到它的全部长度为奇数的回文字串，可能会用这样的朴素算法：

遍历字符串
对于当前位置 i，以其为对称轴向两侧“扩展”，像这样：
```
int cnt=1;
while(i-cnt&&s[i+cnt]==s[i-cnt])++cnt;
```
这样可以确定：以 i 为中心的最长的回文字串的“半径”为 cnt。我们称这个值为 回文半径，用一个 p 数组存下来。
但不难看出来，面对极端情况（字符串只含一种字符），复杂度为 O(n^2)。

怎么优化呢？
首先我们可以注意到：因为我们是按顺序遍历的，也就是说，一个位置的答案确定好之后就不会发生改变了。
考虑到这点，可能我们在优化时要尽可能利用过去得到的答案。

那么如果我们正在考虑 i，在什么情况下，计算 p_i 要用到 p_j 的值呢？
这时我们就能注意到了：如果 i 和 j 是一个回文串 s^* 中对称的位置，那么，以 j 为中心的最长回文字串中*属于 $s^ 的部分**一定也属于以 i$ 为中心的最长回文字串中，事实上，这正是 Manacher 的核心思路。

关于实现方式，有一个巧妙的方法：因为这个优化只有在 i 被一个回文字串包括时才有意义，所以我们只有维护“右端点最靠右的回文串”的必要，如此一来，我们就可以设计出下面的算法流程：

设 C 为 s^* 的中心位置，R 为 s^* 的回文半径。初始化两个为 0。
遍历字符串
找到 i 在 s^* 中的对称位置 2\times C-i，我们称之为 i_m。
倘若 i_m 有意义（即大于 0 ），将 p_i 赋成 \min\{p_{i_m},R-i\}。
直接从 p_i 开始扩展。
如果扩展完得到的 i+p_i 大于 R，用 i 和 p_i 替换 C 和 R。

这个时候可能会有点怪，因为还是扩展了，但让我们仔细思考一下什么时候才会扩展。
很显然，如果扩展完没有更新 C+R，事实上，根本就不会发生扩展。
反证法：
如果能扩展，且最终没有更新 R，则至少以 i 为中心的最长回文字串会包含 i-p_{i_m}-1 和 i+p_{i_m}+1。
而这两个字符分别与 i_m+1 和 i_m-1 相等，如果前二者是相等的，则后二者也相等，但以 i_m 为中心的最长回文字串没有包含后二者，出现矛盾，假设不成立。

这样一来，每次扩展一定会把 C+R 往前推，但这个值很显然不会超过 n，所以扩展的次数也不会超过 n 次，再算上遍历，总的复杂度还是 O(n)。

如果你按照这个思路去写代码并提交，肯定无法 AC，因为我最开始的例子就只考虑的长度为奇数的回文子串，不过，要考虑长度为偶数的情况，有一个巧妙的方式：
在每个字符之间插入一个 罕见的 字符，比如 “#”，也就是代表两两字符之间的空位，再加入一头一尾两个不同的哨兵字符，就能处理全部的情况了（而且这样得到的最大回文半径直接就是真实的回文长度）。

Talk is cheap,show me the code

#include<bits/stdc++.h>
using namespace std;

const int N=3e7+5;
string s,t;
int l;
int p[N],C,R,ans;

void dl(){    //调整字符串
    t="^#";
    for(int i=0;i<l;i++)t+=s[i],t+='#';
    t+='$';
    l=t.size();
}

void solve(){  //获得 p 数组
    for(int i=1;i<l-1;i++){
        int mirri=2*C-i;
        if(i<R)p[i]=max(0,min(R-i,p[mirri]));
        int cnt=0;
        while(t[i+p[i]+1]==t[i-p[i]-1])p[i]++,cnt++;
        if(i+p[i]>R)C=i,R=p[i]+i;
        ans=max(ans,p[i]);
    }
}

int main(){
    cin>>s;
    l=s.size();
    dl();
    solve();
    cout<<ans;
    return 0;
}