给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。
示例1
输入: "babad"
输出: "bab"
注意: "aba"也是一个有效答案。
示例2
输入: "cbbd"
输出: "bb"
代码
class Solution {
public:
string longestPalindrome(string s) {
string ss("$#");
for(int i = 0;i < s.size();++i)
{
ss += s[i];
ss += "#";
}
int id = 0;
int max = 0;
int mid = 0;
vector<int> p(ss.size());
for(int i = 2;i <ss.size();++i)
{
if(p[id] + id > i)
p[i] = min(p[2*id - i],p[id] + id - i);
else
p[i] = 1;
while(ss[i - p[i]] == ss[i + p[i]])
++p[i];
if(max < p[id])
{
max = p[id];
mid = id;
}
if(p[id] + id < p[i] + i)
id = i;
}
string result;
for(int i = mid - max + 1;i < mid + max - 1;++i)
{
if(ss[i] != '#')
result += ss[i];
}
return result;
}
};
