Manacher（馬拉車）算法用于處理字符串最長回文子串問題，其精妙之處在于：通過特殊處理原字符串，統(tǒng)一處理了偶回文與奇回文。

首先特殊處理：ABBBACD ===> #A#B#B#B#A#C#D#(coding技巧：在首尾添加其他特殊符號，免去邊界判斷)

算法的核心其實是對已經(jīng)判斷過的字符串的信息保存并重復(fù)利用，類似動態(tài)規(guī)劃。

例如：ABBBACD的以第二B為軸心（對稱性），第三個B可以利用到第一個B的信息

• 算法時間復(fù)雜度：O(N)
• 空間復(fù)雜度：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;
    }
};