Leetcode 5. Longest Palindromic Substring

https://leetcode.com/problems/longest-palindromic-substring/

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<algorithm>
        if(s.empty()) return s;
        //init
        char str[maxn];
        int L=2*s.size()+1;
        for(int i=0;i<s.size();++i)
            str[2*i]='#',str[2*i+1]=s[i];
        str[L-1]='#';
        int P[maxn],idx_M=0,mx=0,k_dual,k_r,ans=0;
        P[0]=0;        
        //

        for(int k=1;k<L;++k){
            if(L-k<=P[ans]) break;
            if(k>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)<L && str[k_r+1]==str[2*k-(k_r+1)]) ++k_r;
            P[k]=k_r-k;
            //更新
            if(k_r>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;

    }
};

Leetcode 5. Longest Palindromic Substring

原文：https://www.cnblogs.com/ximelon/p/10768912.html