Manacher
Manacher 是用于在 $O(n)$ 的时间复杂度内求出给定字符串所有回文子串的算法。
回文串：
满足 $S[1,|S|]=S[|S|,1]$ 的字符串 $S$ 被称为回文串。
性质：对于回文串 $S$，满足 $S[1,\lfloor\frac{|S|}{2}\rfloor]=S[n,|S|-\lfloor\frac{|S|}{2}\rfloor]$，即回文串是中心对称的。
所以假设确定了对称中心和半径，那么回文串也就确定了。
Manacher：
首先，需要将回文子串分为奇数长或偶数长。若回文串为偶数长，则其对称中心为空字符；若回文串为奇数长，则其对称中心为任意字符。
先考虑奇数长：
假设以 $[1,i]$ 为对称中心的最长回文子串的半径已求好，为 $d_1[i]$，要求 $d_1[i+1]$ 考虑以下两种情况：
- $\max\lbrace i+d_1[i]\rbrace<i+1$，暴力增大 $d_1[i+1]$ 判断是否合法。
- $\max\lbrace i+d_1[i]\rbrace\geq i+1$，考虑在对应的 $\max\lbrace i+d_i\rbrace$ 的回文串中，以 $i’$ 为对称中心，$i+1$ 的对称点 $i’’$。若 $d_1[i’’]\leq i’+d_1[i’]-(i+1)$，那么 $d[i+1]$ 至少为 $d[i’’]$；反之 $d[i+1]$ 至少为 $i’+d_1[i’]-(i+1)$。再暴力增大 $d_1[i+1]$ 判断是否合法即可。
时间复杂度：$O(n)$。
$\max\lbrace i+d_1[i]\rbrace$ 全局维护，当 $d_1[i]$ 更新时，$\max\lbrace i+d_1[i]\rbrace$ 也一定会更新。那么暴力修改 $d_1[i]$ 的次数即为 $O(n)$。
偶数同样处理即可。
特殊处理：
也可以通过一定的特殊处理，将回文串偶数和奇数长度的情况划归到一类中处理。在每两个相邻字符之间插入一个分隔符 #，后按奇数处理方式处理即可。# 为对称中心的情况即为回文串长度为偶数时的情况。