题解 | 最长回文子串

class Solution {
public:
    // manacher算法：https://blog.csdn.net/qq_40342400/article/details/124302078
    string get_new_A(string A){
        int n = A.size();
        string temp = "#";
        for(int i=0; i<n; i++){
            (temp += A[i]) += '#';
        }
        return temp;
    }
    int getLongestPalindrome(string A) {
        A = get_new_A(A);
        int n = A.size();

        int cent = 0, right = 0;
        int max_cent = 0, max_r = 0;
        vector<int> r(n, 0);

        for(int i=0; i<n; i++){
            if(i<right){
                int mirror = 2*cent - i;
                r[i] = min(right-i, r[mirror]);
            }
            while(i-r[i]>=0 && i+r[i]<n && A[i-r[i]]==A[i+r[i]])
                r[i]++;
            if(i+r[i] > right){
                cent = i;
                right = cent + r[i];
            }

            if(r[i]>max_r){
                max_cent = i;
                max_r = r[i];
            }
        }

        return max_r-1;
    }
};

三种解题思路：

1、中心法，O(n^2)

for (i in 0~n-1){

以i为中心，向两边扩散，寻找最大回文；

if (长度>res) res=该长度；

}

2、dp

dp[i][j]表示i～j是否是回文，bool类型。

case1：如果i==j，单字符肯定自成一个回文串，dp[i][j]=true;

case2：如果i、j紧邻着（i=j-1），则str[i]==str[j]时，dp[i][j]=true;

case3：如果i、j不挨着，则str[i]==str[j] && dp[i+1][j-1]==true时，dp[i][j]=true；

dp为上三角矩阵。

3、Manacher算法

永远维护一个cent，一个right，表示以cent为中心，右边界为right的回文字串，是当前能看到的“最”右边界。

同时维护一个vector<int> R表示以i为中心的回文，其半径为多少。

那么，遍历 i=0~n-1，

step1：如果i<right，则说明我们能以cent为对称轴找到i的镜像i_mirror，而且其半径已经计算过了。R[i_mirror]=R[i]。

但是，由于当前算法最多能看到right，所以当前中心i到right的距离可能<R[i_mirror]，所以R[i]=min(right-i, R[i_mirror])；

step2：走到这，我们有了一个新的中心i，和以i为中心最长回文串的半径R[i]。那它还能不能帮我们再向右拓宽right呢？

我们以i为中心，以i-R[i]为左起始点，以i+R[i]为右起始点，分别向两边检查字符是否一致，检查完之后，用新的半径更新R[i]

同时如果真实的i+R[i]>right，则更新cent=i，right=i+R[i]。

step3：找到最大的R[i]。

（当然，还有插入#字符以消除偶数回文子串的操作，以上步骤都是在新的字符串上进行操作，则最终最长半径-1即为所求）。