string Manacher(string s) {
    // Insert '#'：预处理的技巧，通过这样的填充无论是偶数串还是奇数串都变成了偶数长度，
    //但是前面需要加上一个搜索的界限，后边是'\0'
    string t = "$#";
    for (int i = 0; i < s.size(); ++i) {
        t += s[i];
        t += "#";
    }
    // Process t
    vector<int> p(t.size(), 0);
    int mx = 0, id = 0, resLen = 0, resCenter = 0;
    for (int i = 1; i < t.size(); ++i) {
        p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1; // 这边的故事就是一个利用对称点省去
        //繁琐的计算，尽最大可能利用已有的结果，但是这个要求记录最大的右边界
        while (t[i + p[i]] == t[i - p[i]]) ++p[i];
        if (mx < i + p[i]) {
            mx = i + p[i];
            id = i;
        }
        if (resLen < p[i]) {
            resLen = p[i];
            resCenter = i;
        }
    }
    return s.substr((resCenter - resLen) / 2, resLen - 1);
}