一、简介
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;
}