Manacher算法
- manacher算法解决的问题
- 回文 最长回文子串
- 最长回文子串解法
- 解法1.0
- 解法2.0
- Manacher算法
- 回文半径、回文直径
- 回文半径数组
- 之前扩的所有位置中所到达的最右回文右边界(R)
- 取得更远边界的中心点的位置(C)
- Manacher算法优化情形
- Manacher算法优化情形总结
- manacher算法代码实现
manacher算法解决的问题
- 求解最长回文子串的长度
- 大部分回文问题都可以用manacher算法
- 将求解的时间复杂度降到O(N)
回文 最长回文子串
注：此处是根据我的理解进行讲解，需要准确的定义，自行进行搜索，我的讲解只是为了让你们更好的理解
- 回文
字符串正着读反着读都是它本身，或者可以看作它是关于某一个轴对称。
比如"123321" “aba” 就是回文。
-
最长回文子串
- 一个字符串的子串(包括字符串本身)，子串要求连续
- 是回文
- 最长
例：str为"abc112320de1"
根据最长回文子串的定义可以看出，"11"和"232"为回文子串，而“232”最长，所以“232”为最长回文子串，而"12321"不是，因为他是不连续的，也就不是str的子串。
最长回文子串解法
解法1.0
根据回文的定义我们可以想到通用的解法，就是能不能对字符串先进行遍历，然后看当前字符的左右字符是否相等，如果不相等，就直接返回当前回文长度，最开始的回文长度为1，如果相等回文子串长度加1，然后继续向左右两边扩充，不断反复，直到左右字符不等，或者到达字符串左右边界。根据这个想法，我们对上面的str字符串进行该操作。
通过该操作，我们似乎可以得到最长回文子串，但是，这种做法，存在一个问题，就是他忽略了回文长度为偶数的回文！！显然，假如回文是偶数的话，我们不能采取这种做法。那我们就需要对上面的想法进行改进，也就是解法2.0.
解法2.0
在原来的字符串的每个字符左右两边填充特殊字符，然后按照解法1.0的步骤求出每个字符的回文长度，然后取出最大的回文字符长度除以2，得到最终的最长回文子串长度，还是以上面的str字符为例，进行讲解。
我们可以看出，这样的做法对于偶数回文“11”，奇数回文“232”都求出来了，这里的除以2是向下取整不然结果长度会多1个。
理解了这种做法，我们来深入研究一下一些问题。
这里插入的特殊字符有限制吗？
答案是没有，这里的特殊字符没有什么限制，没有说非要是字符串中不存在的字符。这里你们可以看一下你们加了特殊字符，在求原来字符串的各个字符的回文长度的时候，这些特殊字符对于回文有没有影响？答案显而易见，是没有的，所以这里的特殊字符是没有限制的。
这种结果的时间复杂度是多少？
答案是O(N^ 2)，为什么呢？这里不太好解释，我只能讲解个大概，求某一个位置的回文长度，他的往两边扩充要么扩充到左边界停，要么扩充到右边界停，字符串从左边界到字符串中间，字符串中间到字符串右边，扩充次数是个等差数列，所以时间复杂度是O( N^2 )， 假如有大佬能够讲解清楚，可以在评论区留言。
这里我们就引出了Manacher算法，因为它能将时间复杂度缩小到O(N)!!!假如你学过kmp算法，那么对于Manacher算法，你会觉得学起来很轻松，因为它借鉴了kmp算法的next数组进行加速，最终达到O(N)的时间复杂度。
Manacher算法
Manacher算法有四个概念需要理解分别是回文半径、回文直径，回文半径数组，之前扩的所有位置中所到达的最右回文右边界®和取得更远边界的中心点的位置©，这些概念先大致了解，等后面在详细讲解。
回文半径、回文直径
当你求解一个字符的回文字符串长度时，这个回文字符串的长度就是就是回文直径，而对这个回文字符串长度除2向上取整就是回文半径，以上面的str的回文子串“121”为例子，“121”的回文直径是3，回文半径就是2，也就是字符串的“21”或者“12”的长度。
回文半径数组
对于要求字符串的每个字符左右两边填充特殊字符，然后从左往右求每个字符的回文半径放入一个数组中，类似于kmp算法的next数组。
之前扩的所有位置中所到达的最右回文右边界®
这里我用一个例子进行讲解，文字难以表达，你从左往右看我推的过程就能看明白，假如不懂，可以在评论区留言。该值是int类型，在图中我用变量n表示。
取得更远边界的中心点的位置©
int类型，初始值为-1，中心点位置是随着R的值变化的，R变化则C也变化，R不变C也不变，这两个概念有点抽象，因为我们都不知道这两个概念有什么用，先大致的看一下，等后面用到了，自然就明白了。
Manacher算法优化情形
这里的话，不要想太复杂，Manacher算法的思路还是跟解法2.0一样，但是它是为了提速，那么它提速就会有要求，就类似kmp算法，next数组里的数是-1，自然没有提速的办法，只能暴力扩充，看它的回文长度是多少，进而更新其他参数，直到满足提速要求，进行提速。
(1)当来到某个点的时候，这个点没有在最右回文右边界里，暴力扩充，不存在优化。
以第一个字符“#”为例子，此时最右回文右边界是-1，而中心点位置为0，此时，当前点位置不在最右回文右边界里，故直接暴力扩充。
(2)当所处点在最右回文右边界里，则存在优化。
假如所处点在最右回文右边界里，则说明当前点在中心点到最右回文右边界的内部。当前点可能跟中心点重合。
后续简写字母说明：
i ：当前所在位置
i‘ ：i关于中心点C对称位置
R：最右回文右边界
L：R关于中心点C对称位置
C：中心点的位置
按照 i‘ 的 回文状况对（2）大情形进行划分。
(2-1) i’ 自己的回文区域在L-R之间
此时i的回文半径跟i’的回文半径相同。
这个地方很好理解，因为L-R首先是关于C对称的，i跟i‘ 是对称的，那么i的回文半径不就跟i’的一样啦。
(2-2) i’ 自己的回文区域有一部分在L-R区域之外
此时i的回文半径就是i到R。
这里看图就能看明白，我就不多赘述了，总而言之，还是因为对称。
(2-3) i’ 自己的回文区域与L压线
此时i的回文半径只能说至少的i‘的回文半径，具体多少，还要继续扩，以上图为例，i的”abcdcba“子串肯定是回文子串，但是需要看k和？是否相等，如果相等，回文半径+1，不相等则当前大小就是回文半径。
Manacher算法优化情形总结
(1)当来到某个点的时候，这个点没有在最右回文右边界里，暴力扩充，不存在优化。
(2)当所处点在最右回文右边界里，则存在优化。
(2-1) i’ 自己的回文区域在L-R之间，此时i的回文半径跟i’的回文半径相同。
(2-2) i’ 自己的回文区域有一部分在L-R区域之外，此时i的回文半径就是i到R。
(2-3) i’ 自己的回文区域与L压线，此时i的回文半径只能说至少的i‘的回文半径，具体多少，还要继续判断。
manacher算法代码实现
/**
* 将字符串变为处理串 字符数组
* @param str
* @return char[]
*/
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 s) {
if(s == null || s.length() == 0) {
return 0;
}
char[] str = manacherString(s); // 1221 -->#1#2#2#1#
int[] pArr = new int[str.length]; //回文半径数组
int C = -1; //中心点
int R = -1; //最右回文右边界，这里是回文右边界再往右的一个位置，最右有效区是R-1的位置
int max = Integer.MIN_VALUE; //扩出来的最大值
for (int i = 0; i != str.length; i++) { //对每个位置求回文半径
//对两个大情况进行分析，判断不用求的回文半径是多少，也就是加速的地方
//Math.min(pArr[2 * C - 1],R - i)
//pArr[2 * C - 1] 2 * C - 1就是i‘ 这个参数就是i’的回文半径。
//R - i i到R之间的距离
//回文半径大于 i到r之间的距离 对应 2-2 回文半径大于L-R 取i-r
//回文半径小于 i到r之间的距离 对应 2-1 2-3 回文半径小于L-R以及回文半径在L上 取i的回文半径
pArr[i] = R > i ? Math.min(pArr[2 * C - 1],R - i) : 1;
//从不要求的区域开始往外扩，看能不能扩，能就是(1) (2-3)两种情况，不能则是(2-1)(2-2)
//这里只是让代码更加简洁，避免过多的if判断
while (i + pArr[i] < str.length && i - pArr[i] > -1) {
if (str[i + pArr[i]] == str[i - pArr[i]])
pArr[i]++;
else {
break;
}
}
if (i + pArr[i] > R) {
R = i + pArr[i];
C = i;
}
max = Math.max(max, pArr[i]);
}
//回文半径向上取整了，所以会多1
return max - 1;
}
}
}
if (i + pArr[i] > R) {
R = i + pArr[i];
C = i;
}
max = Math.max(max, pArr[i]);
}
//回文半径向上取整了，所以会多1
return max - 1;
}
