求解最长回文子串的中心扩展法与Manacher算法

端午安康~

好久没写算法类文章了。这个假期出行计划泡了汤，没太多事情做，随便搞一篇吧。

最长回文子串

所谓最长回文子串（longest palindromic substring, LPS），顾名思义就是指一个字符串中，长度最大且又满足回文性质的连续子串。例如："bananas"的最长回文子串是"anana"，"麻麻说上海自来水来自海上"的最长回文子串是"上海自来水来自海上"。

求解最长回文子串是一类有趣的算法问题。本文先介绍比较朴素且容易实现的中心扩展法，再介绍由中心扩展思想改进而来的Manacher算法。

中心扩展法

回文串正着读和反着读是一样的，所以一定会有一个对称中心。因此，naive solution就是在原串中逐个枚举对称中心点，同时向左、向右扩展，并比较左右两侧的字符是否相等，最终取出长度最大的那个即可。

需要注意的是，当回文串长度为奇数时，对称中心是具体的字符，如下图。

但是当回文串长度为偶数时，对称中心会位于两个字符的间隙，如下图所示。

由于我们事先无法确定最长回文子串的长度奇偶性，所以每次扩展都要取两次中心点，再取两者的扩展结果中长度较大的那个。代码如下，比较容易理解。

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        int h = 0, t = 0;
        for (int i = 0; i < s.length(); i++) {
            int l1 = expand(s, i, i);       // 以字符作为中心点扩展
            int l2 = expand(s, i, i + 1);   // 以字符间隙作为中心点扩展
            int pl = Math.max(l1, l2);
            if (pl > t - h) {         // 由当前的LPS长度推出下标范围
                h = i - (pl - 1) / 2;
                t = i + pl / 2;
            }
        }
        return s.substring(h, t + 1);
    }

    private int expand(String s, int l, int r) {
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            l--;
            r++;
        }
        return r - l - 1;
    }
}

显然，中心扩展法的时间复杂度为O(n²)，空间复杂度为O(1)。

Manacher算法

O(n²)的时间复杂度显然不尽如人意。所以在1975年，Manacher提出了一个线性时间复杂度的新算法。该算法狠精妙，下面详细讲解之。

预处理

为了解决偶数长度回文串的对称中心在字符间隙的问题，我们在原字符串每个字符前后都插入原本不存在的分隔符（例如"#"或"|"）。这样，带分隔符的字符串长度就固定为奇数（2n+1）了，不必再考虑字符间隙，并且没有破坏回文子串的对称性。

挖掘对称性

考虑字符串"|a|b|a|a|b|a|"，如果我们按照上述中心扩展法来计算，可以得到下图的结果。

其中，position是各字符的下标，LPS Length则是带分隔符的串中，以各个字符作为中心的回文子串的“半径”（包含中心本身以及除了开头和结尾外的"|"符号）。由于"|"符号也是对称的，所以LPS Length恰好等价于去掉"|"符号之后，原字符串以各位置为中心的回文子串的长度。Manacher算法就是致力于找到LPS Length最大的那个点。

如果我们将LPS Length视为以position为下标的数组lpsl[]，可以发现有以下规律：

• lpsl[6] = 6, lpsl[5] = lpsl[7] = 1, lpsl[4] = lpsl[8] = 0, ...
• lpsl[9] = 3, lpsl[8] = lpsl[10] = 0, lpsl[7] = lpsl[11] = 1, ...

也就是说，lpsl数组可能存在以回文中心为轴的对称性，这并不难理解。以lpsl[6] = 6为例，左侧的lpsl[5] = 1，就说明以position 5为中心的短回文串是以postion 6为中心的长回文串的子串，那么在这个长回文串的右侧必然也存在同样的短回文串。所以，随着lpsl数组的值不断被计算出来，通过充分利用上述对称性，我们就有可能通过左侧已知的lpsl值直接求出右侧未知的lpsl值，而不必从头到尾都用中心扩展法。

算法操作

Manacher算法的初始操作其实就是中心扩展法，但是之后的思路会更聪明一些。具体该如何操作呢？下面就来研究算法运行了一段时间之后的一般情况，如图所示。

初看可能会感到一头雾水，先解释一下几个符号的含义。

• 当前已经遍历到的点记为i。也就是说，在i左侧的点的lpsl值都是已知的；
• 在i左侧有一个回文串中心点C，以C为中心的回文串右边界为R，左边界为R'，并且该回文串的R在当前是最大的，也就是右边界是最靠右的；
• i点关于C的对称点记为i'，显然lpsl[i']已经算出来了，并且有i' - R' = R - i。

那么，我们如何判断能否利用lpsl[i] = lpsl[i']的特性来减少计算量呢？下面将以i'为中心的回文串称为当前回文串，以C为中心的回文串称为最右回文串，分3种情况来讨论。

1. 当lpsl[i'] < i' - R'，即lpsl[i'] < R - i时，说明当前回文串就是最右回文串的子串，所以直接满足最右回文串中R'-C-R的对称性，赋值lpsl[i] = lpsl[i']即可。

2. 当lpsl[i'] = i' - R' = R - i时，说明当前回文串的左边界与最右回文串的左边界重合了，此时仍然满足lpsl[i] = lpsl[i']。但是，R'有可能同时也是原始字符串的左边界，亦即右边的lpsl[i]是有可能更大的，所以接下来应该继续用中心扩展法求出最终的lpsl[i]。

3. 当lpsl[i'] > i' - R'，即lpsl[i'] > R - i时，说明当前回文串的左边界超出了最右回文串的左边界，此时以i点为中心的回文串右边界应该与最右回文串右边界重合，即lpsl[i] = R - i。很显然，如果lpsl[i] > R - i的话，就违反了前述最右回文串的定义，亦即存在一个R更靠右的回文串，产生了矛盾。

以上三种情况都是在i < R的前提下讨论的。如果i >= R，就没有必要利用最右回文串的性质了，直接用中心扩展法从i开始扩展就行了。

最后，我们何时需要更新C和R的位置呢？

容易得知，当以i为中心的回文串右边界超过了R时，现在的C就失效了，需要将C更新到i的位置，并且将R更新到以i为中心的回文串右边界。

代码实现

水到渠成。

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        String t = fill(s);

        int n = t.length();
        int[] lpsl = new int[n];
        int c = 0, r = 0;

        for (int i = 1; i < n - 1; i++) {
            int im = 2 * c - i;                              // i'
            lpsl[i] = i < r ? Math.min(lpsl[im], r - i) : 0; // 三种情况综合起来就是取lpsl[i']和r - i的较小值而已
            while (t.charAt(i - lpsl[i] - 1) == t.charAt(i + lpsl[i] + 1)) {
                lpsl[i]++;         // 中心扩展法更新lpsl
            }
            if (i + lpsl[i] > r) { // 更新C和R
                c = i;
                r = i + lpsl[i];
            }
        }

        int ml = -1, mc = -1;
        for (int i = 1; i < n - 1; i++) {
            if (lpsl[i] > ml) {    // 找到lpsl最大的点
                mc = i;
                ml = lpsl[i];
            }
        }
        int ms = (mc - ml) / 2;    // 除2即可映射到原串的下标
        return s.substring(ms, ms + ml);
    }

    private String fill(String s) {
        String t = "|";
        for (int i = 0; i < s.length(); i++) {
            t += s.charAt(i) + "|";
        }
        return t;
    }
}

复杂度分析

空间复杂度显然为O(n)，但是从代码看是for循环套一个while循环，为什么时间复杂度也是O(n)呢？思考：

• 当i < r时，不会进while循环，lpsl[i]的值可以O(1)地得出。
• 当i > r时，会进入while循环，但是根据上述最右回文串的定义，r肯定是单调递增的，不可能向前退。又因为i会从r + 1开始扫描，故直到整个算法结束，字符串中的每个字符最多只会被访问2次。

正因为进入while循环是有严格的条件的，所以实际的时间复杂度是线性的。

The End

本文配图来自geeksforgeeks.org上的相关系列文章。

凌晨有球看（争冠关键战哈哈），民那晚安晚安。