题解：P3805 【模板】manacher
Astraios
·
·
题解
题解
【模板】manacher 算法
算法简介
Manacher 算法，又称为马拉车算法，是一种用于查找字符串中最长回文子串的高效算法。它由 Manacher 在 1975 年提出，能够在 O(N) 的时间复杂度和空间复杂度内解决问题。
算法思想
算法的核心在于通过特殊字符的插入，将偶数长度和奇数长度的回文子串统一处理。
那么，推导与实现过程如下：
首先，有一个小技巧：
对于字符串 s，用一个 s 中不存在的字符把 s 中的字符隔开：
例如 \texttt {aba} \rightarrow \texttt {￥a￥b￥a￥}。
原串最长回文子串长度等于新串最长回文子串长度的一半。
PS：接下来出现的 s 若无特殊说明均为插入字符后得到的新串。
算法详解：
manacher 算法需要维护最大回文半径。
最大回文半径：从 s_i 出发能拓展的字符数，记作：p_i。
我们从左向右依次计算 p_i。\
假设要计算 p_i，则此时应已经计算了 p_1,p_2,p_3,\dots,p_{i-1}。\
为了计算 p_i，在枚举 i 的过程中，我们要维护使得 R 最大的区间 [L,R]。
其中 \begin{cases}
L=M-p_M+1 & (M<i) \\
R=M+p_M-1 & (M<i)
\end{cases}
接下来开始分类讨论：
$i \le R$ 时，找到 $i$ 关于 $M$ 的对称点 $k$：
若 $p_k$ 对应的回文区间不包含 $L$，令 $p_i=p_{2M-i}$。
若 $p_k$ 对应的回文区间包含 $L$，令 $p_i=p_{R-i+1}$ 并继续暴力扩展。
再看回 $p_k$ 对应的回文区间不包含 $L$ 的情况：
若 $p_k$ 对应的回文区间不包含 $L$，则 $L<k-p_k+1$，又 $L=2M-R$ 且 $k=2M-i$，则 $(2M-R)<(2M-i)-p_{2M-i}+1$，化简得 $p_{2M-i}<R-i+1$。
然后是 $p_k$ 对应的回文区间包含 $L$ 的情况：
若 $p_k$ 对应的回文区间包含 $L$，则 $L \ge k-p_k+1$，又 $L=2M-R$ 且 $k=2M-i$，则 $(2M-R) \ge (2M-i)-p_{2M-i}+1$，化简得 $p_{2M-i} \ge R-i+1$。
所以经过观察总结可得
$i>R$ 时，令 $p_i=1$，并暴力向两边扩展。
$i \le R$ 时，令 $p_i = \min (p_{2M-i},R-i+1)$，并暴力向两边扩展。
## 正确性证明
时间复杂度为何是 $O(N)$ 呢？
因为每次在更新右端点时，$i+p_i$ 必然会超过原来的且小于 $n$，即呈递增趋势，不会重复更新。所以最多只会更新 $O(N)$ 次，那么总的时间复杂度就是 $O(N)$ 了。
## Code
接下来就是最美的代码实现了！！！
算法部分：
```cpp
int manacher(string s)
{
int M=0,R=0;
for(int i=1;i<=n;i++)
{
if(i>R) p[i]=1;
else p[i]=min(p[2*M-i],R-i+1);//分类讨论
while(i-p[i]>=1&&i+p[i]<=n&&s[i-p[i]]==s[i+p[i]]) p[i]++;//暴力拓展
if(i+p[i]-1>R) M=i,R=i+p[i]-1;//更新
}
int ans=0;
for(int i=1;i<=n;i++) ans=max(ans,p[i]);
return ans-1;
}
```
本题代码
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
string s,S;
int p[30000005],n;
int manacher(string s)
{
int M=0,R=0;
for(int i=1;i<=n;i++)
{
if(i>R) p[i]=1;
else p[i]=min(p[2*M-i],R-i+1);
while(i-p[i]>=1&&i+p[i]<=n&&s[i-p[i]]==s[i+p[i]]) p[i]++;
if(i+p[i]-1>R) M=i,R=i+p[i]-1;
}
int ans=0;
for(int i=1;i<=n;i++) ans=max(ans,p[i]);
return ans-1;
}
signed main()
{
cin>>S;
s+=' ';
for(int i=0;i<S.size();i++) s+='$',s+=S[i];
s+='$';
n=s.size()-1;
cout<<manacher(s);
return 0;
}
```