最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：

输入: "cbbd"
输出: "bb"

class Solution {
public:
    string longestPalindrome(string s) {
        if(s.size()<0)
            return "";

        //解决奇偶回文
        string str("#");
        for(auto it=s.begin();it!=s.end();++it)
        {
            str+=(*it);
            str+="#";
        }

        //以i为中心的最右回文半径
        vector<int> arr(str.length(),0);
        int maxR=0,id=0;//最右回文半径（不包括此值）和回文中心
        int resId=0,resLen=0;//存储结果回文中心和回文半径
        for(int i=0;i<str.length();++i)
        {
            //在maxR内,i与id对应的j,对应的回文半径相等
            //i与maxR的关系:
            //  1>i在maxR内，直接根据j求得
            //  2>j>=maxR,要依次判断尝试 
            arr[i]=maxR>i?min(arr[2*id-i],maxR-i):1;//i在回文半径内，直接可根据回文特性计算得出
            while(i+arr[i]<str.length()&&i-arr[i]>=0)//i不在回文半径内需要依次向两边扩&&在回文半径内也需要判断回文半径外是否存在回文
                if(str[i+arr[i]]==str[i-arr[i]])
                    ++arr[i];
                else
                    break;

            if(maxR<i+arr[i])//更新回文半径和回文中心
            {
                id=i;
                maxR=i+arr[i];
            }

            if(resLen<arr[i])
            {
                resId=i;
                resLen=arr[i];
            }
        }
        return s.substr((resId-resLen+1)/2,resLen-1);
    }
};