Manachar 算法主要处理回文串的，讲 Manachar 算法之前先讲一下中心扩散法求最长回文子串，中心扩散法就是以每一个字符为中心往两边扩散，来找出最长的回文子串。但这样计算会有一个问题，因为我们知道回文串有两种形式，一种是长度为奇数的比如 “aba” ，一种是长度为偶数的比如 “abba” 。如果最长回文子串的长度是偶数，这种方式就不行了。来思考这样一个问题，如果是单个字符，可以认为他是回文子串，如果是多个字符，并且他们都是相同的，他们也是回文串。所以如果以当前字符为中心往两边扩散的时候，最开始的时候如果有相同的则直接跳过，如下图所示。
以当前字符为中心计算完之后，还要以下一个字符为中心在继续计算 …… 。这样计算虽然也没问题，但总感觉不是很完美，以下一个字符为中心计算的时候又要重新开始，有没有一种方法不是每次都要重新计算，而是可以利用之前计算的结果呢？答案是有的，这就是 Manachar 算法。就像我们前面讲的 KMP 算法一样，前面计算的结果实际上还可以重复利用，下面我们就来学习 Manacher 算法的原理。
使用 Manacher 算法会在每个字符之间都插入一个特殊字符，并且两边也会插入，这个特殊字符要保证不能是原字符串中的字符，这样无论原字符串长度是奇数还是偶数，添加之后长度都会变成奇数。
- “aba”–>”#a#b#a#”（原来长度是 3 ，添加之后长度是 7 ）
- “abba”–>”#a#b#b#a#”（原来长度是 4 ，添加之后长度是 9 ）
这里再来引用一个变量叫 回文半径 ，通过添加特殊字符，原来字符串长度无论是奇数还是偶数最终都会变为奇数，因为特殊字符的引用，改变之后的字符串的所有回文子串长度一定都是奇数。并且回文子串的第一个和最后一个字符一定是你添加的那个特殊字符。我们定义 回文子串最中间的那个字符到回文子串最左边的长度叫回文半径 ，如下图所示。
比如字符串 “babad” 在添加特殊字符之后每个字符的回文半径如下所示。
假如以当前字符 s[maxCenter] 为回文中心的最大回文长度是从 left 到 right ，如果求以字符 s[i] 为回文中心的最大回文长度（其中 i>maxCenter ），只需要找到 i 关于 maxCenter 的对称点 j ，看下 j 的回文长度，因为 j 已经计算过了，就会有 3 种情况：
1，如果 i 在 right 的左边，并且 j 的最大回文长度左边没有到达 left ，根据对称性， i 的最大回文长度就等于 j 的最大回文长度。
2，如果 i 在 right 的左边，并且 j 的最大回文长度左边到达或者超过 left ，根据对称性， i 的最小回文半径等于 j-left+1 也等于 right-i+1 ，至于最大能有多大，还需要在继续判断。
3，如果 i 在 right 或者 right 的右边，就没法利用之前计算的结果了，这个时候就需要一个个计算了。
举个例子看下，第一种情况如下图所示。
第二种情况如下图所示。
第三种情况就不画了，因为 i 已经到 right 或者超过 right ，他的最小回文半径是 1 ，然后我们在使用中心扩散法往两边计算，上面三种情况的代码整理如下：
if (i < right) {
// 2 * maxCenter - i 就是 j 的位置。
if (p[2 * maxCenter - i] < right - i) {
// 情况一，i 的左边没有到达 left，直接让 p[i]=p[j] 即可。
p[i] = p[2 * maxCenter - i];
} else {
// 情况二，j 的回文半径左边到达或超过 left ，可以确定p[i]的最
// 小值是 right-i+1，至于到底有多大，后面还需要在计算。
p[i] = right - i + 1;
// 这里可以把 i - p[i] 和 i + p[i] 看做是左右两个指针，往两边走。
// i - p[i] >= 0 && i + p[i] < length 是判断字符的左右边界，不能超出字符串外面。
while (i - p[i] >= 0 && i + p[i] < length && res[i - p[i]] == res[i + p[i]])
p[i]++;
}
} else {
// 情况三，i 到达 right 或者超过 right 。
p[i] = 1;
while (i - p[i] >= 0 && i + p[i] < length && res[i - p[i]] == res[i + p[i]])
p[i]++;
}
上面代码还可以合并，我们来看下完整代码：
// 返回最长回文串长度。
public String getLongestPalindrome(String s) {
int charLen = s.length();// 源字符串的长度。
int length = charLen * 2 + 1;// 添加特殊字符之后的长度。
char[] chars = s.toCharArray();// 源字符串的字符数组。
char[] res = new char[length];// 添加特殊字符的字符数组。
int index = 0;
for (int i = 0; i < res.length; i++) // 添加特殊字符。
res[i] = (i % 2) == 0 ? '#' : chars[index++];
// 新建p数组 ，p[i]表示以res[i]为中心的回文串半径。
int[] p = new int[length];
// right(某个回文串延伸到的最右边下标)，
// maxCenter(right所属回文串中心下标)，
// resCenter（记录遍历过的最大回文串中心下标，主要用于最后字符串截取），
// resLen（记录遍历过的最大回文半径，主要用于最后字符串截取），
int right = 0, maxCenter = 0, resCenter = 0, resLen = 0;
for (int i = 0; i < length; i++) {
// 合并后的代码
p[i] = right > i ? Math.min(right - i + 1, p[2 * maxCenter - i]) : 1;
// 上面的代码只能确定 [i,right-1] 的回文情况，至于 right 以及 right 之后的
// 部分，就只能一个个去匹配了，匹配的时候首先数组不能越界。
while (i - p[i] >= 0 && i + p[i] < length && res[i - p[i]] == res[i + p[i]])
p[i]++;
// 记录更远的 right 以及 maxCenter。
if (i + p[i] > right) {
right = i + p[i] - 1;
maxCenter = i;
}
// 记录最长回文串的半径和中心位置，这个主要用于后面截取然后返回。
if (p[i] > resLen) {
resLen = p[i];
resCenter = i;
}
}
// 计算最长回文串的长度和开始的位置。
resLen = resLen - 1;
int start = (resCenter - resLen) >> 1;
// 截取最长回文子串。
return s.substring(start, start + resLen);
}
