class Solution {
    std::string expend(const std::string& s) {
        std::string res = "@#";
        for (int i = 0; i < s.size(); i++)
            res += s[i], res += '#';
        res += '%';
        return res;
    }

    std::string Manacher(const std::string& s) {
        std::string t = expend(s);
        std::vector<int> p(t.size());
        int mx = 0, pos = 0;
        for (int i = 1, r = 0, c = 0; i < t.size() - 1; i++) {
            p[i] = (r > i ? std::min(p[2 * c - i], r - i) : 1);
            while (t[i - p[i]] == t[i + p[i]])
                p[i]++;
            if (i + p[i] > r) {
                r = i + p[i];
                c = i;
            }
            if (p[i] > mx) {
                mx = p[i];
                pos = i;
            }
        }
        int len = mx - 1;
        int start = (pos - mx) / 2;
        return s.substr(start, len);
    }

public:
    string longestPalindrome(string s) { return Manacher(s); }
};