给定一个字符串 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;
    }
};