最长回文子串这个问题的Manacher算法，看了很多博客，好不容易理解了，做一下记录。
这个算法的核心就是：将已经查询过的子字符串的最右端下标保存下来，在计算下标为i的回文字符串时，不需要从左右相邻的地方开始比较遍历，而是从某个初始值开始。
那么求这个初值就是该算法的关键。
1.字符串的初始化
先将字符串的每两个字符之间插入标识符，如“#”，然后在头尾也插入，插入什么符号这个其实影响不大。我是在头部和尾部也插入的“#”。这一步是为了让对称轴都在字符串数组中。
实例字符串 abada --> #a#b#a#d#a#
2.计算回文长度的初始
下标i从1 ~ length-1 开始遍历。同时借助2个辅助量 mid 和 maxRight ，maxRight 是用来存储我们扫描过的字符串的最右端的下标。mid为扫描最右端时的对称轴下标。注意，最右端的回文串不一定是最长的回文串。我们只是用maxRight来标识扫描长度。
我们用p[i]来存储回文字符串的单边长度。即以下标i的字符为对称轴的回文串的最右端与i的差值+1。回文串长度/2+1。
示例：
注意：maxRight对应下标时需要-1去对应。因为每次从center开始扩张时，结束条件是maxRight时center不能成为回文中心。
核心代码为这一句：
p[i] = maxRight > i ? Math.min(p[2*center-i],maxRight-i) : 1 ;
可能这样比较难以理解。我们可以结合以上的例子，来慢慢分析。
str[center] - str[maxRight-1]为我们的最右端回文字符串。我们维护这个字符串的位置。
当我们处理str[i]这个字符的回文长度时。
if ( maxRight > i){
//如果当前的位置已经被扫描过了（maxRight为我们扫描过的最右端）
//center肯定在左边，因为是随着i++扫描来更新center的
//假设j是i关于center的对称下标,即i+j=2*center
//string下标示意i图
//0----j---center---i----maxRight------length-1
int j = 2*center-i;
//算法核心：
//由于i j 关于center对称 而 center到maxRight在center~【center-maxRight】也是相同的
//另外由于j的最长回文串长度我们在计算i的时候已经算好了，那么可以认为i的周围也有这么p[j]长度的对称回文串
//center左右对称 j左右长度p[j]字符串对称 那么i左右也有对称字符串
//那么此时分为2种情况
//第一种 ---(j-p[j])--j--(j+p[i])-----center---(i-p[j])----i---(i+p[j])----maxRight
//第二种 ------(i-p[j])----center------i---maxRight----(i+p[j])
if ( p[j] + i<maxRight){
//第一种情况，已扫描范围内就已经找到最大值了
p[i] = p[j];
}else {
//第二张情况，maxRight太小，后面的可能相等，需要左右扩张来判断
p[i] = maxRight - i ;
}
}else {
//0-------maxRight--i
//p[i]还没有扫描呢，因此初始长度就是1
p[i] = 1;
}
上面的核心分析过程简化后就是上面的那一行代码。
核心代码理解了，后续的就简单了，从p[i]的初始值开始，向左右扩张，判断左右边界是不是相等，并同时更新center和maxRight的值。最后扫描p[]数组，其中最大的就是回文子串的长度，下标就是扩充了#的字符串下标。
最后，贴上源代码，大家看一看就可以理解了。
public static String longestPalindrome(String s) {
if ( s.length() <= 1 )return s ;
StringBuilder builder = new StringBuilder();
builder.append("#");
for (int i = 0; i <s.length() ; i++) {
builder.append(s.charAt(i));
builder.append("#");
}
int center = 0 ,maxRight = 0 ,len = builder.length();
int[] p = new int[len];
for (int i = 1; i < len-1; i++) {
//确定已扫描过的字符串中 最长回文串的初始值
//减少的时间复杂度 就在这里
//maxRight都被扫描，初值就不用从0开始了。
p[i] = maxRight > i ? Math.min(p[2*center-i],maxRight-i) : 1 ;
//确定p[i]的初始值后继续扩张判断回文
while (i+p[i] <len && i-p[i]>=0 &&builder.charAt(i+p[i])==builder.charAt(i-p[i])){
p[i]++;
}
//更新maxRight center
if ( i + p[i] > maxRight){
maxRight = i + p[i] ;
center = i ;
}
}
//遍历p数组求极大值
int mid= 0 , maxLength = 0 ;
for (int i = 1; i < builder.length(); i++) {
if ( p[i] > maxLength){
maxLength =p[i];
mid = i;
}
}
//分割字符串，消去"#"
return builder.toString().substring(mid-maxLength+1,mid+maxLength-1).replace("#","");
}