\(\rm Manacher\) 是用于求解一个字符串中所有回文子串的算法。
首先，回文子串的数量级是 \(n^{2}\) 的，所以要考虑如何将所有回文子串快速地表达出来，容易发现如下性质：
如果存在一个以 \(p\) 为中心，半径为 \(d\) 的回文子串，那所有以 \(p\) 为中心，半径小于 \(d\) 的子串都是回文子串，证明显然。
于是我们记 \(d_{i}\) 表示以 \(i\) 为中心的最大回文子串，而 \(\rm Manacher\) 算法的用处就是在线性复杂度下求出这个序列。
具体过程跟 \(Z\) 算法类似，记 \(L,R\) 表示在之前的回文子串中，右端点最靠右的子串的左右端点，转移分三种情况：
- 若 \(i\gt R\)，令 \(L=i-1,R=i+1\)，暴力更新。
- 若 \(i\leqslant R,\ d_{L+R-i}\lt 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\) 就是以当前点为中心的最长回文子串的长度。
