manacher算法
斯♥哈♥学长的博客https://www.cnblogs.com/luckyblock/p/17044694.html#5140558
为什么老师叫他马拉车算法/yiw
简介
我们都知道，求最长回文子串可以枚举每一个开始的点，然后直接一个一个比较就完事，但这样的复杂度是接近 \(O(n^{2})\) 的，不出意外你就会
，那么我们这个时候就需要用到 manacher 算法了，他和 KMP 一样都是基于暴力的思想改进的一种算法，利用了已求得的回文半径加速了比较的过程，使复杂度降到了 \(O(n)\) 级别。
过程
上面已经提到 manacher 算法是解决最长回文子串的问题的。
回文串可以分为两种类型：一种是长度为奇数的回文串，比如 \(12321\)，另一种是长度为偶数的回文串，比如： \(123321\)，这个时候我们要是想分类讨论的话也太麻烦了，所以我们就开始用一些奇♂技♂淫♂巧：我们在每一个串的首尾和每一个字符之间插♂入一个字符串，就像下面这样：\(!1!2!3!2!1!\)，\(!1!2!3!3!2!1!\)，这个时候能发现，这俩串都成了长度为奇数的回文串了，那么我们就可以不用分类讨论了。
我们定义 \(p[i]\) 为以 \(i\) 为中心的回文串的最长半径，比如串 \(\%a\%b\%a\%\)，其中 \(b\) 为第四个字符，则 \(p[4]=4\)（因为以他为中心的最长回文串是 \(\%a\%b\%a\%\)，而这个回文串的半径为 \(4\)）。所以我们在原字符串中的这个回文字串长度就是 \(p[i]-1\)，为什么嘞？因为我们原字符串中是这样的 \(aba\)，设上面修改过的串的长度为 \(n\)，则原字符串的长度为 \(\frac{n-1}{2}\)，而我们的半径刚好是 \(\frac{n+1}{2}\)，半径减去原字符串长度则为 \(\frac{n+1-n+1}{2}\)，也就是 \(1\)，所以我们就可以知道半径减去 \(1\)，就是原字符串的长度啦。（你问我为什么给你证这个？当然是后面的我不会证）接下来我们就要来快速求出 \(p[i]\) 数组了，我们假设 \(pos\) 是一个已经记录的值，R$ 为以 \(pos\) 为中心的回文串的最长右边界，然后现在要求 \(p[i]\)，\(j\) 是 \(i\) 关于 \(pos\) 的对称点，也就是说 \(j=2\times pos-i\)。
这个时候就分两种情况了，第一种情况就是 \(j\) 的回文串没有跳出 \(L\)，也就是这样：
因为 \(L\) 到 \(R\) 是一个回文串，所以 \(i\) 的回文和 \(j\) 的回文相同，即 \(p[i]=p[j]\).
第二种情况就是 \(j\) 的最长回文越过了 \(L\)，也就是下面这样：
如果在这种情况下，\(j\) 的最长回文就不一定是 \(i\) 的最长回文了。然后黄色那块肯定还是满足条件的
所以综上，\(p[i]=min(p[2\times pos-1],R-i)\)
然后剩下的那部分怎么办？暴力直接算！
复杂度不会证，看上面学长的博客吧。