1. Introduction

Longest palindromic substring(最长回文子串)问题可描述为: 如何在给定字符串中寻找最大长度的连续回文子串. 假设回文子串的正序为$s_1$, 倒序为$s_2$, 则$s_1 = s_2$. 例如, bananas的最长回文子串为anana, apple的最长回文子串为pp.

2. Brute Force

最简单的实现方式是遍历所有字符, 将每个字符视为一个回文子串的中心, 然后以该中心点向外拓展, 直到不满足回文条件. 需要注意的是, 由于回文子串的长度可为偶数, 意味着中心点并不一定是单个字符, 因此需修改原字符串, 假设原字符串为book, 长度为4, 修改后为#b#o#o#k#, 长度为9; 假设原字符串长度为N, 则修改后长度为2N+1, 从而保证字符串的长度永远为奇数.

char[] preprocess(String s) {
    char[] arr = new char[2 * s.length() + 1];
    arr[0] = '#';
    for (int i = 0; i < s.length(); i++) {
        arr[2 * i + 1] = s.charAt(i);
        arr[2 * i + 2] = '#';
    }
    return arr;
}

int longestPalSubstring(String s) {
    char[] arr = preprocess(s);
    int res = 0;
    for (int i = 0; i < arr.length; i++) {
        int l = i - 1, r = i + 1;
        while (l > -1 && r < arr.length && arr[l] == arr[r]) {
            l--;
            r++;
        }
        res = Math.max(res, (r - l - 1) / 2);
    }
    return res;
}

该算法的时间复杂度为$O(N^2)$(原字符串的长度为$N$).

3. Manacher's Algorithm

Brute force的问题在于, 从左向右遍历字符时, 当前字符没有利用之前找到的回文子串信息. 假设原字符串为s, 预处理后的字符串为S, 若当前字符($S[i]$)位于之前某个字符($S[j]$, $j < i$)为中心点的回文子串范围内, 则可找到以$S[j]$为中心, $S[i]$的镜像字符$S[i']$.
$$
\overbrace{S[l] \ldots S_{i'} \ldots S_{j} \ldots S_i \ldots S[r]}^{\text{palindrome}}
$$

介绍Manacher算法前, 需引入三个变量:

  • 最右边界r: 已遍历的字符中, 其回文子串所能抵达的最大边界
  • 中心点c: 最右边界r所在的回文子串的中心点位置
  • 数组p, 其包含每个字符向外拓展所得的回文子串的半径: 该数组长度为$|S|$, 每处理一个字符, 将其回文子串的半径放入p中

以字符串book为例, 预处理后S为$#b#o#o#k#@, S的首字符为$, 尾字符为@, 这两个字符使得中心点向外拓展时无需检查边界. 数组p与S中每个字符的对应如下:

index character in S radius of palindromic substring
0 $ 0
1 # 0
2 b 1
3 # 0
4 o 1
5 # 2
6 o 1
7 # 0
8 k 1
9 # 0
10 @ 0

Manacher算法遍历字符时, 不处理$和@, 因此遍历范围为$[1,|S|-1]$. 假设当前遍历到坐标i, 可能遇到以下情况:

3.1 $i > r$

若$i > r$, 则中心点$c$与$S[i]$的位置关系如下:
$$
\overbrace{S[l] \ldots S_{c} \ldots S[r]}^{\text{palindrome}} \ldots S[i]
$$
$S[l]$表示中心点$c$所在回文子串的左边界. 由于$S[i]$没有位于任何先前遍历字符所在回文子串内, 因此无法使用回文字符串的对称性推断$S[i]$的情况, 只能采用brute force方式向左右拓展, 直到字符不匹配, 并更新最右边界$r$和中心点$c$.

3.2 $i \le r$

若$i \le r$, 则$S[i]$以$c$为轴, 可以找到镜像坐标$i'$($i - c = c - i'$):
$$
\overbrace{S[l] \ldots S[i'] \ldots S_{c} \ldots S[i] \ldots S[r]}^{\text{palindrome}}
$$
假设$S[i']$的半径为k, 存在以下几种情况:

  1. $i'-k > l$: $S[i']$所在回文子串的左边界未超出$c$所在回文子串的左边界, 字符串如下:
    $$
    \overbrace{S[l] \ldots \underbrace{S[i'-k] \ldots S[i'] \ldots S[i'+k]}_{\text{palindrome}} \ldots S_{c} \ldots S[i] \ldots S[r]}^{\text{palindrome}}
    $$

    上图可得出以下结论:

    • 由于$S[l:r]$为回文字符串, 且$S[i'-k:i'+k]$为回文字符串, 因此$S[i-k:i+k]$为回文字符串
    • 由于$S[i']$所在的回文子串的半径为k, 因此$S[i'-k-1] \ne S[i'+k+1] = S[i-k-1]$
    • 由于$S[l:r]$为回文字符串, 且$i'-k > l$, 因此$S[i'-k-1] = S[i+k+1]$

    综上所述, $S[i+k+1] = S[i'-k-1] \ne S[i'+k+1] = S[i-k-1]$, 因此$S[i]$所在回文子串的半径为k.

  2. $i'-k = l$: $S[i']$所在回文子串的左边界等同c所在回文子串的左边界, 字符串如下:
    $$
    S[l-1] \quad \overbrace{\underbrace{S[l] (S[i'-k]) \ldots S[i'] \ldots S[i'+k]}_{\text{palindrome}} \ldots S_{c} \ldots S[i] \ldots S[r] (S[i+k])}^{\text{palindrome}} \quad S[r+1]
    $$

    上图可得出以下结论:

    • 由于$S[l:r]$为回文字符串, 且$S[i'-k:i'+k]$为回文字符串, 因此$S[i-k:i+k]$为回文字符串
    • 由于$S[i']$所在回文子串的半径为k, 因此$S[i'-k-1] \ne S[i'+k+1] = S[i-k-1]$
    • 由于$l = i'-k-1$, 因此$S[i'-k-1]$与$S[i+k+1]$的关系不确定

    因此$S[i-k-1]$与$S[i+k+1]$的关系无法确定, 但$S[i]$所在回文子串的长度至少为k.

  3. $i-k < l$: $S[i']$所在回文子串的左边界超出c所在回文子串的左边界, 字符串如下:
    $$
    \rlap{\underbrace{\phantom{S[i'-k] \ldots S[l] \ldots S[i'] \ldots S[i'+k]}}_{\text{palindrome}}}
    S[i'-k] \ldots \overbrace{S[l] \ldots S[i'] \ldots S[i'+k] \ldots S_{c} \ldots S[i] \ldots S[r]}^{\text{palindrome}}
    $$

    该情况与第二种情况相同: $S[i]$所在回文子串的半径至少为k.

4. Implementation of Manacher

char[] preprocess(String s) {
    char[] t = new char[s.length()*2 + 3];
    t[0] = '$';
    t[s.length()*2 + 2] = '@';
    for (int i = 0; i < s.length(); i++) {
        t[2*i + 1] = '#';
        t[2*i + 2] = s.charAt(i);
    }
    t[s.length()*2 + 1] = '#';
    return t;
}
    
int[] Manacher(String s) {
    char[] t = preprocess(s);
    int[] p = new int[t.length];
    int center = 0, right = 0;
    for (int i = 1; i < t.length-1; i++) {
        int mirror = 2*center - i;
        if (right > i) {
            p[i] = Math.min(right - i, p[mirror]);
        }
        while (t[i + (1 + p[i])] == t[i - (1 + p[i])]) {
            p[i]++;
        }
        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }
    }
    return p;
}

上述代码中, Manacher()返回数组p, 若需要最长回文子串的长度, 可遍历p并找到最大值; 若需要最长回文子串, 可调用以下函数:

String longestPalindromicSubstring(String s, int[] p) {
    int len = 0, c = 0;
    for (int i = 1; i < p.length-1; i++) {
        if (p[i] > len) {
            len = p[i];
            c = i;
        }
    }
    return s.substring((c - 1 - len) / 2, (c - 1 + len) / 2);
}