【Leetcode】5.最长回文子串（Manacher算法）

/*
 * @lc app=leetcode.cn id=5 lang=cpp
 *
 * [5] 最长回文子串
 */
class Solution {
public:
    string longestPalindrome(string s) {
        string str = processString(s);
        int ans=0;  // 结果串的长度
        int ans_pos=0;  // 结果串的中心
        int id=0;  // 搜索最远回文串的中心
        int mx=0;
        vector<int> p(str.size(), 0);
        for (int i=1; i<str.size()-1; i++)
        {
            // 如果前面已经扫描到过这个位置，可以直接和对称位置比较
            p[i] = mx > i ? min(p[2*id-i], mx-i) : 1;

            // 不管用不用搜索，都试一下，和用if判断效果一样
            while (str[i+p[i]] == str[i-p[i]])
                p[i]++;
            
            // 更新一下扫描的最远位置
            if (i+p[i] > mx)
            {
                mx = i+p[i];
                id = i;
            }

            // 更新结果
            if (p[i] > ans)
            {
                ans = p[i];
                // 中心位置
                ans_pos = i;
            }
        }
        return s.substr((ans_pos-ans)/2, ans-1);
    }
    string processString(const string &s)
    {
        string str = "^#";
        for(int i=0; i<s.size(); i++)
        {
            str += s[i];
            str += "#";
        }
        str += "$";
        return str;
    }
};