class Solution {
public:
    inline int get_min(int x, int y)
    {
        return x < y ? x : y;
    }
    string longestPalindrome(string s) {
        string istr(2 * s.size() + 3, ' ');
        istr[0] = '$';
        istr[istr.size() - 1] = '&';
        istr[1] = '#';
        for(size_t i = 0, beg = 2; i < s.size(); ++i)
        {
            istr[beg++] = s[i];
            istr[beg++] = '#';
        }

        //palindRadiumLen[i]代表以i为中心点的回文串的半径
        vector<int> palindRadiumLen(2 * s.size() + 3, 1);  
        int maxpos = 2, symmetPos = 0;  //回文串半径最长的中心点位置
        palindRadiumLen[maxpos] = 2;
        for(int i = 3; i < istr.size(); ++i)
        {
            if (maxpos + palindRadiumLen[maxpos] > i)
        {
            symmetPos = 2 * maxpos - i;
            palindRadiumLen[i] = get_min(palindRadiumLen[symmetPos], maxpos + palindRadiumLen[maxpos] - i);
        }
            while(istr[i + palindRadiumLen[i]] == istr[i - palindRadiumLen[i]])
                ++palindRadiumLen[i];
            if(palindRadiumLen[i] > palindRadiumLen[maxpos])
                maxpos = i;
        }
        int len = palindRadiumLen[maxpos] - 1;
        string ansstr;
        for(int i = maxpos - palindRadiumLen[maxpos] + 1; i < maxpos + palindRadiumLen[maxpos]; ++i)
            if(istr[i] != '#') ansstr.push_back(istr[i]);
        return ansstr;
    }
};