给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd" 输出："bb"
思路
我们回想中心扩散法：某字符处的中心扩散完毕后，其实已经将它身前身后的字符段落都搜索过了，那么如果我们搜索其后的字符能够利用这一点，能否避免不必要的搜索来达到线性时间复杂度O(n)呢？
我们不妨先研究比较简单的一种情况：回文子串只有一个回文中心，是一个奇字符串（后续我们可以用一些方法将奇偶字符串全部处理成奇字符串）
观察这段字符：
--------x--------
--a--
char[i]: f t b a b x b a b t g
i : 0 1 2 3 4 5 6 7 8 9 10
Now i : c |当我们来到char[7]='a'位置时,我们发现他被此前的以'x'为中心的当前最长回文串覆盖住了。
这表明我们可以用此处的以'x'为中心对称点来快速判断而不需要进行暴力扩散。
我们将'x'所在位置称为c，这是我们的回文中心;数组r[i]记录每个点的回文半径（回文半径=本身+扩散距离，如r[c]=5）容易发现i=7的对称点ii=c-(i-r[c])=3。
我们发现ii的回文长度被c的回文长度完全覆盖，这意味着i的回文长度和ii是相等的，那么直接r[i]=r[ii]即可快速得到i的回文长度。
在进行遍历的同时维护中心c，如果某字符在c的屋檐下，那么可以使用回文串的对称性质来避免重复的暴力扩散（毕竟为了得到c的回文长度时我们进行过暴力扩散了），这就是Manacher算法的思想。
只在得到中心c时进行暴力扩散，后续的字符通过c来判断，这样我们就保证了c身前身后的字符只被遍历了一次，因此时间复杂度是O(n)。
解题过程
我们有两个工作要做：一是处理字符串使其称为奇字符串（只有一个中心字符）；二是判断i的对称位置ii的三种情况
首先对字符串进行插值处理：
string ss="#";
for(int i=0;i<s.size();i++){
ss.push_back(s[i]);
ss.push_back('#');
}
//s="abacc"则ss="#a#b#a#c#c#"原字符串的任意回文子串长度为len，新字符串的长度为2*len+1，必然是奇字符串。
这一步的时间复杂度为O(n),有限个线性时间复杂度加和仍是线性的。
接下来开始判断三种情况：
- i=7的对称点ii=3的回文半径被r[c]完全覆盖
--------x-------- --a-- char[i]: f t b a b x b a b t g i : 0 1 2 3 4 5 6 7 8 9 10 Now i : c |此时r[i]=r[ii]，直接continue循环
- i=7的对称点ii=3的回文半径超出r[c]
--------x-------- ------a------ char[i]: b x b a b x b a b x g i : 0 1 2 3 4 5 6 7 8 9 10 Now i : c |此时对r[ii]进行截断，r[i]=ii-(c-r[c])。
这是因为如果r[i]==r[ii]，当初暴力扩散r[c]的时候得到的结果不可能使r[ii]超出r[c]，r[i]==r[ii]时得到的r[c]长度即为情况1) - i=7的对称点ii=3的回文半径恰好压线
--------x-------- ----a---- ------a------ char[i]: f x b a b x b a b x b i : 0 1 2 3 4 5 6 7 8 9 10 Now i : c |此时我们只能知道r[i]至少等于r[ii]，此后应进行暴力扩散
最后，如果我们得到的新回文半径比r[c]长，那么应该令c=i来确保c的r[c]的全局最大性。
至于i>c+r[c]-1？(i不在最长回文串覆盖下)直接暴力扩散就好了。
得到结果后利用string::substr(int pos，int n)（从pos开始的n个字符）方法截取以c为中心的全局最长回文串,过滤掉插值字符'#'后输出答案即可。
复杂度
时间复杂度: O(n)
空间复杂度: O(n)
经测试Manacher算法击败全世界
Code
class Solution {
public:
string longestPalindrome(string s) {
string ss="#";
for(int i=0;i<s.size();i++){ss.push_back(s[i]);ss.push_back('#');}//处理字符串
int c=0,r[2001]={1,};
for(int i=1;i<ss.size();i++){
int j=1;//j是我们用于的暴力扩散的回文半径
if(i<=c+r[c]-1){//i在当前最长回文串中
int ii=c-(i-c);//↓以下为讨论三种情况
if(ii-r[ii]>c-r[c]){r[i]=r[ii];continue;}//r[ii]被r[c]完全覆盖
else if(ii-r[ii]<c-r[c]){r[i]=ii-(c-r[c]);continue;}//r[ii]超出r[c]
else j=r[ii];//r[ii]压线
}
//↓需要暴力扩散：i不在回文串中或r[ii]压线
while(i+j<ss.size()&&i-j>=0&&ss[i+j]==ss[i-j])j++;
r[i]=j;
if(r[i]>=r[c])c=i;//更新c保证其全局最大
}
//↓生成答案
string ans="",ANS=ss.substr(c-r[c]+1,2*r[c]-1);
for(int i=0;i<ANS.size();i++)if(ANS[i]!='#')ans.push_back(ANS[i]);
return ans;
}
};