一、简介
Manacher 算法，又称“马拉车算法”，主要用于求解最长回文子串的长度
二、经典最长回文子串长度求法
从字符串的每个字符开始，向左右两边扩，算出以每个字符为中心的回文子串的长度，然后取最大值。
但是用这种方法只能算出奇回文子串的长度，无法算出偶回文子串的长度，如下图所示，这是一个长度为 4 的回文串，但用上面的方法没办法算出它的长度，因为上面的方法是以一个字符为中心算长度，但是偶回文子串的中心并不是一个字符。
为了可以计算出偶回文子串的长度，我们可以对字符串做一些变化，把 “abba” 变成 “#a#b#b#a#” ，然后按照上面的方面再计算一次，就可以算出来了，最大值除以 2 向下取整就是最长回文串的长度。
这里是在原字符串的每个字符前后加了特殊符号 “#”，但其实这个特殊符号加什么都行，只是为了方便，就算原字符串中本来就有 “#” 也不会有影响，因为我们可以发现在比较的时候原字符只会与原字符进行比较，特殊字符只与特殊字符比较。
整个过程的时间复杂度为 O(n2)
三、Manacher 算法
与 KMP 有点类似，就是对经典的算法做一个加速
1、几个重要的概念，
以字符串 “#a#b#b#a#b#b#a#”为例
回文半径：从中心字符到回文子串结束的距离，如回文子串 “#a#” 的回文半径就是 2，“#a#b#b#a#” 的回文半径是5
回文半径数组 pArr：与 KMP 的next 数组有点类似，回文半径数组存放的是每个字符对应回文子串的半径
最右回文右边界 R：之前所有的回文子串的最右的边界
最右回文右边界的中心 C：即最右回文有边界对应的回文串的中心位置
2、Manacher算法流程
主要是计算回文半径数组 pArr，分为两种情况
1）下一个字符的位置 i 不在 R 里，这种情况 R 直接往右扩，且以这个字符为中心的回文子串的长度至少为 1
2）下一个字符的位置 i 在 R 里，找到 i 相对于 C 的对称点 j，这时又分为三种情况，记 R 相对于 C 的字符为 L，[L……R]即为以 C 为中心最长回文子串
① j 为中心的回文子串（下面称 j 回文子串）在 [L……R] 里，那么 i 为中心的回文子串（下面称 i 回文子串）半径与以 j 回文子串半径相等
② j 回文子串部分在 [L…… R]里，那么 i 回文子串半径为 R - i
③ j 回文子串的左边界正好等于 L，那么 i 回文子串半径至少为 R - i，然后继续往外扩
证明：主要证 2）部分
2）①如下图所示，j 左右的小括号区域（下面称为 j 区域）代表 j 回文子串 ，因为 L 到 R 是以 C 为中心的最长回文子串，所以 i 左右的小括号区域（下面称为 i 区域）与 j 区域一定是互相逆序的，又因为 j 区域是回文子串，所以 i 区域也是回文子串。那么如何确定它是最大呢？我们假设 x 是以 j 回文子串前一个字符，y 是后一个字符，p、q同理分别为以 i 回文子串前一个和后一个字符，我们假设刚才的回文子串不是最大，那么p 和 q 必是相等的，按照回文串的性质，p和y相等，q和x 相等，则x 和 y 一定是相等的，但是 j 回文子串是不包括 x 和 y 的，也就是说 x 和 y 不可能相等，即 p 和 q 不可能相等，假设不成立，所以 i 回文子串半径一定与 j 回文子串半径相等。
② j 回文子串不全在 [L……R] 里，如下图所示，找到 L 相对于 j 的对称点 L' ，由回文串的性质可知，[L…… L'] 一定是回文子串，所以与之对应 [R'…… R] 也是回文串，所以 i 回文子串的半径最小是 R - i。那有没有可能更大呢？不可能。下图中 x 是 L 的前一个字符，y 是 L' 的后一个字符，p 是 R' 的前一个字符，q 是 R 后一个字符。i 回文子串半径要想更大，就需要 p 和 q 相等，我们现在已知 x 和 y 都属于 j 回文子串，所以 x 和 y 相等，y 和 p 相等，即 x 和 p 相等，因为 以 C 为中心的最长回文子串的左右边界是 L 和 R，所以 x 和 q 是不可能相等的，结合起来就是 p 不可能等于 q，所以 i 的回文子串半径最大为 R - i。
③ j 回文子串的左边界正好等于 L，如下图所示，首先我们可以肯定 i 回文子串至少是 R - i，至于能不能继续扩大，就需要看 p 能不能等于 q，从图中可以看出，与前面两种情况不同，p 等不等于 q，并不会破坏 j 回文子串和以 C 为中心的回文子串，所以 p 是可以等于 q 的，如果 p 等于 q，那么 R 往右扩， i 回文子串半径 +1，直到不能继续向右为止。
3、时间复杂度
O(n)
具体分析过程，可以看 左神的视频讲解
4、具体实现
//转换字符串
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;
}
//具体的 manacher 算法
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;
//回文右边界
int R = -1;
//最大的回文半径
int max = Integer.MIN_VALUE;
//求每一个位置的回文半径
for (int i = 0; i != charArr.length; i++) {
//i 至少的回文区域，先给 pArr[i]
/**
* 同时满足上面的两类情况
* 1）如果 R < i，即 i 不在 R 里，那么半径至少为 1
* 2）如果 R > i，即 i 在 R 里，那么
* p[Arr[2 * C - i]]：i 关于 C 的对称点 j 所对应的回文半径
* 为什么取两者的较小值呢？
* 首先三种情况：
* 如果 j 回文子串完全在 C 回文子串里，那么 i 回文子串半径就是p[Arr[2 * C - i]]
* 如果 j 回文子串在部分在 C 回文子串里，那么 i 回文子串半径就是 R - i
* 如果 j 回文子串左边界正好等于 C 回文子串的左边界，那么 i 回文子串半径至少为 R - i
* 因为 j 回文子串可能不全在 C 回文子串里，
* 当 j 回文子串满足第一种情况时，此时 R - i >= p[Arr[2 * C - i]]， i 回文子串半径就是p[Arr[2 * C - i]]
* 当 j 回文子串满足第二、第三种情况时， 此时 R - i <= p[Arr[2 * C - i]]，i 回文子串半径就是 R - i
* 所以直接写成了 Math.min(pArr[2 * C - i], R - i)
*/
pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1;
/**
*
* 主要针对 R < i 和 j 回文子串左边界正好等于 C 回文子串的左边界这两种情况，回文子串需要扩充
* pArr[i]存放了当前位置的最少的回文半径,charArr[i + pArr[i]]和charArr[i - pArr[i]分别是当前回文子串的后一个和前一个字符，相等则 pArr[i]++，否则break
*
* 虽然上面 j 回文子串完全在 C 回文子串里和 j 回文子串在部分在 C 回文子串里时，pArr[i] 已经是确定值，不需要再扩充，
* 但为了代码方便，减少 if else 使用，直接全部扩充，不需要的扩充的仅需进行一次判断就 break了，对代码整体时间复杂度影响不大
*/
while (i + pArr[i] < charArr.length && i - pArr[i] > -1) {
if (charArr[i + pArr[i]] == charArr[i - pArr[i]]) {
pArr[i]++;
} else {
break;
}
}
/**
* 判断当前字符的回文子串的有边界是否大于之前最右回文有边界
* 如果大于，更新 R 和 C
*/
if (i + pArr[i] > R) {
R = i + pArr[i];
C = i;
}
//取出最大半径
max = Math.max(max, pArr[i]);
}
//max 中包括是 # 字符的半径，max - 1正好是原回文串的长度
return max - 1;
}
