1. 介绍
Manacher算法是一种线性时间复杂度的算法，用于查找给定字符串中的最长回文子串。 它由计算机科学家G. Manacher在1975年开发。 该算法在字符串处理中被广泛应用，并在模式匹配和数据压缩等领域有应用。 该算法利用回文字符串的性质来实现高效率
2. 原理
在介绍算法原理之前了解几个概念：
- 暴力解
- 最长回文直径
- 最长回文半径
- 回文半径数组
- 最右回文右边界
- 最右回文右边界的中点
以下s表示给定的字符串
2.1 暴力解
思路：
从每一个位置i开始都从两边扩，即比较s[i-1]和s[i+1]的位置是否相等
时间复杂度为：n^2
存在的问题：如果s的长度为偶数时，会出错，例如s=abba，通过上述方法，那么最长的回文字符串长度为1，但其实是4，因为偶数时回文字符串的对称轴为虚轴
解法：
- 对字符串特殊处理，即在s的每一个字符的前后都加入#，那么经过处理后变为str = #a#b#b#a#，
- 特殊字符可以为任何字符，如果s中存在#字符也不影响最后的结果，因为在对称比较时也是“实和实”、“虚和虚”在比较，不存在“实和虚”的比较，所以不会影响结果。
以下用str代表经过特殊字符处理后的字符串
2.1 最长回文直径 和 最长回文半径
每一个位置的最长回文直径，例如：[#a#1#2#1#b#]
- index=0 位置的最长回文直径为1，因为最长回文字符串就是#自己,最长回文半径为1，为#
- index=1 位置的最长回文直径为3，因为最长回文字符串为#a#, 最长回文半径为2，为#a 或者 a#
- index=5 位置的最长回文直径为7，因为最长回文字符串为#1#2#1#, 最长回文半径为4，为#1#2 或者 2#1#
2.2 最长回文半径数组
Manacher算法的精髓就是利用了最长回文半径数组来加速了整个过程。
最长回文半径数组：pArr[i], 记录了字符串srt每个位置的最长回文半径，那么字符串的最长回文子串就是str[ i - pArr[i] ~ i + pArr[i]]
2.3 最右回文右边界
- 使用R来表示最右回文右边界，含义为：在之前所有扩的位置中，所到达的最右回文右边界。
- 使用C来表示取得最右回文右边界时的中心点位置（必须是R更新时，C跟着更新）
- 使用L来表示当前扩出的最长回文区域的左边界，那么最长回文区域为[L,R]
例如：str = #1#2#2#1# ，初始R=-1，C=-1
- index=0时，该位置扩的最长回文区域为[#]， 所以R=0,C=0
- index=1时，该位置扩的最长回文区域为[#1#]，所以R=2,C=1
- index=2时，扩不动，即该位置的最长回文区域为[#]，R不变，C不变
- index=3时，该位置扩的最长回文区域为[#2#]，R变大了，R=4, C=3
- index=4时，该位置扩的最长回文区域为[#1#2#2#1#]，R变大了，R=8, C=4
- ...
3. 算法实现
3.1 算法步骤
- 当i不在最右回文右边界里，暴力扩，即 i < R
- 当i在最右回文右边界里
- i对应中心点C对称的位置 i', i'的回文区域在[L-R], 判断条件为：i' - pArr[i'] > L，此时i位置的最长回文半径就是i'的最长回文半径，即pArr[i] = pArr[i']
- i'的回文区域的左边界超出了L, 判断条件：i' - pArr[i'] < L，此时i位置的最长回文半径为 R-i
- i'的回文区域的左边界 刚好压在了 L上，判断条件：i' - pArr[i'] = L，此时 pArr[i'] = R-i，需要看下i+1的位置是否也能加入的最长回文区域中，即往i+1的位置扩才能确定
3.2 代码实现
普通版：
public int getLongestPalindromeSubUpgrade(String s){
//1. 特殊处理
String str = manacherStr(s);
int pArr[] = new int[str.length()];
int max = Integer.MIN_VALUE;
int r = -1;
int c = -1;
//2. 分情况，构建 pArr[i]
for (int i = 0; i < str.length(); i++) {
if(i>=r){
//暴力扩
while (i + pArr[i] < s.length() && i - pArr[i] > -1){
if(str.charAt(i + pArr[i]) == str.charAt(i - pArr[i])){
pArr[i]++;
}else {
break;
}
}
//更新R,C
if(i + pArr[i] > r){
r = i + pArr[i];
c = i;
}
}else{
int i1 = 2 * c -i;
int l = 2 * c - r;
if(i1 - pArr[i1] > l){
pArr[i] = pArr[i1];
}else if(i1 - pArr[i1] < l){
pArr[i] = r - i;
}else {
//暴力扩
while (i + pArr[i] < s.length() && i - pArr[i] > -1){
if(str.charAt(i + pArr[i]) == str.charAt(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]);
}
//3. 由于str是特殊处理的，所以返回max-1就是s的最长回文直接
return max-1;
}
private String manacherStr(String s){
char[] str = new char[s.length() * 2 + 1];
int index = 0;
for (int i = 0; i < str.length; i++) {
str[i] = (i&1) == 0 ? '#' : s.charAt(index++);
}
return new String(str);
}
精简版：
public int gethwSubLongestUpgrade(String s){
//1. 特殊处理
String str = manacherStr(s);
int pArr[] = new int[str.length()];
int max = Integer.MIN_VALUE;
int r = -1;
int c = -1;
//2. 分情况，构建 pArr[i]
for (int i = 0; i != str.length(); i++) {
int i1 = 2 * c - i;
//统一处理，i至少的回文区域先给pArr[i]
pArr[i] = r > i ? Math.min(pArr[i1], r-i) : 1;
//统一暴力扩，2.1，2.2的情况也扩不动不影响
while (i + pArr[i] < s.length() && i - pArr[i] > -1){
if(str.charAt(i + pArr[i]) == str.charAt(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]);
}
//3. 由于str是特殊处理的，所以返回max-1就是s的最长回文直接
return max-1;
}
private String manacherStr(String s){
char[] str = new char[s.length() * 2 + 1];
int index = 0;
for (int i = 0; i < str.length; i++) {
str[i] = (i&1) == 0 ? '#' : s.charAt(index++);
}
return new String(str);
}
4. 题目
4.1 最长回文子串
给你一个字符串 s，找到 s 中最长的 回文子串。
4.2 代码
public String longestPalindrome(String s) {
if(s == null || s.length() == 0){
return "";
}
if(s.length() == 1){
return s;
}
//1. 特殊处理
String str = manacherStr(s);
int pArr[] = new int[str.length()];
int r = -1;
int c = -1;
//2. 分情况，构建 pArr[i]
for (int i = 0; i != str.length(); i++) {
int i1 = 2 * c - i;
//统一处理，i至少的回文区域先给pArr[i]
pArr[i] = r > i ? Math.min(pArr[i1], r-i) : 1;
//统一暴力扩，2.1，2.2的情况也扩不动不影响
while (i + pArr[i] < str.length() && i - pArr[i] > -1){
if(str.charAt(i + pArr[i]) == str.charAt(i - pArr[i])){
pArr[i]++;
}else {
break;
}
}
//更新R,C
if(i + pArr[i] > r){
r = i + pArr[i];
c = i;
}
}
//3. 遍历pArr[i]
String res = "";
int max = Integer.MIN_VALUE;
for(int i= 0; i< pArr.length; i++){
if(pArr[i]> max){
max = pArr[i];
res = str.substring(i - pArr[i] + 1, i + pArr[i] - 1);
}
}
return res.replaceAll("#", "");
}
private String manacherStr(String s){
char[] str = new char[s.length() * 2 + 1];
int index = 0;
for (int i = 0; i < str.length; i++) {
str[i] = (i&1) == 0 ? '#' : s.charAt(index++);
}
return new String(str);
}
