Manacher 算法求最长回文子串
0. 最长回文子串
回文子串是指字符串中顺序读和逆序读都一样的一个子串。给定一个原串，有且仅有一个最长的回文子串，这类问题要求我们将它求出来。直接将字符串和反转后的串一点点比较的话时间复杂度较高，更何况一般都是比较长的字符串，如果能在线性时间内求解的话节约的时间将是相当可观的，Manacher算法就是一种方法。
1. Manacher算法
该算法利用了回文串对称的特点，利用已经知道的信息来减少对比次数。这个信息就是一个数组P（P[i]代表以i为中心的回文串的半径）和记录最长回文子串中点的max（那么max+P[max]就是中点+半径就是已知最长的回文子串的最右一个字符的下标）。
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| str | b | a | b | c | b | a | b | c | b | a | c | c | b | a |
| P[index] | 0 | 1 | 0 | 3 | 0 | 4 | 0 | 2 | 0 | 0 | 0 | 0 | 0 | 0 |
那么这个数组怎么用呢
比如我们现在要算P[5]，且已经知道一个点max是当前已知的最长回文字串的中点，这个子串就是[str[max-P[max]],str[max+P[max]]]这个区间，上例中max=3，str[3-P[3]]到str[3+P[3]]=“babcbab”。此时：
- index=5这个字符在这个子串之内，即子串最右的下标为max+P[max]=3+3=6，5<6。那么，既然index=5在子串里，它就可以关于max对称，对称点为index'=1，既然对称，那么关于index'已知的信息就可以拿来用：以index'为中心的回文串长度是P[index']=1是“bab”；还是既然对称，那么以index=5为中心的回文串长度也就至少是1，就是str[index-1]到str[index+1]这一部分，那么在计算以index=5为中心的回文串时，就可以跳过index=5到min(index=5+1,max+P[max])这一部分（取小是因为如果以index=5为中心的回文串长度超出了已知最长的右边界，只能确定5到右边界max+P[max]这一段关于5对称，而不能确定右边界max+P[max]到5为中心的子串的最右是否对称），而从min(index=5+1,max+P[max])+1开始继续匹配。
- 如果index > max+P[max]，当前位置超出了已知信息的位置，就只能用普通方法地匹配。
- 还有个重要的问题，如果字符串长度是偶数，那么在以上过程中就会找不到一个中点的字符。解决方法是在原串每个字符两侧加上同一个特殊符号，要求其在原串中没使用过。这样就可以把偶数长的串都变为奇数长。
