Manacher（马拉车）算法用于处理字符串最长回文子串问题，其精妙之处在于：通过特殊处理原字符串，统一处理了偶回文与奇回文。
首先特殊处理：ABBBACD ===> #A#B#B#B#A#C#D#(coding技巧：在首尾添加其他特殊符号，免去边界判断)
算法的核心其实是对已经判断过的字符串的信息保存并重复利用，类似动态规划。
例如：ABBBACD的以第二B为轴心（对称性），第三个B可以利用到第一个B的信息
| # | A | # | B | # | B | # | B | # | A | # | C | # | D | # |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 3 | 1 | 2 | 1 | 3 | 1 | 2 | 1 | 2 | 1 | 2 | 1 | 2 | 1 |
- 算法时间复杂度：O(N)
- 空间复杂度：O(N)
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;
}
};
