Manacher 算法

$\rm Manacher$ 是用于求解一个字符串中所有回文子串的算法。

首先，回文子串的数量级是 $n^2$ 的，所以要考虑如何将所有回文子串快速地表达出来，容易发现如下性质：

如果存在一个以 $p$ 为中心，半径为 $d$ 的回文子串，那所有以 $p$ 为中心，半径小于 $d$ 的子串都是回文子串，证明显然。

于是我们记 $d_i$ 表示以 $i$ 为中心的最大回文子串，而 $\rm Manacher$ 算法的用处就是在线性复杂度下求出这个序列。

具体过程跟 $Z$ 算法类似，记 $L,R$ 表示在之前的回文子串中，右端点最靠右的子串的左右端点，转移分三种情况：

• 若 $i>R$，令 $L=i-1,R=i+1$，暴力更新。

• 若 $i\leqslant R~\&~d_{L+R-i}<R-i$，$d_i=d_{L+R-i}$。

• 若 $i\leqslant R~\&~d_{L+R-i}\geqslant R-i$，令 $L=2i-R$，暴力更新。

由于 $R$ 只会往右移，且每次暴力更新必定右移一位，所以时间复杂度为 $\Theta(n)$。

但是我们发现，上面这种方法只处理了回文子串长度为奇数的情况，而偶数的情况只需要分开考虑，奇偶性稍微改变一下即可，但还有一种更加巧妙的方式可以规避分奇偶讨论。

考虑给所有字符之间加入一个不可能出现的相同字符，如字符串 $abaca$ 变成 $\#a\#b\#a\#c\#a\#$，这样在奇数位上统计的就是字串长度为偶数的答案，在偶数位上统计的就是字串长度为奇数的答案。同时，这样统计出来的半径 $d$ 就是以当前点为中心的最长回文子串的长度。