最长回文子串问题

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

• 示例 1 ：

输入: "babad"
输出: "bab"

• 示例 2：

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

中心扩展算法

根据回文串的特性：关于中心镜像对称，我们可以将回文串从中间进行展开，共有 2n-1 个中心点。从中心向两边扩展，记录最长的回文子串信息。这样就得到了一个 的算法。

// 中心扩展算法
string longestPalindrome(string s) {
    string temp = "#";
    for(int i = 0; i < s.length(); ++i){
        temp = temp + s[i] + "#";
    }
    int maxL = 0;
    int begin_ = 0;
    int end_ = 0;
    for(int i = 0; i < temp.length(); ++i){
        int begin = i;
        int end = i;
        int currL = 0;
        while(begin >= 0 && end < temp.length() && temp[begin] == temp[end]){
            ++currL;
            --begin;
            ++end;
        }
        if(currL > maxL){
            maxL = currL;
            begin_ = begin + 1;
            end_ = end - 1;
        }
    }
    string res;
    for(int i = begin_; i <= end_; ++i){
        if(temp[i] != '#')
            res += temp[i];
    }
    return res;
}

Manacher 算法

中心扩展算法解决了奇偶不对称这一问题，但是没有解决重复访问字符的问题，这样使得时间复杂度仍然达到了 。Manacher 算法通过跳过部分字符，使得时间复杂度降低到了 。
同中心扩展算法相同，首先需要对字符串 s 做预处理：在每个字符之间及首尾插入不在字符串中出现的字符，以解决奇偶不一致问题。

RL 数组

Mancher 算法定义了一个回文半径数组 RL ，用 RL[i] 表示以第 i 个字符为对称轴的回文半径。

通过观察我们可以发现， RL - 1 的值即为原字符串中以 i 为中心位置的最长回文子串长度。这样我们的问题就变为了如何高效地求 RL 数组的值。

MaxRight 变量与 pos 变量

MaxRight 变量用来表示当前所有回文子串所能触及到的最右一个字符的位置。另外还要记录下 MaxRight 对应回文串的对称轴所在的位置，记为 pos ，它们的位置关系如下：

我们从左往右访问字符串来求 RL ，假设当前访问到的位置为 i ，即要求 RL[i] 。在计算过程中，我们需要关注的是： i 是在 MaxRight 的左边还是右边。我们分情况来讨论：

情况一：i 在 MaxRight 左边

• 图中两个红色块及之间的串是回文的
• 以 i 为对称轴的回文串与红色块间的回文串有所重叠

我们找到 i 关于 pos 的对称位置 j ，此时 RL[j] 已经计算出来，以 i 为对称轴的回文串和以 j 为对称轴的回文串，是一部分相同的，具体分为两种情况：

以 j 为对称轴的回文串较短

• RL[i] 不会小于 RL[j]
• 初始化 RL[i] = RL[j] ，并以 i 为对称轴，继续向左右两边扩展，直到左右两边字符不同，或者到达边界。

以 j 为对称轴的回文串较长

• 不超过 MaxRight 部分一定是回文的
• 初始化 RL[i] = MaxRight - RL[i] ，并以 i 为对称轴，继续向左右两边扩展。

总结起来，具体操作过程为：

1. RL[i] = min(RL[2 * pos - i], MaxRight - i)
2. 以 i 为中心进行扩展，直到两边字符不一致或到达边界
3. 更新 MaxRight 与 pos 。

情况二：i 在 MaxRight 右边：

遇到这种情况，只能从 i 开始扩展。

string longestPalindrome(string s) {
    string temp = "#";
    for(int i = 0; i < s.length(); ++i){
        temp = temp + s[i] + "#";
    }
    int* RL = new int[temp.length()];
    for(int i = 0; i < temp.length(); ++i)
        RL[i] = 1;
    int MaxRight = 0;
    int pos = 0;
    int MaxR = 0;
    int Maxi = 0;
    for(int i = 1; i < temp.length(); ++i){
        RL[i] = i > MaxRight ? 1 : min(RL[2 * pos - i], MaxRight - i);
        int j = i - RL[i];
        int k = i + RL[i];
        while(j >= 0 && k < temp.length() && temp[j] == temp[k]){
            --j;
            ++k;
        }
        if(k-1 > MaxRight){
            MaxRight = k - 1;
            pos = i;
        }
        RL[i] = k - i;
        if(RL[i] > MaxR){
            MaxR = RL[i];
            Maxi = i;
        }
    }
    return s.substr((Maxi + 1 - MaxR) / 2, MaxR - 1);
}

参考文章：

1. Manacher 算法求最长回文子串