\(\operatorname{Manacher}\) 算法大体来讲并不难，使用它可以在线性时间内求出某字符串中最大回文子串的长度。
基础
首先我们知道一个回文串的长度可以是奇数（存在回文中心），也可以是偶数。为了方便我们可以在每两个字符之间都插入一种相同且没有在原字符串出现过的字符，例如 #@~$之类的。同时为了保证过程中不能跑出边界，可以在两边或者一边加上一个其他字符，大概也就是#@~$这些。
设 \(p_i\) 为以 \(i\) 为回文中心的最大回文子串的回文半径（即 \([i-p_i+1,i+p_i-1]\) 这一段为以 \(i\) 为中心的最大回文子串 ），初始时 \(p_i=1\) 。通过定义显然有这样的求法：
while(K[i-P[i]]==K[i+P[i]]) ++P[i];
但对每一个都这样求，会炸掉。
能不能再给力一点儿？
假设我们已经求出来 $1 \sim i-1 $ 的所有回文半径，并且知道了此前回文半径能到达的右边界为 \(R\) ，控制着右边界的回文中心为 \(mid\) ，且 \(R>i\) 。
此时我们再找到 \(i\) 关于 \(mid\) 的对称位置 \(2\times mid-i\)，容易发现 \(i\) 的回文半径一定跟 \(2\times mid-i\) 有、关系，具体是什么关系：
-
当 \(p_{2\times mid-i}\le R-i+1\) 时，由于我们知道此时 \(mid \sim i\) 已经与 \(2 \times mid -i \sim i\) 已经是对称的关系，所以此时 \(i\) 的回文半径完全可以初始化成关于 $2 \times mid -i $ 的回文半径，即 \(p_i=p_{2\times mid-i}\) 。
-
否则，由于 \(R\) 之后的字符能与前面构成回文的情况未知，我们最多只能取到 \(R\) ，因此 \(p_i=R-i+1\) 。
在此基础上拓展即可，复杂度为 \(O(n)\) 。
注意答案为是 \(\max{p_i}-1\) 。
代码：
int R=0,mid=0;
for(Reg int i=1;i<=tot;++i){
P[i]=(R>i)?min(R-i+1,P[2*mid-i]):1;
while(K[i-P[i]]==K[i+P[i]]) ++P[i];
if(i+P[i]-1>R){
R=i+P[i]-1;
mid=i;
}
}
例题
（是骡子是马拉出来溜溜）
【模板】Manacher算法
板子题。
\
[POI2010]ANT-Antisymmetry
题意：
对于一个01字符串，如果将这个字符串0和1取反后，再将整个串反过来和原串一样，就称作“反对称”字符串。比如00001111 和 010101就是反对称的，1001就不是。 现在给出一个长度为 \(N\) 的01字符串，求它有多少个子串是反对称的。
\(N\le 5e5\)
解题思路：
假如说我们在所有字符的后面都加上一个取反过后的字符，例如10操作过后会变成1001，容易发现的是这样操作过后一个反对称的串会变成回文串。有多少子串是反对称的，就是要求有多少子串是回文的（而且长度为偶数，所以中心应该为特殊字符），答案是 $\sum (p_k-1)/2 $ ，\(k\) 为添加字符的位置，除以 \(2\) 是因为求的是数量而非长度。
\
[国家集训队]最长双回文串
题意：
输入长度为 \(n\) 的串 \(S\) ，求 \(S\) 的最长双回文子串 \(T\) ,即可将 \(T\) 分为两部分 \(X\) ，\(Y\) ，（ \(|X|,|Y|≥1\) ）且 \(X\) 和 \(Y\) 都是回文串。
\(|S|\le 1e5\)
解题思路：
考虑用两个数组在所有回文串的左边界 \(lmax\) 和右边界 \(rmax\) 位置保存最大回文半径，答案就是两个边界保存的半径拼接起来。但发现过程中不可能将所有的回文半径长度都更新下来（时间复杂度感人）。所以再考虑每次只在拓展完毕之后更新 \(lmax\) 和 \(rmax\) 。其余的情况主要通过递推来解决，因此有：
\[lmax_i=\max(lmax_i,lmax_{i-2}-2) \\ rmax_i=\max(rmax_i,rmax_{i+2}-2) \]注意 \(lmax\) 与 \(rmax\) 循环的顺序不同。
\
[国家集训队]拉拉队排练
题意：
见洛谷P1659。
解题思路：
发现是要从所有长度为奇数的回文串中选出最大的 \(K\) 个并求所有长度的乘积。显然以原字符为中心的最大回文半径 \(p_i\) 是好求的，数量为 \((p_i-1)/2\) ，而且我们可以通过数量去间接地知道它的长度。
可以考虑开个桶维护该数量的字符串有多少个，最后求出其前缀和即可知道每个长度的回文字符串数，接下来就很好做了。
说实话也比较裸
\
[SHOI2011]双倍回文
题意：
见洛谷P4287。
解题思路：
好吧这题是刚做的，我暴力草过去了。
因为要求双倍回文的长度必须为 \(4\) 的倍数，我们可以跑完 \(\operatorname{Manacher}\) 之后枚举所有以特殊字符为中心的回文半径。
显然，双倍回文要求该子串中心的两侧还必须分别有两个回文半径至少为原半径一半的次中心。我们可以从大往小再枚举回文半径以内的 \(4\) 的倍数并根据性质判断，当前半径小于答案时终止枚举（否则大概会炸得很惨，某种意义上是时间的保证）。但复杂度是假的，能过就离谱。
有一种 \(\operatorname{Manacher}\) 的正解做法是，在算法过程中找以该位置为右侧次中心时最靠左的子串中心。首先当 \(mid+(p_{mid}-1)/2 \le i\) 时可以将 \(mid\) 作为一个可能的决策，否则要在集合中删除（因为往后的位置一定不会选到 \(mid\) ）。因此我们可以维护两个 \(set\) ，一个维护 \(mid+(p_{mid}-1)/2\) 的值，另一个维护 \(mid\) 的值，删除时在两个 \(set\) 中都删除，查询时就在第二个 \(set\) 中二分查找第一个 \(\ge i-p_i\) 的位置。答案取每次查询的最小值即可。注意此时的中心依然是特殊字符。
标签：子串,主说,马要,mid,lmax,半径,长度,拉车,回文 From： https://www.cnblogs.com/Broken-Eclipse/p/16792262.html