Manacher算法
Manacher算法
求最长子回文串
转载声明：@刘毅 (Ethson Liu)
算法过程分析由于回文分为偶回文（比如 bccb）和奇回文（比如 bcacb），而在处理奇偶问题上会比较繁琐，所以这里我们使用一个技巧，具体做法是：
在字符串首尾及每个字符间都插入一个 “#”，这样可以使得原先的奇偶回文都变为奇回文；
接着再在首尾两端各插入 “$” 和 “^”，这样中心扩展寻找回文的时候会自动退出循环，不需每次判断是否越界，可参见下面代码。
上述新插入的三个字符，即 “#”、 “$” 和 “^”，必须各异，且不可以与原字符串中的字符相同。
举个例子：s="abbahopxpo"，转换为 s_new="$#a#b#b#a#h#o#p#x#p#o#^"。如此，s 里起初有一个偶回文 abba 和一个奇回文 opxpo，被转换为 #a#b#b#a# 和 #o#p#x#p#o#，长度都转换成了奇数。
定义一个辅助数组 int p[]，其中 p[i] 表示以 i 为中心的最长回文的半径，例如：
i
0
1
2
3
4
5
6
7
8
9
10 ...
