$\mathrm{Manacher}$ 算法用于解决求解字符串中的最长回文子串问题，时间复杂度为 $O(n$) 是目前求解该问题效率最高的算法。
求最长回文子串
之前学进制哈希的时候学到了一种名为中心扩展法的求解方法，时间复杂度 $O(n^2)$ ，搭配上 哈希+二分 可以优化到 $O(n\log n)$ 。
分析一下中心扩展法的效率，最好时，即每个字符都只需扩展一次，这样复杂度为 $O(n)$ ，最坏的话每个字符都要扩展 $n$ 次，复杂度 $O(n^2)$ 。究其低效的原因，在于有大量的重复检查。
如果能够改善这种重复，那么便可以设计出一个高效的算法。
$\mathrm{Manacher}$ 算法发巧妙地利用回文串本身的特征实现了极大的改善。
$\mathrm{Manacher}$ 算法
考虑回文串时有两种情况，一种是有一个中心字符的奇数串，另一种是有两个中心字符的偶数串。
那么求 $S$ 的最长回文子串时，两种情况编码较为麻烦。
考虑做一个变换，使这两种情况变为一种情况。
在字符串 $S$ 的每个字符左右插入一个不属于 $S$ 的字符，如 # ，同时为了编程方便，在 $S$ 的首尾再加上两个奇奇怪怪的字符防止越界。
例如字符串 $S$ 为 abba ，经过变换后变为 $#a#b#b#a#& ，经过变换后的字符串，不影响对其中回文串的判定。
定义数组 $P[]$ ，其中 $P[i]$ 表示以字符 $S[i]$ 为中心字符的最长回文串的半径。
如果已经计算出了 $P[]$ ，那么最大的 $P[i]-1$ 就是答案，这个最长回文串在原字符串的开头位置是 $(i-P[i])/2$ 。
那么现在的问题就是如何高效地求出 $P[]$ 。
考虑用动态规划的思路。
假设目前已经求出了 $P[0]\sim P[i-1]$ ，考虑如何求出 $P[i]$ 。
令 $R$ 为 $P[0]\sim P[i-1]$ 这些回文串中最大的右端点，即能覆盖到的最远点。
令 $C$ 为这个 $R$ 对应的回文串的中心点。
也就是说， $P[C]$ 是已经求得的一个回文串，它的右端点是 $R$ ，且 $R$ 是所有已经求得的回文串的右端点的最大值， $R=P[C]+C$ 。
在字符串 $S$ 上， $R$ 左边的字符已经被检查过， $R$ 右边的字符还未被检查。
下面来计算 $P[i]$ 。
设 $j$ 是 $i$ 关于 $C$ 的镜像点，$P[j]$ 已经被计算出来了。
若 $i\ge R$ ，由于 $R$ 右边的字符都没有检查过，所以只能初始化 $P[i]=1$ ，然后用暴力中心扩展法求出 $P[i]$ 。
若 $i<R$ ，细分为两种情况：
$j$ 的回文串被 $C$ 的回文串包含。而 $i$ 为 $j$ 的景象，所以镜像 $i$ 的回文不会越过 $C$ 的右端点 $R$ ，所以 $P[i]$ 有初值 $P[i]=P[j]$ 。
根据 $(i+j)/2=C$ ，所以 $j=2C-i$ ，即 $P[i]$ 有初值 $P[2C-i]$ 。这个初值并非最后的 $P[i]$ 的值，仍需继续用中心扩展法来扩展。
$j$ 的回文串不被 $C$ 的回文串包含，即 $j$ 回文串的左端点比 $C$ 回文串的左端点小。根据镜像原理，所以 $i$ 回文串的右端点比 $R$ 大，但是由于 $R$ 右边的字符还没有被检查过，只能先让 $P[i]$ 被限制在 $R$ 之内，有 $P[i]=R-i$ 。然后继续用中心扩展法完成 $P[i]$ 的计算。
上面的两种情况可以一起处理， $P[i]$ 取两者的较小值，然后用中心扩展法来计算。
例题 洛谷3805 【模板】manacher 算法
给出一个只由小写英文字符 $\texttt a,\texttt b,\texttt c,\ldots\texttt y,\texttt z$ 组成的字符串 $S$ ,求 $S$ 中最长回文串的长度 。
字符串长度为 $n$。
代码
直接贴代码吧
#include<bits/stdc++.h>
#define N 11000010
using namespace std;
inline int read() {
int w=1,x=0;
char ch=0;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return w*x;
}
char a[N],s[N<<1];
int n,P[N<<1],ans=0;
void init() {
n=strlen(a);
int m=0;
s[m++]='$',s[m++]='#';
for(int i=0;i<n;i++) s[m++]=a[i],s[m++]='#';
s[m++]='&';
n=m;
}
void Manacher() {
int R=0,C;
for(int i=1;i<n;i++) {
if(i<R) P[i]=min(P[(C<<1)-i],R-i);
else P[i]=1;
while(s[i+P[i]]==s[i-P[i]]) P[i]++;
if(P[i]+i>R) {
R=P[i]+i;
C=i;
}
ans=max(ans,P[i]-1);
}
}
int main() {
scanf("%s",a);
init();
Manacher();
printf("%d\n",ans);
system("pause");
return 0;
}时间复杂度
最后来分析分析 $\mathrm{Manacher}$ 算法的时间复杂度。
该算法表面上是逐步求解 $P[i]$ ，实际上是在扩展 $R$ 。
$R$ 的扩展是通过 while 循环实现的，算法的计算量取决于 $R$ 的计算。
而从 $S[1]$ 到 $S[n]$ 的整个扩展过程中， $R$ 对每个字符只计算了一次，所以总时间复杂度为 $O(n)$ 。
参考资料
《算法竞赛》罗勇军
