我们每次遍历都能得到一个最长回文子串的长度，使用一个全局变量保存最大的那个，遍历完后就能得到此题的
解。但分析这种方法的时间复杂度：当来到第一个字符时，只能扩其本身即1个；来到第二个字符时，最多扩两
个；……；来到字符串中间那个字符时，最多扩 (n-1)/2+1 个；因此时间复杂度为 1+2+……+(n-1)/2+1 即
O(N^2) 。但Manacher算法却能做到 O(N) 。
Manacher算法中定义了如下几个概念：
回文半径：串中某个字符最多能向外扩的字符个数称为该字符的回文半径。比如 abcdcb 中字符 d ，能扩一
个 c ，还能再扩一个 b ，再扩就到字符串右边界了，再算上字符本身，字符 d 的回文半径是3。
回文半径数组 pArr ：长度和字符串长度一样，保存串中每个字符的回文半径。比如 charArr="abcdcb" ，
其中 charArr[0]='a' 一个都扩不了，但算上其本身有 pArr[0]=1 ；而 charArr[3]='d' 最多扩2个，算上
其本身有 pArr[3]=3 。
最右回文右边界 R ：遍历过程中，“扩”这一操作扩到的最右的字符的下标。比如 charArr=“abcdcb” ，当遍
历到 a 时，只能扩 a 本身，向外扩不动，所以 R=0 ；当遍历到 b 时，也只能扩 b 本身，所以更新 R=1 ；
但当遍历到 d 时，能向外扩两个字符到 charArr[5]=b ，所以 R 更新为5。
最右回文右边界对应的回文中心 C ： C 与 R 是对应的、同时更新的。比如 abcdcb 遍历到 d 时， R=5 ，
C 就是 charArr[3]='d' 的下标 3 。
处理回文子串长度为偶数的问题：上面拿 abcdcb 来举例，其中 bcdcb 属于一个回文子串，但如果回文子串长度
为偶数呢？像 cabbac ，按照上面定义的“扩”的逻辑岂不是每个字符的回文半径都是0，但事实上 cabbac 的最长
回文子串的长度是6。因为我们上面“扩”的逻辑默认是将回文子串当做奇数长度的串来看的，因此我们在使用
Manacher算法之前还需要将字符串处理一下，这里有一个小技巧，那就是将字符串的首尾和每个字符之间加上一
个特殊符号，这样就能将输入的串统一转为奇数长度的串了。比如 abba 处理过后为 #a#b#b#a ，这样的话就有
charArr[4]='#' 的回文半径为4，也即原串的最大回文子串长度为4。相应代码如下：
接下来分析，BFPRT算法是如何利用遍历过程中计算的 pArr 、 R 、 C 来为后续字符的回文半径的求解加速的。
首先，情况1是，遍历到的字符下标 cur 在 R 的右边（起初另 R=-1 ），这种情况下该字符的最大回文半径
pArr[cur] 的求解无法加速，只能一步步向外扩来求解。
情况2是，遍历到的字符下标 cur 在 R 的左边，这时 pArr[cur] 的求解过程可以利用之前遍历的字符回文半径信
息来加速。分别做 cur 、 R 关于 C 的对称点 cur' 和 L ：
如果从 cur' 向外扩的最大范围的左边界没有超过 L ，那么 pArr[cur]=pArr[cur'] 。
public static char[] manacherString(String str){
char[] source = str.toCharArray();
char chs[] = new char[str.length() * 2 + 1];
for (int i = 0; i < chs.length; i++) {
chs[i] = i % 2 == 0 ? '#' : source[i / 2];
}
return chs;
}
1
2
3
4
5
6
7
8
评论0