求给定字符串中的最长回文串

题目描述
找出给出的字符串S中最长的回文子串。假设S的最大长度为1000，并且只存在唯一解。
思路分析
首先要弄清楚回文串的概念，回文串就是正着顺序和反着顺序是一样的字符串，有aba和abba两种类型。现在我们怎么判断给定的字符串中的回文串呢？开始想着的是依次遍历字符串，然后从字符串的末尾和当前位置之间的字符串是否为回文串来寻找最长的回文串，比如给定字符串"abcbaba"，当前字符为'a'时，先'a'和字符串的末尾字符一致，然后相向缩小，得到'b'和'b'，然后继续缩小，得到'c'和'a'，没有匹配上；接着就让当前字符'a'和倒数第二个继续进行比较判断，一直到挨着的后一个字符，这样的方式复杂度过高。
那么接着想是否可以从回文串的中间字符入手进行比较判断，依次以第二个字符到最后一个字符为回文串的中间字符，看向左向右判断能得到的最长回文串，这样的复杂度能降低到O(n^2)级别。
参考代码如下

    string longestPalindrome(string s) 
    {
        if(s.length()<2) //如果字符串的长度小于2的话，直接返回自身就可以了
            return s;
        string ret=s.substr(0,1); //初始化回文串为第一个字符组成的字符串
        int maxlen=1; //初始最长回文串的长度为1
        int len;
        for(int i=1;i<=s.length()-1;++i) //依次遍历第2个字符到最后一个字符
            longestPalindromeCore(i,s,ret,len,maxlen);
        return ret;
    }
    void longestPalindromeCore(int i,string s,string &ret,int &len,int &maxlen)
    {
        int j=i-1,k=i+1; //当前字符的前一个下标和后一个下标
        len=1;
        while(j>=0 && k<=s.length()-1 && s[j]==s[k]) //aba类型
        {
            len+=2;
            --j;
            ++k;
        }
        if(len>maxlen)
        {
            ret=s.substr(j+1,len);
            maxlen=len;
        }
        j=i-1,k=i+1;
        if(s[j]==s[i]) //abba类型,第二个b是当前字符，第一个b是左边一个与当前字符一样的字符
        {
            len=2;
            --j;
            while(j>=0 && k<=s.length()-1 && s[j]==s[k])
            {
                len+=2;
                --j;
                ++k;
            }
            if(len>maxlen)
            {
                ret=s.substr(j+1,len);
                maxlen=len;
            }
        }
    }