以下图片为 png 格式，点击放大后为 svg 格式。但 svg 显示需要 Source Code Pro 字体。
介绍
最长回文子串问题
最长回文子串问题就是：给定一个字符串，求最长的回文子串的长度。
如果一个字符串正着读和反着读是一样的，那么它就是回文字符串
例如，abacacbaaaabaab的最长的回文子串是baaaab其长度是 6。
模板题地址：洛谷：【模板】manacher算法
POJ：Palindrome
Manacher
Manacher 算法就是用来解决最长回文子串问题的。
他可以在$O(N)$的时间复杂度下求出最长的回文子串的长度。
原理
暴力查找
如果是刚刚学信息学的小朋友们，一定会想出一个粗暴的方法：枚举每一个子串，并验证它是否为回文串。不过这样做的时间复杂度是$O(N^3)$。
当然这个暴力还可以优化一下，因为所有的回文串都是对称的，所以我们可以枚举回文串的对称轴，然后往左右两边扩展，这样做的时间复杂度是$O(N^2)$。
虽然已经减小了一个”$N$”，但是还是不够快。
统一奇偶性
如果你真的编写了上面$O(N^2)$的方法的话，那么你应该体验到了奇偶性不统一的烦恼吧。
在 Manacher 中，我们首先要做一个预处理，在每一对相邻的字符之间插入一个相同的字符（例如#），但是不能在原串出现过。举个栗子：
lgj → l#g#j
abba → a#b#b#a
加了#字符后，原子串的回文性并不会变，原来不是回文的子串不会变成回文串，原来的回文串也不会变成非回文串（这个还可以理解吧）。
而且加了#字符后，对称轴只会出现在整除位置，不会在两个字符的中间，方便了我们下面的运算。
代码也很简短：（tmp为原字符串，str为扩展后的字符串）
for (int i=0; i<len; i++)
str[i] = (i%2)? tmp[i/2] : '#';
高效求解
在暴力的做法中，我们做了大量的无用功。
例如在暴力的
ababaeaba中，aba（2~4）被访问了 2 次。
我们定义一个回文串的回文半径为：该回文串的对称轴到最远端的距离，例如abcba的回文半径是 3。我们定义一个match[]数组，用match[i]表示以i为对称轴的回文串的回文半径。
然后我们发现，match[i]*2-1就是扩展后的回文串的长度，match[i]-1就是原回文串的长度。所以只要我们求出来match[]，我们就能求出答案。
于是我们的问题就变成了如何快速求出match数组。
我们在定义两个辅助变量：right表示在当前访问过的所有的回文子串中，最右端最长能到达right这个位置。pos表示这个回文子串的对称轴的位置。用一个图表示这个关系：
然后我们访问到第i个字符，要求match[i]。我们可以知道，i一定在pos的右端。不过它有可能在right的左端，也可能在right的右端（或重合）。所以我们要分类讨论。
i ≤ right
如图所示，因为位置3~11是回文串，并关于pos对称，即以i为中心的回文串的一部分也会关于pos对称，另一部分的中心在2*pos-i处。
所以要求match[i]，也就是求match[2*pos-i]。不过当前子串可能更长，还要在原来的基础上继续扩展。
当然，match[i]的初始值也不能超出right的范围。
所以最后的结论是，先把match[i]赋值为min(match[2*pos-i], right-i+1)。
i > right
这个情况就好办了。i在“最右回文串”的外面，所以i没有“先例”，只能从match[i]=1开始扩展。
综上所述，当求match[i]时，如果i <= right，则match[i] = min(match[2*pos-i], right-i+1)，否则match[i] = 1，然后再继续扩展。
完成扩展之后，还要检查一下match[i]+i-1是否超过right，如果是，则更新right。
代码
void manacher() {
int len = 2 * n + 1;
for (int i=0; i<len; i++)
str[i] = (i&1)? tmp[i>>1] : '#';
int pos=0, right=0;
for (int i=0; i<len; i++) {
match[i] = (i>right)? 1 : min(right-i+1, match[pos*2-i]);
while (i-match[i] >= 0 && i+match[i] < len && str[i-match[i]] == str[i+match[i]])
match[i] ++;
if (match[i]+i-1 > right) {
right = i + match[i] - 1;
pos = i;
}
}
}
时间复杂度
先说结论：Manacher 的时间复杂度是$O(N)$。
关于时间复杂度，大家看到代码可能会有一个错觉，就是双重循环的时间复杂度是$O(N^2)$的。是的，while循环在没有限制的时候的确是$O(N)$的，但是这里不一样。我们要明确一个地方，就是while循环会在什么时候进入。
答案就是，仅当match[i]+i-1 >= right时，才可能进入while循环。为什么？因为right是我们目前能访问到的最远的字符，如果match[i]+i-1，我们就到达了未知区域，无法利用已有信息，所以需要进入while循环进行扩展。
重点在于，while循环每执行一次，match[i]都会+1，又因为match[i]+i-1 >= right，所以每一次循环都会更新right。right最远只会到达n，所以while循环总共只会执行n次，不存在与for循环的乘法关系。
那大家可能又有问题了：为什么当match[i]+i-1 < right时，就不会进入while循环呢？
当match[i]+i-1 < right时，可以推断i < right（因为match[i] >= 1），那么match[i]基于match[pos*2-i]，点match[i]+i-1关于pos对称的点pos*2-(match[i]+i-1)（以下简称B）也一定在这个“最右回文串”之内。
此时如果match[i]继续可以扩展，那么match[B]也可以继续扩展，与match[]的定义矛盾了。如果不能继续扩展，自然也不会进入while循环了。
所以 Manacher 的时间复杂度是$O(N)$。
CC 原创文章采用CC BY-NC-SA 4.0协议进行许可，转载请注明：“转载自：Manacher”