前言
Manacher算法目前了解到的适用范围只有求回文字符串。以下的所有解析也都会围绕求最大回文字符串来展开（求最大回文子串）。
什么是回文字符串？
回文字符串就是如“abba”,"abcba",这种围绕中心完全对称的字符串。
题目：在字符串里求出他的最大回文子串
如：12323，他的最大回文子串就是232和323。
接下来我们引入几个概念 对称中心，顾名思义就是对称最中心的那个数，比如121的对称中心就是2.因为我们这里需要把对称中心由一个数字具体表示，所以我们没法表示偶数数量的对称中心(比如1221的对称中心是22中间的对称轴)。那这里怎么解决呢？在每个数字的两边插入任意相同的字符（为什么是任意呢？因为原先对称的串在插入对称的字符后依然对称，所以随便插入什么字符都不会影响原先的结果），这里以插入#举例，插入后的效果是这样的。
插入完之后原来偶数数量对称的串都会变成奇数，并且也不会产生新的对称字符串（具体不理解的手画一遍就懂了），并且我们根据变化之后的（字符串长度/2）就可以得到原来字符串的长度了。
这时候可以用一种暴力解法来完成功能，遍历一遍数组，遍历过的每个元素都执行一遍操作：检验遍历过的元素的左右两边是否相等，如果相等则继续往外检验是否相等直到遇到左右不相等的字符为止或者碰到数组的边界为止。（举个例子：看上面那幅图，当我遍历到b时，我会检测b左边一位和b右边一位是否相等，这里是相等所以我继续将往左两位和往右两位进行比较）。这样就可以得到我们以该字符为中心的回文字符串的长度。然后再拿变量去记录最长的长度和下标，我们就能得到最终最长子字串的长度了。虽然这样已经能够实现功能，但他还有能够优化的地方，Manacher算法就是在这的基础上优化的。
为了后面的运算能够快捷，我们需要申请一个长度等于加#后长度的数组，用来存储已经遍历过的每个位置的（中心的最长子字符串长度/2）。这里为什么要除以2呢，不是因为之前加过#要算回原来的大小，而是我们后面需要知道串伸向最右边的那个点（先不用知道为什么），而我们现在已经有了中心点的下标了，这时候直接加上一半的长度就可以得到该子串最右边的坐标了。
现在开始我们进行Manacher算法的讲解。
第一种情况 maxRight(遍历过的回文子串达到过最右的位置，一开始是0)小于现在所遍历到的位置，那就按照之前的解法一个个的遍历并记录每个的最大长度/2并更新maxRight.
第二种情况 maxRight大于现在所遍历到的位置。那么这时候将再分成三种情况。这里我们设当前遍历到的元素为 i，子字符串达到最右边的距离为maxRight,达到maxRight的子串中心center，i关于center的对称点 j，还有记录之前所遍历所有元素的最长臂长long[]（从此以后臂长就是最大长度/2）。
①maxRight - i > long[j]
如图，假设这的的long[j] = 1，那么我们可以直接得到long[i] = 1且不需要做额外的对比。这是为什么呢？因为在maxRight内，i两边的内容和j两边的内容是完全相等的（因为关于center对称），而 j处的最大子串由不超过center的子串（由式子得出来的），所以long[i] = long[j]。
② maxRight - i = long[j]
这里直接说结论，当相等时，检测i的最长子串可以直接从maxRight右边开始，maxRight左边至i的位置一定是回文的（因为j与i对称且j在maxRight'之前都是对称），然后maxRight的右边由于是为检验过的区域所以不知道能不能与i组成回文，只要直接从maxRight的右边检测就行。
③ maxRight - i < long[j]
当满足上述式子时，是不是可以直接从maxRight右边开始检测呢？不必，因为这时候的结论是long[i] = maxRight - i ，这是因为如果这时候i的回文串能再往外多一个，就说明那个点与j在maxright'左边的那个点相等了，那就满足了center的中心回文的条件，这是矛盾的。所以这个时候long[i] = maxRight - i。
上述的几种情况是可以进行合并的，可观察①和③。当maxRight - i > long[j] 时 long[i] = long[j]，当maxRight - i < long[j] 时 long[i] = maxRight - i，再看②，是直接long[i] = long[j]然后再往后搜索。那我们就可以合并这三个式子为long[i] = min(maxRight - i,long[j])并再往后搜索。
接下来就是重复上面的操作，记得每算完一个元素在对应的long里写进去他的臂长，也要及时修改maxRight的值。
总结
搜索最大回文子串，当i大于maxRight时，按照暴力解法从中心往外拓展搜索并记录搜索过位置的long[i]和maxRight；i小于maxRight时，long[i] = min(maxRight - i,long[j])并再往后搜索。
复杂度对比，直接暴力解发的时间复杂度是O(n^3),以搜索子串中心为目的的暴力解发时间复杂度是O(n^2),动态规划时间复杂度为O(n^2),Manacher算法的时间复杂度是O(n)，空间复杂度是O(n)。
