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.

本文利用动态规划的思想，如果s[i]==s[j]，那么s[i+1]==s[j-1]时，才是子串。时间复杂度O(n²)。时间：226ms

代码如下：

string longestPalindrome(string s) {    int n = s.size();    int substrBegin = 0;    int maxlen = 1;    bool state[1000][1000] = { false };    for (int i = 0; i < n; i++){        state[i][i] = true;        if (i < n - 1 && s[i] == s[i + 1]){            state[i][i + 1] = true;            substrBegin = i;            maxlen = 2;        }    }    for (int i = 3; i <= n ; i++){        for (int j = 0; j < n - i + 1; j++){            if (s[j] == s[j + i - 1] && state[j + 1] [j+i-2]== true){                state[j][j+i - 1] = true;                substrBegin = j;                maxlen = i;            }        }    }    return s.substr(substrBegin, maxlen);}

 之后学习了新的想法。通过对string添加‘#’使得回文子串只存在一种有轴的回文子串序列，然后利用动态规划的思想求解。时间复杂度：O(n)。时间：12ms

代码如下：

class Solution {public:    string longestPalindrome(string s) {        string s1;        s1.resize(2 * s.size() + 2);        s1[0] = '$';        s1[1] = '#';        for (int i = 0; i < s.size(); ++i) {            s1[(i + 1) << 1] = s[i];            s1[((i + 1) << 1) + 1] = '#';        }        vector
     
       p(s1.size(), 0);        int res = 0, id = 0, first = 0;        for (int i = 1; i < s1.size(); ++i) {            if (p[id] + id > i)                p[i] = min(p[2 * id - i], p[id] + id - i);            else                p[i] = 1;            while (s1[i + p[i]] == s1[i - p[i]])                ++p[i];            if (i + p[i] > id + p[id])                id = i;            res = max(res, p[i]);            if (res == p[i])                first = (i - res) / 2;        }        return s.substr(first,res-1);    }};