Manacher算法
最长回文子串问题
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
示例 3：
输入：s = "a"
输出："a"
示例 4：
输入：s = "ac"
输出："a"
提示：
1 <= s.length <= 1000s仅由数字和英文字母（大写和/或小写）组成
方法一：中心扩散法
第 1 步：预处理
第一步是对原始字符串进行预处理，也就是 添加分隔符 。
首先在字符串的首尾、相邻的字符中插入分隔符，例如 "babad" 添加分隔符 "#" 以后得到 "#b#a#b#a#d#"。
对这一点有如下说明：
1、分隔符是一个字符，种类也只有一个，并且这个字符一定不能是原始字符串中出现过的字符；
2、加入了分隔符以后，使得“间隙”有了具体的位置，方便后续的讨论，并且 新字符串中的任意一个回文子串在原始字符串中一定能找到唯一的一个回文子串与之对应 ，因此对新字符串的回文子串的研究就能得到原始字符串的回文子串；
3、新字符串的回文子串的长度一定是奇数；
4、新字符串的回文子串一定以分隔符作为两边的边界，因此分隔符起到“哨兵”的作用。
第 2 步：计算辅助数组 p
辅助数组 p 记录了新字符串中以每个字符为中心的回文子串的信息。
手动的计算方法仍然是“中心扩散法”，此时记录以当前字符为中心，向左右两边同时扩散，记录能够扩散的最大步数。
以字符串 "abbabb" 为例，说明如何手动计算得到辅助数组 p ，我们要填的就是下面这张表。
| Char | # | A | # | B | # | B | # | A | # | B | # | B | # |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| p |
第 1 行数组 char ：原始字符串 加上分隔符以后 的每个字符。
第 2 行数组 index ：这个数组是新字符串的索引数组，它的值是从 0 开始的索引编号。
- 我们首先填
p[0]。
以 char[0] = '#' 为中心，同时向左边向右扩散，走 1 步就碰到边界了，因此能扩散的步数为 0，因此 p[0] = 0；
| Char | # | A | # | B | # | B | # | A | # | B | # | B | # |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| p | 0 |
- 下面填写
p[1]。
以 char[1] = 'A' 为中心，同时向左边向右扩散，走 1 步，左右都是 "#"，构成回文子串，于是再继续同时向左边向右边扩散，左边就碰到边界了，最多能扩散的步数”为 1，因此 p[1] = 1；
| Char | # | A | # | B | # | B | # | A | # | B | # | B | # |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| p | 0 | 1 |
- 下面填写
p[2]。
以 char[2] = '#' 为中心，同时向左边向右扩散，走 1 步，左边是 "a"，右边是 "b"，不匹配，最多能扩散的步数为 0，因此 p[2] = 0；
| Char | # | A | # | B | # | B | # | A | # | B | # | B | # |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| p | 0 | 1 | 0 |
- 下面填写
p[3]。
以 char[3] = 'b' 为中心，同时向左边向右扩散，走 1 步，左右两边都是 “#”，构成回文子串，继续同时向左边向右扩散，左边是 "a"，右边是 "b"，不匹配，最多能扩散的步数为 1 ，因此 p[3] = 1；
| Char | # | A | # | B | # | B | # | A | # | B | # | B | # |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| p | 0 | 1 | 0 | 1 |
下面填写 p[4]。
| Char | # | A | # | B | # | B | # | A | # | B | # | B | # |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| p | 0 | 1 | 0 | 1 | 4 |
继续填完 p 数组剩下的部分。
分析到这里，后面的数字不难填出，最后写成如下表格：
| Char | # | A | # | B | # | B | # | A | # | B | # | B | # |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| p | 0 | 1 | 0 | 1 | 4 | 1 | 0 | 5 | 0 | 1 | 2 | 1 | 0 |
说明 ：有些资料将辅助数组 p 定义为回文半径数组，即 p[i] 记录了以新字符串第 i 个字符为中心的回文字符串的半径（包括第 i 个字符），与我们这里定义的辅助数组 p 有一个字符的偏差，本质上是一样的。
下面是辅助数组 p 的结论：辅助数组 p 的最大值是 5，对应了原字符串 "abbabb" 的 “最长回文子串” ："bbabb"。这个结论具有一般性，即：
辅助数组 `p` 的最大值就是“最长回文子串”的长度
因此，我们可以在计算辅助数组 p 的过程中记录这个最大值，并且记录最长回文子串。
简单说明一下这是为什么：
如果新回文子串的中心是一个字符，那么原始回文子串的中心也是一个字符，在新回文子串中，向两边扩散的特点是：“先分隔符，后字符”，同样扩散的步数因为有分隔符 # 的作用，在新字符串中每扩散两步，虽然实际上只扫到一个有效字符，但是相当于在原始字符串中相当于计算了两个字符。
因为最后一定以分隔符结尾，还要计算一个，正好这个就可以把原始回文子串的中心算进去；
如果新回文子串的中心是 #，那么原始回文子串的中心就是一个“空隙”。在新回文子串中，向两边扩散的特点是：“先字符，后分隔符”，扩散的步数因为有分隔符 # 的作用，在新字符串中每扩散两步，虽然实际上只扫到一个有效字符，但是相当于在原始字符串中相当于计算了两个字符。
因此，“辅助数组 p 的最大值就是“最长回文子串”的长度”这个结论是成立的，可以看下面的图理解上面说的 2 点。
写到这里，其实已经能写出一版代码。（注：本文的代码是结合了 LeetCode 第 5 题「最长回文子串」进行讲解）
public class Solution {
public String longestPalindrome(String s) {
// 获取字符串的长度
int len = s.length();
// 若字符串的长度小于2（0或者是1,则说明该串不是回文子串，也不存在回文子串）
if (len < 2) {
return s;
}
// 给字符串添加分割符号
String str = addBoundaries(s, '#');
// 添加分割符后字符串的长度变为2*len+1
int sLen = str.length();
int[] p = new int[sLen];
// 设置字符串的最长回文子串长度的初始值为1
int maxLen = 1;
// start用于记录最长回文字符串的开始位置
int start = 0;
for (int i = 0; i < sLen; i++) {
// 获取字符串中心的左边位置
int left = i - (1 + p[i]);
// 获取字符串中心的右边位置
int right = i + (1 + p[i]);
// 从中心位置向两边扩散
while (left >= 0 && right < sLen && str.charAt(left) == str.charAt(right)) {
p[i]++;
left--;
right++;
}
// 如果返回的最大回文子串的长度大于已经记录的最大回文子串的长度,则更新当前最大的回文子串的长度
if (p[i] > maxLen) {
maxLen = p[i];
start = (i - maxLen) / 2;
}
}
return s.substring(start, start + maxLen);
}
/ **
* 创建预处理字符串
*
* @param s 原始字符串
* @param divide 分隔字符
* @return 使用分隔字符处理以后得到的字符串
*/
private String addBoundaries(String s, char divide) {
// 获取字符串长度
int len = s.length();
// 若字符串长度为0，则返回一个空字符串,长度为0的字符串不需要添加分割符号
if (len == 0) {
return "";
}
// 判断分割符是否在字符串中存在,若分隔符在字符串中存在,则需要抛出参数异常错误
if (s.indexOf(divide) != -1) {
throw new IllegalArgumentException("参数错误，您传递的分割字符，在输入字符串中存在！");
}
// 使用字符串拼接函数拼接字符
StringBuilder sb = new StringBuilder();
// 遍历整个字符串,先是在每个字符前面加上分割符
// 然后在字符串的最后加上分割符
for (int i = 0; i < len; i++) {
sb.append(divide);
sb.append(s.charAt(i));
}
sb.append(divide);
return sb.toString();
}
}
- 时间复杂度：O(N2)，这里 N 是原始字符串的长度。新字符串的长度是 2 * N + 1，不计系数与常数项，因此时间复杂度仍为 O(N2)。
- 空间复杂度：O(N)。
方法二：Manacher算法
上面的代码不太智能的地方是，对新字符串每一个位置进行中心扩散，会导致原始字符串的每一个字符被访问多次，一个比较极端的情况就是：#a#a#a#a#a#a#a#a#。事实上，计算机科学家 Manacher 就改进了这种算法，使得在填写新的辅助数组 p 的值的时候，能够参考已经填写过的辅助数组 p 的值，使得新字符串每个字符只访问了一次，整体时间复杂度由o(N2)改进到o(N)
具体做法是：在遍历的过程中，除了循环变量 i 以外，我们还需要记录两个变量，它们是 maxRight 和 center ，它们分别的含义如下：
maxRight：记录当前向右扩展的最远边界，即从开始到现在使用“中心扩散法”能得到的回文子串，它能延伸到的最右端的位置 。对于maxRight我们说明 3 点：
1.“向右最远”是在计算辅助数组 p 的过程中，向右边扩散能走的索引最大的位置，注意：得到一个 maxRight 所对应的回文子串，并不一定是当前得到的“最长回文子串”，很可能的一种情况是，某个回文子串可能比较短，但是它正好在整个字符串比较靠后的位置；
2.maxRight 的下一个位置可能是不被程序看到的，停止的为左边界不能扩散，导致右边界受限制也不能扩散；
3.为什么 maxRight 很重要？因为扫描是从左向右进行的， maxRight 能够提供的信息最多，它是一个重要的分类讨论的标准，因此我们需要一个变量记录它。
center：center是与maxRight相关的一个变量，它是上述maxRight的回文中心的索引值。对于center的说明如下：
** maxRight 与 center 是一一对应的关系，即一个 center 的值唯一对应了一个 maxRight 的值；因此 ** maxRight 与 center 必须要同时更新 **。
下面的讨论就根据循环变量 i 与 maxRight 的关系展开讨论(maxRight 与 center 的初始值均为0)：
情况 1 ：当 center =<maxRight<= i 的时候，这就是一开始，以及刚刚把一个回文子串扫描完的情况，此时只能够根据“中心扩散法”一个一个扫描，逐渐扩大 maxRight；
情况 2 ：当 center=< i < maxRight(i值不可能小于center,因为i是在center之后遍历的) 的时候，根据回文串的对称性质，循环变量i关于 center 对称的那个索引（记为 mirror）的 p 值就很重要。
我们先看 mirror 的值是多少，因为 center 是中心，i 和 mirror 关于 center 中心对称，因此 (mirror + i) / 2 = center ，所以 mirror = 2 * center - i。
根据 p[mirror] 的数值从小到大，具体可以分为如下 3 种情况：
情况 2（1） ：p[mirror] 的数值比较小，不超过 maxRight - i。
从图上可以看出，由于“以 center 为中心的回文子串”的对称性，导致了“以 i 为中心的回文子串”与“以 center 为中心的回文子串”也具有对称性，“以 i 为中心的回文子串”与“以 center 为中心的回文子串”不能再扩散了，此时，直接把数值抄过来即可，即 p[i] = p[mirror]。
情况 2（2） ：p[mirror] 的数值恰好等于 maxRight - i。
说明：仍然是依据“以 center 为中心的回文子串”的对称性，导致了“以 i 为中心的回文子串”与“以 center 为中心的回文子串”也具有对称性。
- 因为靠左边的
f与靠右边的g的原因，导致“以center为中心的回文子串”不能继续扩散； - 但是“以
i为中心的回文子串” 还可以继续扩散。
因此，可以先把 p[mirror] 的值抄过来，然后继续“中心扩散法”，继续增加 maxRight。
情况 2（3） ：p[mirror] 的数值大于 maxRight - i。
说明：仍然是依据“以 center 为中心的回文子串”的对称性，导致了“以 i 为中心的回文子串”与“以 center 为中心的回文子串”也具有对称性。
下面证明，p[i] = maxRight - i ，证明的方法还是利用三个回文子串的对称性。
① 由于“以 center 为中心的回文子串”的对称性， 黄色箭头对应的字符 c 和 e 一定不相等；
② 由于“以 mirror 为中心的回文子串”的对称性， 绿色箭头对应的字符 c 和 c 一定相等；
③ 又由于“以 center 为中心的回文子串”的对称性， 蓝色箭头对应的字符 c 和 c 一定相等；
推出红色箭头对应的字符 c 和 e 一定不相等。
因此，p[i] = maxRight - i，不可能再大。上面是因为我画的图，可能看的朋友会觉得理所当然。事实上，可以使用反证法证明：
如果“以 i 为中心的回文子串” 再向两边扩散的两个字符 c 和 e 相等，就能够推出黄色、绿色、蓝色、红色箭头所指向的 8 个变量的值都相等，此时“以 center 为中心的回文子串” 就可以再同时向左边和右边扩散 格，与 maxRight 的最大性矛盾。
合以上 3 种情况，当 i < maxRight 的时候，p[i] 可以参考 p[mirror] 的信息，以 maxRight - i 作为参考标准，p[i] 的值应该是保守的，即二者之中较小的那个值：
p[i] = min(maxRight - i, p[mirror]);
public class Solution {
public String longestPalindrome(String s) {
int len = s.length();
if (len < 2) {
return s;
}
String str = addBoundaries(s, '#');
int sLen = str.length();
int[] p = new int[sLen];
int maxRight = 0;
int center = 0;
int maxLen = 1;
int start = 0;
for (int i = 0; i < sLen; i++) {
// 通过 maxRight 和 center 更新p[i]
if (i < maxRight) {
int mirror = 2 * center - i;
p[i] = maxRight > i ? Math.min(maxRight - i, p[mirror]) : 1;
}
// 获取字符串中心的左边位置
int left = i - (1 + p[i]);
// 获取字符串中心的右边位置
int right = i + (1 + p[i]);
// 从中心开始向两边扩散
while (left >= 0 && right < sLen && str.charAt(left) == str.charAt(right)) {
p[i]++;
left--;
right++;
}
// 更新 maxRight 和 center
if (i + p[i] > maxRight) {
maxRight = i + p[i];
center = i;
}
if (p[i] > maxLen) {
maxLen = p[i];
start = (i - maxLen) / 2;
}
}
return s.substring(start, start + maxLen);
}
/ **
* 创建预处理字符串
*
* @param s 原始字符串
* @param divide 分隔字符
* @return 使用分隔字符处理以后得到的字符串
*/
private String addBoundaries(String s, char divide) {
int len = s.length();
if (len == 0) {
return "";
}
if (s.indexOf(divide) != -1) {
throw new IllegalArgumentException("参数错误，您传递的分割字符，在输入字符串中存在！");
}
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < len; i++) {
stringBuilder.append(divide);
stringBuilder.append(s.charAt(i));
}
stringBuilder.append(divide);
return stringBuilder.toString();
}
}
复杂度分析：
-
时间复杂度：o(n)，由于 Manacher 算法只有在遇到还未匹配的位置时才进行匹配，已经匹配过的位置不再匹配，因此对于字符串
S的每一个位置，都只进行一次匹配，算法的复杂度为o(n)。 -
空间复杂度：o(n)。