书接上回。
发现中考英语作文没拿满分，严肃意识到自己不会字符串。
由于现在是上午，所以只学一个算法，剩下一个放在下午。
MANACHER
将每个字符两边用一个滚木包裹，使得所有回文串长度都为奇数。
考虑维护此时每个 iii 为中心的最长回文子串端点与 iii 的距离 PiP_iPi 。则原串答案显然为 (2Pi+1)−12=Pi\frac{(2P_i+1)-1}{2}=P_i2(2Pi +1)−1 =Pi 。
考虑维护目前小于 iii 为中心的最长回文子串中右端点最大值 rrr 及其中心 midmidmid。
由回文串定义（关于中心对称）得，iii 为中心，min{r,i+Pmid−(i−mid)}\min\{r,i+P_{mid-(i-mid)}\}min{r,i+Pmid−(i−mid) } 为右端点的串一定回文。
然后暴力扩展，更新 midmidmid 与 rrr。每次暴力扩展一定会使 rrr 移动 111，而 rrr 一共只会移动 nnn 次，所以时间复杂度为 O(n)O(n)O(n)。
时间复杂度：O(n)O(n)O(n)。
