以每个位置作为中心，向两边扩展，可以确定奇回文，但是偶回文无法这样做。
解决方法：在字符串中间及两边插入某种字符，此时可以按照这种方法进行扩展。此时无论奇回文还是偶回文都可以找到。
例如11211，此时添加任意字符在两边#1#1#2#1#1#此时均可以进行回文判断。
补充概念：

  • 回文直径：以一个位置为中心，扩出来整个串的长度为回文直径
  • 回文半径：以一个位置为中心，扩出来半个串长度为回文半径
  • 回文数组：对于字符串而言，从0位置开始，一直到最后，新建一个数组，数组中保存对应位置的回文半径。
  • 最右回文右边界：所有回文半径中，最靠右的边界，回文右边界只要没更新，记录最早取得此处的回文中心。
    Manacher算法详解：
    Manacher在向外扩展的过程整体跟之前的算法相似，但是有加速。一共有四种情况：
  1. 回文右边界R不包含位置i，此时暴力扩展，直到R包含i。
  2. i位置在回文有边界内时，知道了回文右边界可以知道回文左边界，对称中心为c，此时关于c做i的对称点i‘，若i‘的回文彻底在c为中心的回文里面，此时i的回文半径和i’的回文半径相同。
  3. i位置的对称位置i’的回文半径越过了以c为中心的左边范围。（i‘扩出的范围以c为中心的回文没包住，存在一部分在回文直径外面）此时i’的回文半径是i-R。
  4. 正好i‘的回文半径正好跟左边L相等，此时可以直到i的回文半径大于等于i-R，然后需要判断R后面的位置，重新返回第一步。
    整个算法的复杂度O(n)，虽然第一步和第四步花费时间长，但是1，4都会扩展R，依次变化的过程中，R最多也就是变化到n，所以时间复杂度为O(n)。
    import java.util.*;

public class Solution {
public int getLongestPalindrome(String A, int n) {
// write code here
int max = Integer.MIN_VALUE;
char[] arr = A.toCharArray();
int[] r = new int[2n+1];
char[] str = new char[2n+1];
for(int i=0,j=0;i<2n+1;i++){
if(i%2==0){
str[i] = '#';
}else{
str[i] = arr[j];
j++;
}
}
int C = -1;
int R = -1;
for(int i=0;i<2n+1;i++){
if(i>=R){
r[i] = 1;
while(i+r[i]<str.length&&i-r[i]>-1){
if(str[i-r[i]]==str[i+r[i]]){
r[i]++;
}else{
break;
}
}
}else{
int iIndex = 2*C-i;
if(iIndex-r[iIndex]>C-r[C]){
r[i] = r[iIndex];
}else if(iIndex-r[iIndex]<C-r[C]){
r[i] = R-i;
}else{
r[i] = R-i;
while(i+r[i]<str.length&&i-r[i]>-1){
if(str[i-r[i]]==str[i+r[i]]){
r[i]++;
}else{
break;
}
}
}
}
if(r[i]+i>R){
R = r[i]+i;
C = i;
}
max = Math.max(r[i],max);
if(i+r[i]==str.length){
break;
}
}
return max-1;
}
}
```