Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

这道题来源于leetcode，有很多种方法可以解决，最直接的Brute Force 时间复杂度是O(n^3)的，Dynamic Programming时间复杂度是O(n^2)，但空间复杂度也是O(n^2)的，这儿给出一种Time:O(n^2)，Space:O(1)的方法。

关键点：回文字符串是中心对称的

从中心开始向两侧扩展，代码如下：

class Solution {
public:
    string longestPalindrome(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(s.empty())
            return s;
        int maxl=0,maxr=0,size=1;
        for(int i=0;i<s.length();i++)
        {
            int l=i-1,r=i+1,il=i,ir=i+1;
            while(l>=0 && r<s.length() && s[l]==s[r])
                l--,r++;
            while(il>=0 && ir<s.length() && s[il]==s[ir])
                il--,ir++;
            if(r-l<ir-il)
                l=il,r=ir;
            if(r-l-1>size)
                maxl=l+1,maxr=r-1,size=r-l-1;
        }
        return s.substr(maxl,size);
    }
};

该问题还有一种Time:O(n)，Space:O(n)的算法，Manacher's Algorithm