最近刷leetcode时，遇到求最长回文子串问题，一开始想的是暴力匹配算法（逐个字符向两边检索），发现花费时间过长，后来了解到Manacher算法，跟大家分享一下。
一、字符串处理
在暴力匹配算法中，我们以某个字符为对称中心，分别向两边检索，但问题出现了。
如果回文子串长度为奇数，如： ababa
当我们逐个匹配时，肯定会找到最长子串，
但如果长度为偶数时， 如: abaaba
这时对称中心不是某个字符，匹配失败。
所以，为了解决这种问题，我们需要对字符串进行处理
处理前： ababa
处理后: #a#b#a#b#a#
其中'#'为特殊处理字符，你也可以选择其它不在字符串中的字符
二、计算长度
我们用一个数组 len 来表示处理后回文字符串的长度，len[i] 表示以第i个字符为对称中心的回文字符串的半径+1（自身），len[i] -1 表示原字符串(处理前)中以第i个字符为对称中心的回文子串长度。如:
字符串: # a # b # a # b # a #
len[]: 1 2 1 4 1 6 1 4 1 2 1
len-1: 0 1 0 3 0 5 0 3 0 1 0
i : 0 1 2 3 4 5 6 7 8 9 10
我们可以循环遍历求得len数组，但这样和暴力匹配算法没啥区别，所以我们来看看Manacher的精髓:
假设我们求 len[i] 的值，我们设 len[j] ( j < i ) 中的最大值为R,对应的下标为J,其意义是以第J个字符为对称中心的回文子串 (记为S) 的 半径+1 = R。Tl,Tr分别为S的左右端点。如图：
image.png
这时，我们需要对 i 所处的位置情况进行讨论：
当 i >= Tr，即：
image.png
我们需要依次往两边匹配，直到达到边界，或者字符不相等。
当 i < Tr，关于 点J 作 i 对称点 ii，以下标ii 为对称中心的回文字符串记为s：
image.png
当 s 的右端点 <= J,即 ii + len[ii] -1 <= J：
此时 len[i] = len[ii]
image.png
当 s 的 右端点 > J 我们会得到一个必定回文区域，
然后在该区域的端点往两边匹配，直到到达边界，或者字符不相等。
image.png
经过一番比较匹配后，我们会得到 len[ i ] ,如果 len [ i ] > R ( ps: len [ J ] ),
则另 R = len [ i ] , J = i ,再计算 len [ i +1 ] ,直到达到边界。
代码实现
......
int R = 0,J = 0;
for (int i = 0; i <s.length() ; i++) {
if(i < R){
len[i] = Math.min(len[2 * J - i],R-i); // 寻找最短公共半径
}else{
len[i] = 1; // len[i] = 半径 + 自身， 所以初始化为1
}
while(i - len[i] >= 0 && i + len[i] <s.length()
&& s.charAt(i- len[i]) == s.charAt(i + len[i])){
len[i] += 1;
}
if(len[i] > R){
R = len[i];
J = i;
}
}
......
参考文章：
最长回文子串——Manacher 算法
