Manacher 马拉车算法（最长回文串） Manacher 马拉车
本人介绍较为简略，实在看不懂网上找博客吧。。。
首先对于求最长回文字符串，有 N^3，有 N^2的，但一般来说要拿满分都要用O（n） 或者更高要求的复杂度。
好的算法都是建立在优化暴力的基础上。比如记忆化搜索、剪枝，省去了不必要的计算和重复的计算，只计算对答案有贡献的东西，效率自然高了。。
有个性质：设一个回文串 [l,r] 的对称轴为 mid ,则若 在对称轴左边有个回文字符串，则相应的在对称轴右边，也有个相同的回文字符串（红色部分）。如图示：
设两回文串的对称轴分别为 x,y，则必定有f[x]<=f[y] （前提是y<=r！！！）
若 y>=r 已经越过边界，那么只能从长度为1开始往两边慢慢扩。并更新r、mid。
可以证明复杂度为O(n)。
若 r 未更新，则 i 可以 O(1)求出；
若 r 更新，则最多移O(n)遍，整个程序就结束了。。。
模板题网上找吧。。。
fighting fighting fighting!!!