Manacher's algorithms（马拉车算法）最长回文子串

最长回文子串

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

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"
输出: "bb"

Manacher’s algorithm

核心思想：通过插入其他的字符，将回文串变为奇回文串。奇回文串一定存在一个中心点loc，对应的有一个半径p[loc]。从左往右遍历，关于每个节点都用扩张法（也就是不断判断两边的边缘是否相同，相同则不断增加） 来得到以它为中心的最长回文子串的边界长度来更新所对应的p[i]。然后，记录下当前 边界最右 的回文子串（即，记录下中心位置loc,以及对应的边界mx）。注意一个非常重要的细节：对于在当然记录下的loc右边的点，明显由于奇回文串的对称性， 能够知道该店关于loc的对称点的半径长度的最小值p[2* loc -i] 。而当然，它也会受到边界mx的限制，在i和mx之间的点，由于对称点的信息基本可以保证不用判断，就算需要判断，但是由于对称性，落入其中一定是因为不能再扩张了，（这点保证了算法时间复杂度被约束在了O(n)），而在mx以外的点，仍然需要用扩张法来扩张对应的半径，（这样虽然是二重循环，但是，第二重只是对于mx以外的点进行了判断，因此仍然是O(n）。

代码

#define min(x, y) ((x)>(y)?(y):(x))
class Solution { 
public:
    string regenerate_str(string s) {  // 插入
        string t("#");
        int count=0;
        for (int i = 0; i < s.size() * 2 + 1; ++i) { 
            if (i % 2 == 0) {  t += s[count++]; }
            else t += "#";
        }
        return t;
    }
    string longestPalindrome(string s) { 
        if (s.size() < 2) return s;
        s = regenerate_str(s);
        int p[2002], start = 0, maxlen = 0;
        int mx = 0, loc = 0;
        for (int i = 0; i < s.size(); ++i) { 
            if (i < mx && 2 * loc - i < s.size()) { 
                p[i] = min(mx - i, p[2 * loc - i]);
            }
            else { 
                p[i] = 1;
            }
            while (p[i] + i < s.size() && i - p[i] >= 0 && s[i - p[i]] == s[i + p[i]])
                p[i] ++;
            if (i + p[i] > mx) { 
                mx = i + p[i];
                loc = i;
            }
            if (p[i] > maxlen) {  maxlen = p[i]; start = i; }
        }
        s = s.substr(start - p[start] + 1, 2 * p[start] - 1);
        string t;
        for (int i = 0; i < s.size(); ++i) { 
            if (s[i] != '#') t.push_back(s[i]);
        }
        return t;
    }
};