题解 | #最长回文子串#

class Solution {
public:
    void manacher(string s,int n,vector<int>& p){
        int m = 0;
        int r = m + p[0]; //回文串的最右点
        for(int i = 1; i < n; i++){
          //当新中心在之前的回文中时
            if(r > i)
                p[i] = p[2*m-i]<(r - i)?p[2*m-i]:(r-i);
          //r-i表示最右点离新中心的距离，p[2*m-i] = p[i],以m为中心
          //半径p增长，得到以i为中心的最长半径
            for(;s[i + p[i]] == s[i - p[i]] && i - p[i] >= 0 && i + p[i] < 2 * n - 1; p[i]++){
                if(r < i + p[i]){
                  //更新回文中心和最右点
                    r = i + p[i];
                    m = i;
                }
            }
        }
    }
    
    int getLongestPalindrome(string A, int n) {
        string s;
        vector<int> p(2*n+1,1);
        for(int i = 0;i<n+1;i++)  //预处理，插入特殊字符，包含终止符
        {
           s.push_back('#');  
           s.push_back(A[i]);
        }
        
        manacher(s, 2*n+1, p);//计算
        
        int max_len = 0;//寻找最大值
        for(auto i : p){
            max_len = max(max_len,i-1);
        }
        return max_len;
    }
};