当初学kmp hash的时候被教导manacher非常的鸡肋
今天因为一篇神奇的题解我忍不住颓废了两节课把它学了
思路，代码都比较好懂
虽然它不如各种自动机霸气，唯一的功能貌似就是$O(n)$求出所有回文串..
不过它的时空花费都比较小
首先为了解决回文串的奇偶问题，在每两个字符中间和整个串的两边都加上一个特殊字符（只要不在原串出现就可以）
然后发现所有的回文串都是奇串，只需要求出以每个点为对称中心的回文串即可
定义一个数组$p[i]$,表示以$i$点为对称中心的回文串的长度+1再/2（其实就是i从这个点到边界的长度）
维护一个变量$center$，表示之前处理过的回文串中，最右端点最靠右的中心
由回文串的性质，我们发现如果这个点关于$center$的对称点的最长回文串被$center$的串完全包含
那么这个$p$就和之前的相等，直接$O(1)$
否则向右暴扫更新右端点，是单调的，所以总的复杂度$O(n)$