预处理：
将字符串每个位置插入特殊符号“#”，例如“abba”为“#a#b#b#a#”，这样每个偶数或奇数回文串都被处理成了奇数回文串。
Manacher算法核心思想：
利用之前回文串的信息来提供当前串的先验信息。
需要维护2两个变量和一个数组：
变量R代表已经发现的所有回文串中可以到达最右的那个回文串的右边界， 变量Center代表满足上述条件回文串的对称中心位置， Parr[i]代表以i为中心的最大回文半径。
如何快速得到Parr[i]？
若R<=i，表明当前位置超过之前所有检查过回文串的右边界，所以没有先验信息可以提供，只能暴力检查以 i 为中心的最大回文半径，然后更新R和Center。 若R>i，表明之前的回文串已经检查过当前位置，所以可以利用对称信息来直接给出 以 i 为中心的最小回文半径，即Parr[i] 至少为 min{ Parr[Center*2-i] , R - i } , 然后直接从最小回文半径往外扩，最大的时间优化就是这个处理。
因为计算过程中R不断往右扩，所以时间为O(N)
