说明
给一个字符串str，要求用O(n)的时间复杂度求出其中最长回文子串的长度
实现步骤
基本过程
求最大回文子串的长度一般要看原串的长度是奇数还是偶数，然后分别求得，但Manacher算法的第一个神奇之处就是把两种字符串都化为长度为奇数，从而简化计算：
public static char[] manacherString(String str) {
char[] charArr = str.toCharArray();
char[] res = new char[str.length() * 2 + 1];
int index = 0;
for(int i = 0;i <= res.length;i++)
res[i] = (i & 1) == 0 ? '#' : charArr[index++];
return res;
}例如原来是aaaba，变化之后就是#a#a#a#b#a#，无论原来是奇数还是偶数，变化之后都是奇数，方便处理
概念引入
manacher算法引入三个重要概念：
- 已知回文串的中心位置C
- 回文串的最右边界R
- 每个字符的回文半径数组pArr
C就是不断遍历的位置，只会向右不会向左。R就是最远的回文半径到了右边哪，有更大的就更新，没有就不变，所以R只会越来越向右，不会回退。pArr[]就是把每个位置的回文半径保存起来
确定回文半径
假设现在求出了pArr[0,...,i-1]，现在要求i的值，分三种情况
如图，黑色部分是当前求出的最长回文直径，C是这个最长回文直径的回文中心，现在要求的是i位置的最长回文半径是多少。蓝色部分是i关于c的对称点i'的回文半径，具体值就是pArr[i']，现在的情况是蓝色的左边界超过了C的左边界，那么i的回文半径就确定是pArr[i]=R - i，为什么不可能更长，假设i的回文半径跟i'是一样的，那i的回文半径就一定能伸展到R的外面，那么这样的话黑色部分应该也会伸长，可是黑色部分只有这么长，说明R后面的字符不足以给i构成更长的回文半径
如图，蓝色部分在黑色部分里面，这是第二种情况，那就很简单了，pArr[i] = pArr[i']
最后一种情况，如图，蓝色部分正好和黑色部分的边界重合，这个时候就不能肯定R后面的字符能否是的i'的回文半径更长，需要去判断
其实还有一种情况，就是i如果在R的外面，这种情况就只能暴力去扩展，看i的最长回文半径有多长。
manacher代码
public static char[] manacherString(String str) {
char[] charArr = str.toCharArray();
char[] res = new char[str.length() * 2 + 1];
int index = 0;
for(int i = 0;i < res.length;i++)
res[i] = (i & 1) == 0 ? '#' : charArr[index++];
return res;
}
public static int maxLcpsLength(String str) {
if(str == null || str.length() == 0)
return 0;
char[] charArr = manacherString(str);
int[] pArr = new int[charArr.length];//回文半径数组
int C = -1,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;
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) {
R = i + pArr[i];
C = i;
}
max = Math.max(max,pArr[i]);
}
return max - 1;
}总结
看到manacher的算法流程，我想到了另一个算法——kmp，两者最初的方法时间复杂度都是O($n^2$)，但是由于通过各种方法，使得有一个参照的东西能够加快进度，时间复杂度变为O(n)，比方说kmp里，加速的东西就是next数组，而manacher就是回文半径数组pArr。这提供了一个很好思路，以后优化什么算法，从记录值来着手，说不定能发现一个更优秀的算法
