大致题意
就是求字符串的最长回文子串
解题思路
这题当然是用爆爆爆爆爆爆力啊
最长回文子串有多种求法吧
刚好趁着这题学了一下马拉车算法，我是说Manacher算法
参考了这篇博客
Manacher算法的原理其实很简单
-
首先，在字符串s的每个字符中间添加该字符串不存在的符号，比如’#’，这样做并不会影响整个字符串的回文情况，但是，这样可以解决因为字符子串奇偶长度回文情况的差异，构建得到的字符串称为news(….)
-
然后定义辅助数组p，p[i]表示以i为中心在news中最长回文串的半径，得到了p，就可以直接求最长回文子串长度了
-
那么问题来了，怎么求p
-
定义辅助变量pos和mx
mx当前回文子串能达到的最右位置
pos为当前回文子串的中心
-
然后开始从左向右扫描字符串news，下标为i
-
判断i是否在mx左边，如果不在的话就不在当前已知回文串区域，直接让p[i] = 1
在的话它一定关于pos对称的那个点对称情况在回文区域相同，所以超出mx的部分不可以直接计算
-
然后判断i 不是可以继续回文（这个主意处理的就是在上一部分超出mx的部分）
-
最后判断新的回文字符串是否可以到达比mx更远的地方
-
重复step3~5
-
string longestPalindrome(string s) {
int len = s.length();
//构建新字符串
char news[2012];
int p[2012] = { 0 };
news[0] = '@'; //news[0]先赋值另一个符号这样可以防止越界
for (int i = 1; i < len+1; i++){
news[2 * i - 1] = '#';
news[2 * i] = s[i - 1];
}
news[2 * len + 1] = '#'; news[2 * len + 2] = 0;
len = 2 * len + 2;
int pos = 0, mx = 0, maxlen = 0, maxindex = 0;
for (int i = 1; i < len; i++){
if (i < mx) //判断i是否在mx左边，如果不在的话就不在当前已知回文串区域
p[i] = min(p[pos * 2 - i], mx - i); //在的话它一定关于pos对称的那个点对称情况在回文区域相同，所以超出mx的部分不可以直接计算
else
p[i] = 1;
while (news[i - p[i]] == news[i + p[i]]) //在当前已知的p[i]情况下继续判断p[i]是不是有可能更大
p[i]++;
if (mx < p[i] + i) { //更新mx和pos
pos = i;
mx = p[i] + i;
}
//记录最长回文子串
if (maxlen < p[i] - 1) {
maxlen = p[i] - 1;
maxindex = pos * 2 - mx + 1;
}
}
//拼接最小回文子串
for (int i = 0; i < maxlen; i++)
news[i] = news[maxindex + i * 2 + 1];
news[maxlen] = 0;
return news;
}
