Manacher 算法应用于一个特定场景：查找一个长度为 $n$ 的字符串 $S$ 中的最长回文子串（Longest Palinadromic Substring），其时间复杂度为 $O(n)$，是这种场景中效率最高的做法。
回文串是从头到尾读和从尾到头读都相同的字符序列，也就是反转之后与原串相同。回文串有两种，一种长度为奇数，有一个中心字符；一种长度为偶数，有两个相同的中心字符（或者说没有中心字符）。
Manacher 算法实际上是对中心扩展暴力法求解的一次改进，利用了动态规划的思想。
暴力法：中心扩展
在【令人心动的算法】进制哈希中我们提到过，利用中心扩展法可以把原本 $O(n^2)$ 的遍历过程优化到 $O(n)$。然而，如果这个串中有大量的回文串，而且长度较长，这个过程也将变得效率很低。这是因为我们选择某一个中心点进行扩展的时候，会重复扩展一些部分，这些重复的检查是可以被改善的。
用 Manacher 算法优化
处理奇偶串
首先，让我们做一个简单但有效的优化：由于回文串存在奇数和偶数的差别，编码起来比较麻烦，我们可以在 $S$ 的字符左右插入一个不属于 $S$ 的字符，如 '#'。于是 "abcde" 就变成了 "# a # b # c # d # e #"，中心字符就是 'c'；对于偶数串也是同理， abccba 变成 # a # b # c # c # b # a，中心字符是 '#'。
这样，新字符串的长度都是奇数，中心字符都只有一个。同时，为了编程方便，在 $S$ 的首尾分别加上 '$' 和 '&' 这两个奇怪字符防止越界。
动态规划维护答案
在9.1 进制哈希中，我们利用哈希函数求解问题的时候提到过，判断的根本方法是选择一个数作为 半径，然后从某一个中心字符向外扩展，判断是不是回文串。当时我们观察到其具有单调性，可以用二分加速。时间复杂度为 $O(n \log_2 n)$。
让我们利用动态规划的思想更进一步。
定义 dp[i] 是以字符 s[i] 为中心字符的最长回文串的半径，那么答案就是最大的 dp[i] - 1，并且这个回文串的开头位置是 (i - dp[i]) / 2。这里除以 $2$ 是因为对应的是 原串 而不是 改串。
用回文串特征减少检查
我们前面提到过，Manacher 算法优化的正是暴力法中重复的检查部分，它利用了 回文的镜像也是回文 的特征。
具象来说，假设我们已经找到了一个回文串 $S$，那么这个回文串的中心字符两边对称的位置上，如果左边有一个回文串，那么右边自然也存在一个，不用重复检查。
不过，如果仅仅只是这样设计，仍然有很多问题，不能保证左边的回文串一定短于 $S$；而且由于我们是从左到右检查的，如果右边存在一个很大的回文串，但是它超出了 $S$ 的范围，而右侧的部分我们还没有检查到，不能直接跳过检查。
Manacher 算法的巧妙之处，正是处理了这个问题。
假设已经计算出了 dp[0] 到 dp[i-1]，下一步就是计算 dp[i]。令 $R$ 为 dp[0] 到 dp[i-1] 这些回文串中 最大的右端点， $C$ 是这个 $R$ 对应的回文串 的中心点。也就是说， dp[C] 是已经求得的一个回文串的半径，它的右端点是 $R$，并且 $R$ 是所有已经求得的回文串的右端点最大值。显然有 R = C + dp[C]。在字符串中， $R$ 左边的都已经检查过了，右边的还没有检查。
下面计算 dp[i]，并且假设 j 是 i 关于 $C$ 的镜像点。显然，dp[j] 已经被计算出来了。
- 若 $i >= R$，那么它右边的字符还没有被检查到。按正常的暴力法，先令
dp[i] = 1，再左右扩展即可。 - 若 $i < R$，那么可以再细分成两种情况。
- 如果
j的回文串被 $C$ 包含，即j回文串的左端点比 $C$ 回文串的左端点大（右侧），那么根据我们之前的镜像原理，至少有dp[i] = dp[j]，然后继续左右扩展。其中，我们利用(i + j) / 2 == C，可以得到j == 2*C - i，也就是dp[i] = dp[2*C-i]。 - 否则，我们就先让
dp[i] = R - i = C + dp[C] - i，也就是把dp[i]限制在 $R$ 之内，然后再左右扩展。也就是“至少有dp[i] = dp[j]”再向外拓展，区别只是给了一个限制。也就是说，这两种情否则，我们就先让dp[i] = R - i = C + dp[C] - i，也就是把dp[i]限制在 $R$ 之内，然后再左右扩展。也就是“至少有dp[i] = dp[j]”再向外拓展，区别只是给了一个限制。也就是说，这两种情况可以 合并处理 ，取两者最小值即可。 - 况可以 合并处理 ，取两者最小值即可。
- 如果
模板代码
#include <iostream>
#include <cstring>
using namespace std;
const int maxN = 1.1e7 + 5;
int n;
int dp[maxN << 1]; // 两倍空间，因为要加上 '#' 字符
char a[maxN];
char S[maxN << 1]; // 改串
void change()
{
n = strlen(a);
int k = 0;
S[k++] = '$';
S[k++] = '#';
for (int i = 0; i < n; i++)
{
S[k++] = a[i];
S[k++] = '#';
}
S[k++] = '&';
n = k;
}
void manacher()
{
int R = 0, C;
for (int i = 1; i < n; i++)
{
if (i < R)
dp[i] = min(dp[(C << 1) - i], dp[C] + C - i);
else
dp[i] = 1;
while (S[i + dp[i]] == S[i - dp[i]])
dp[i]++;
if (dp[i] + i > R)
{
R = dp[i] + i;
C = i;
}
}
}
int main()
{
scanf("%s", a);
change();
manacher();
int ans = 1;
for (int i = 0; i < n; i++)
ans = max(ans, dp[i]);
printf("%d\n", ans - 1);
return 0;
}
