class Solution {public:    const int maxn=5000;    string longestPalindrome(string s) {        /*        回文串        马拉车算法        先隔着填充#，这样只需要考虑奇数长度的回文串就可以                P[k]:第k个字符为中心的回文串的一半长度(/2)        idx_M,用到最大坐标的回文串的中心位置.        最大坐标mx=idx_M+P[idx_M]        求P[k]时:        若k>mx,则k_r=k;        否则:            k相对idx_M的对偶坐标k_dual=2*idx_M-k,            k_r=min(k+P[k_dual],mx)        可以保证以k为中心,右边延伸到k_r时,仍为回文串        之后继续延伸即可        更新idx_M【实际只有k_r=mx时才更想idx_M】        */        #include
    
             if(s.empty()) return s;        //init        char str[maxn];        int L=2*s.size()+1;        for(int i=0;i
     
      mx) k_r=k;            else{                k_dual=2*idx_M-k;                k_r=min(k+P[k_dual],mx);            }                        while(2*k-(k_r+1)>=0 && (k_r+1)
      
       mx){                idx_M=k;                mx=k_r;            }            if(P[k]>P[ans]) ans=k;        }        string sans;        for(int i=ans-P[ans];i<=ans+P[ans];++i)            if(str[i]!='#') sans.push_back(str[i]);        return sans;    }};