Lintcode-最长回文子串

问题描述：

给出一个字符串（假设长度最长为1000），求出它的最长回文子串，你可以假定只有一个满足条件的最长回文串。

image.png

问题分析：

中心扩展法
如果是一个回文序列，那么以这个序列中心字符展开的前缀和后缀都是一样的，因此，我们可以枚举中心位置，然后再在这个位置上扩展。记录并且更新得到最长的回文长度。

示例代码：

class Solution {
public:
    /**
     * @param s input string
     * @return the longest palindromic substring
     */
    string longestPalindrome(string& s) {
        // Write your code here
         static int flag=0,legth=0;
 int c=0,max=0,i,j;
        int n=s.size();
        if(s.size()==0) return 0;
        for(i=0;i<n;i++)
        {
            for(j=0;i-j>=0&&(i+j)<n;j++)
            {
                if(s[i-j]!=s[i+j])
                    break;
                c=j*2+1;
                
            }
            if(c>max)
                {
                    max=c;
                    flag=i;
                    legth=j-1;
                }
            for(j=0;i-j>=0&&(i+j+1)<n;j++)
            {
                if(s[i-j]!=s[i+j+1])
                    break;
                c=j*2+2;
                
            }
            if(c>max)
            {
                    legth=j-1;
                    max=c;
                    flag=i;
            }
        }
        string res;
        for(int t=flag-legth;t<flag-legth+max;t++)
        {
            res.push_back(s[t]);
        }
        return res; 

    }
};