计算字符串的最大回文字符数，难点：奇回文与偶回文
解决方法：在字符串中插入特殊字符
如：11311--->#1#1#3#1#1#，无论是奇数还是偶数个字符，都可以变成奇数。
马拉车算法：O（N）
- 准备辅助数组arr[],记录每个位置的回文半径，用前面的记录为后面加速。
- 记录最右回文右边界R
- 记录最右回文右边界R第一次对应的中心C
流程：
- 当前i不在R里面，直接暴力扩展
- i在R内，i'是i关于C的对称点：
- i'的回文直径在C的回文直径【L,R】内，此时不用扩展，arr[i]=arr[i']
- i'的回文左边界<L,没包住，此时i的回文半径是【i,R】
- i'的回文左边界=L，压线，此时i的回文半径需要去试
相关题：
在一个字符串后面添加最少字符是的其成为一个回文串。
解法：找到第一个字符，其回文右边界R包含字符串最后一个字符，则在字符串后面加上L前的字符串逆序即可。
如：abc12321，遍历到‘3’时，R包含1，L为左边1的位置，此时在后面加上cba即可。
Manacher代码实现：
private static char[] manacherString(String str){
StringBuilder sb = new StringBuilder("#");
for(int i = 0; i < str.length(); i++){
sb.append(str.charAt(i));
sb.append('#');
}
return sb.toString().toCharArray();
}
public static int manacher(String str) {
if(str == null || str.length() == 0){
return 0;
}
char[] charArr = manacherString(str);
int[] pArr = new int[charArr.length]; // 回文半径数组
int C = -1; // R对应的中心位置
int R = -1; // 最右回文右边界
int max = Integer.MIN_VALUE;
for(int i = 0; i < charArr.length; i++){
pArr[i] = R > i ? Math.min(pArr[2*C-i], R-i) : 1; // i在R里面，比较对称点回文半径
while(i + pArr[i] < charArr.length && i - pArr[i] > -1){
if(charArr[i + pArr[i]] == charArr[i - pArr[i]]){
pArr[i]++;
} else {
break;
}
}
if(i + pArr[i] > R){ // 更新C,R
R = i + pArr[i];
C = i;
}
max = Math.max(max, pArr[i]);
}
return max - 1; // 最终回文串长度是回文半径-1
}
