Manacher算法

Manacher（马拉车）算法用于处理字符串最长回文子串问题，其精妙之处在于：通过特殊处理原字符串，统一处理了偶回文与奇回文。

首先特殊处理：ABBBACD ===> #A#B#B#B#A#C#D#(coding技巧：在首尾添加其他特殊符号，免去边界判断)

算法的核心其实是对已经判断过的字符串的信息保存并重复利用，类似动态规划。

例如：ABBBACD的以第二B为轴心（对称性），第三个B可以利用到第一个B的信息

• 算法时间复杂度：O(N)
• 空间复杂度：O(N)

leetcode：5. 最长回文子串

class Solution {
public:
    string longestPalindrome(string s) {
        string str = "!#";
        for(int i = 0; i < s.size(); i++){
            str.push_back(s[i]);
            str.push_back('#');
        }
        str += "@";
        // 轴心
        int c = 0;
        // 最右边界
        int r = 0;
        int max = 1;
        vector<int> vec(str.size());
        for(int i = 1; i < str.size(); i++){
            if(i < r)
                vec[i] = min(vec[2*c-i], r - i);
            else
                vec[i] = 1;
            while(str[i + vec[i]] == str[i - vec[i]])
                vec[i]++;
            if(r < i + vec[i]){
                r = i + vec[i];
                c = i;
            }
            
            if(vec[i] > vec[max])
                max = i;
        }
        string res="";
        for(int i = max - vec[max] + 2; i < max + vec[max]; i+=2)
            res += str[i];
        return res;
    }
};