笑点解析：我最终还是更新了 Manacher。
【算法漫笔005】浅谈MANACHER
Manacher 算法用于解决查找最长回文子串问题（下文令操作的字符串 SSS 的长度为 NNN），时间复杂度为 O(N)O(N)O(N)。
BRUTE FORCE
即暴力拓展法。寻找 SSS 中的回文子串，很容易想到暴力匹配。我们遍历 SSS 的每一个字串，检查正读反读是否一样，取最大值即可。时间复杂度为 O(N3)O(N^3)O(N3)，期望 N≤5×102N \le 5 \times 10^2N≤5×102
CENTER EXPANSION
即中心拓展法。分两种情况，即奇回文和偶回文。奇回文遍历 SSS 的每一个字符，从该字符向外拓展，找到不同的即不是回文子串，否则继续向外拓展至边界或两边字符不相同为止。其时间复杂度显然为 O(N2)O(N^2)O(N2)，期望 N≤104N \le 10^4N≤104。
MANACHER
容易发现，Center Expansion算法仍然有许多可以优化的地方，例如：奇回文和偶回文需要单独计算、时间复杂度过高等问题，Manacher将一一解决这些问题。
统一奇偶回文
我们尝试在 SSS 的每两个字符之前插入一个 #[1]，并在头尾也插入一个 #，得到新字符串 TTT。例如我们令 S=abcS=abcS=abc，则 T="#a#b#c#"T=\text{"\#a\#b\#c\#"}T="#a#b#c#"。
显然，此时原串中的任意回文子串都会在 TTT 中对应一个奇数长度的回文串：
* 奇回文 aba 对应 #a#b#a#，中心是 b。
* 偶回文 abba 对应 #a#b#b#a#，中心是 #。
这样我们就成功的统一了奇偶回文。那么时间复杂度怎么处理呢？
回文半径数组
我们定义一个 pip_ipi 表示以 TiT_iTi 为中心的最长回文半径[2]。例如 T="#a#b#a#"T=\text{"\#a\#b\#a\#"}T="#a#b#a#"，则有 p3=4p_3=4p3 =4，即 TTT 本身。显然我们只需要计算出回文半径数组 ppp，那么 res=max(p0,p1…pTlen)res=\max(p_0,p_1 \dots p_{T_{len}})res=max(p0 ,p1 …pTlen ) 的值就是 TTT 的最长回文串长度，而 SSS 的最长回文串长度显然是 res−1res-1res−1。所以问题就转化成了：如何快速计算 pip_ipi ？
快速计算 PIP_IPI
直接对每个 iii 暴力扩展，时间复杂度显然是 O(N2)O(N^2)O(N2)，没有改进。而 Manacher 的核心就是利用的回文的对称性，避免重复扩展。
简单来说，如果一个奇回文串的长度 ≥3\ge 3≥3 的话，那么它一定可以分成 L+c+RL+c+RL+c+R，其中 ccc 是若干个字符，而 LLL 和 RRR 是两个长度相等的子串，且 RRR 是 LLL 的逆序。
不难想到，如果我们已经知道了一个较大的回文串，那么它内部的所有位置都可以利用对称性快速得到回文半径的下界，而不需要重新暴力扩展。
我们维护两个变量 rrr 和 midmidmid，分别表示当前所有回文串中，最靠右的右端点（即 i+pii+p_ii+pi 的最大值）和其对应的回文中心。此时如果要计算 pip_ipi ，我们可以分两种情况讨论。
① I<RI<RI<R
此时 iii 被某个已知的大回文串覆盖。找到 iii 关于 midmidmid 的对称点 j=2×mid−ij=2\times mid-ij=2×mid−i。由于回文的对称性，所以 TjT_jTj 附近的回文情况一定可以反映到 TiT_iTi 附近，但不能超出大回文串的边界 rrr，因此得到：
pi=min(pj,r−i)p_i=\min(p_j,r-i) pi =min(pj ,r−i)
② I≥RI \GE RI≥R
此时无法利用任何信息，我们只能令 pi=1p_i=1pi =1。
此时我们就可以从上述得到的 pip_ipi 开始，继续暴力向两边 Center Expansion。
拓展后若 i+pi>ri+p_i>ri+pi >r，我们就可以更新 r=i+pir=i+p_ir=i+pi 和 mid=imid=imid=i 了。
时间复杂度证明
Manacher 算法的核心思路类似于 exKMP（点我），时间复杂度的证明也类似。
首先：我们需要关注算法中唯一可能带来额外开销的部分，即 while 暴力 Center Expansion 的部分。
关键在于观察到，rrr 在我们整个算法过程中是单调不减的。
1. 当 i<ri<ri<r 时，pip_ipi 被初始化为 min(p[j],r−i)\min(p[j],r-i)min(p[j],r−i)，这保证了我们不会在已知的大回文串内部进行重复的无效扩展。
2. 随后的 while 循环每成功匹配一次，都会使以 iii 为中心的回文串向右扩展一位。因为 iii 是固定的，这必然导致当前最右端点 i+pii+p_ii+pi 向右移动，也就是更新了 rrr 的值，使其至少增加 1。
3. 由于 rrr 的最大值不会超过新串 TTT 的长度 2N+12N+12N+1，所以整个算法过程中，while 循环的总执行次数是 O(N)O(N)O(N) 的。
因此，外层循环遍历 TTT 的每个位置是 O(N)O(N)O(N)，内层 while 循环的总次数也是 O(N)O(N)O(N)，故 Manacher 算法的总时间复杂度为 O(N)O(N)O(N)。
于是我们就得到了 O(N)O(N)O(N) 求最长回文子串问题的算法了。
恭喜你水了一道青题。
洛谷P3805
AC记录
注释&致谢
感谢 StackEdit软件，欢迎大家去使用这个免费的 Markdown 编辑软件。它不仅可以在线使用，还可以下载使用。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1. 此处的 # 作用是不参与回文串的匹配，所以说 # 实际上是指一个不在 SSS 中出现的字符。如果 S 中可能出现 #，我们可以使用一些奇怪的符号，例如：\0、\256 等等。 ↩︎
2. 半径包含中心本身。 ↩︎
