字符串 - 最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。

示例1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例2：

输入: "cbbd"
输出: "bb"

解决方法很多，其中有一种时间复杂度达到了O(n)级别，就是Manachar算法。在思想上很类似于KMP，同样是利用已知信息减少重复操作。

一. 情况分析与预处理

• 可以发现的是，回文串有两种情况
  • 奇数回文：aba回文中心是一个字符。
  • 偶数回文：bb回文中心是两个字符中间。
• 为了简化操作（两种情况分别处理），在每个字符左右添加特殊字符#，将两种情况合并为奇数。
  babad化为# b # a # b # a # d #
cbbd化为 # c # b # b # d #
  这时候回文中心必定是一个字符。

二. 如何获取最长回文子串长度？

这里需要借助一个辅助数组p，用于记录以每个字符为中心的最大回文半径。

• 辅助数组与预处理后的字符串数组等长。
• 辅助数组对应位置的值存放以该位置字符为中心的最长回文子串长度。（回文子串只有一个字符时为1）

index 0 1 2 3 4 5 6 7 8 9 10
arr   # b # a # b # a # d #
p     1 2 1 4 1 4 1 2 1 2 1 

得到两个最大值（4），代表着以index=3和index=5两个字符为中心的最大回文子串半径都为4（这个长度包含了特殊字符）。我们去除特殊字符后发现这两个子串为bab和aba，长度为3。

• 在测试更多例子后我们可以发现这样一个规律：最大的半径p[i]与最长回文子串长度maxLength存在这样一种关系
  • const maxLength = p[i] -1

二. 如何获取最长回文子串？

回归题目，显然获取到最大长度是不够的，还需要知道开始的index。
let res = slice(最长回文开始index，index + maxLength)
那么，如何获取这个开始索引呢？Manachar算法给出了一个巧妙的方法。

• 偶数回文情况

index 0 1 2 3 4 5 6 7 8
arr   # c # b # b # d #
p     1 2 1 2 3 2 1 2 1 

最大半径index为4，p[index] = 3，index - p[index] = 1。在cbbd中index = 1刚好就是最长回文bb的开始位置。

• 奇数回文情况

index 0 1 2 3 4 5 6 7 8 9 10
arr   # b # a # b # a # d #
p     1 2 1 4 1 4 1 2 1 2 1 

最大半径index为3，p[index] = 4，index - p[index] = -1。数组越界。

初步结论：最长回文子串开始索引 = index - p[index]，但是奇数情况下不成立。

• 为了解决越界问题，我们在arr前面和后面再添加一对特殊符号$和@（必须成对加）

index 0 1 2 3 4 5 6 7 8 9 10 11 12
arr   $ # b # a # b # a # d  #  @  
p       1 2 1 4 1 4 1 2 1 2  1  

再次使用刚才的结论，最大半径index为4，p[index] = 4，index - p[index] = 0，刚好是babad的最长回文bab的开始索引。

• 奇数回文问题解决，加了两个符号后偶数回文的情况：

index 0 1 2 3 4 5 6 7 8 9 10
arr   $ # c # b # b # d # @
p       1 2 1 2 3 2 1 2 1 

最大半径index为5，p[index] = 3，index - p[index] = 2，结论需要修正，即(index - p[index]) / 2。（奇数情况下 / 2 不影响）

最终结论：最长回文子串的开始索引 = (index - p[index]) / 2

三. 计算辅助数组p

• 计算p是整个算法最核心的地方，也不太好理解。
• 设置两个指针：
  • center：取得tail的回文子串的中心
  • tail：已知的最长回文子串的最右端
• 整个过程是一次数组遍历，假如我们现在要算p[i]（也就是前面的0 <= j < i都已经算完了）。
  1. 情况1：i < tail
     
  • i 仍然处于已知最长子串的范围内，由于回文的对称性，以i为回文中心的子串在左边能够找到对应的j子串。
    其中：j = 2 * center - i
  • 但是需要注意的是，i为中心的回文子串不一定整串都处于已知的center子串范围内，也就是说有可能从右边延展出去。在这种情况下，我们姑且认为i的子串最多到tail位置了，大于tail的部分需要逐一匹配。这种时候，我们暂时认为p[i] = tail - i
    上面两个结论综合得到p[i] = Math.min(p[2*center - i],tail - i)
  2. 情况2：i > tail
     当i大于tail时，无法根据已知信息推断i为中心的子串长度，需要从中心开始扩展。

四. JavaScript实现

function Manacher(str){
    if(str.length < 2){
        return str;
    }

    // 1.预处理，添加'#'以及前后两个特殊字符'$'、'@'
    let s = '$';
    for(let i = 0;i < str.length;i++){
        s += `#${str[i]}`;
    }
    s += '#@';

    // 2.初始化辅助量
    let center = 0;
    let tail = 0;
    let p = [];
    let maxLength = -1;// 最长回文子串的长度
    let index = 0;// 最长回文子串的中心位置

    // 2-1.遍历s
    for(let j = 1;j < s.length - 1;j++){

        // 直接使用i < tail情况下的结论
        p[j] = tail > j ? Math.min(p[2*center - j],tail - j) : 1;

        // 中心向两边扩展
        while(s[j - p[j]] == s[j + p[j]]){
            p[j]++;
        }

        // 如果新的回文串最右端大于tail，就需要更新tail与center
        if(tail < p[j] + j){
            tail = p[j] + j;
            center = j;
        }

        // 如果行的回文串大于maxLength，那么就更新maxLength
        if(maxLength < p[j] - 1){
            maxLength = p[j] - 1;
            index = j;
        }

    }

    let begin = (index - maxLength) / 2;

    return str.slice(begin,begin + maxLength);
}