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.

（1）

class Solution {public:    string longestPalindrome(string s) {        if (s == "")            return "";        int l = s.length(), r[2100], maxID = 0, ID = 0, m = 0, i;        string ss;        ss.resize(l * 2 + 3);        ss[0] = '@';        ss[1] = '#';        for (i = 0; i < l; i++)        {            ss[i * 2 + 2] = s[i];            ss[i * 2 + 3] = '#';        }        ss[l * 2 + 2] = '\n';        l = l * 2 + 2;        for (i = 2; i < l; i++)        {            if (maxID > i)                r[i] = min(r[(ID << 1) - i], maxID - i);            else                r[i] = 1;            while (ss[i + r[i]] == ss[i - r[i]])                r[i]++;            if ((i + r[i] - 1) > maxID)            {                maxID = i + r[i] - 1;                ID = i;            }            if (r[i] > r[m])                m = i;        }        return s.substr((m-r[m])>>1, r[m]-1);    }};

 

（2）DP

string longestPalindrome_dp_opt_way(string s) {    int n = s.size();    if (n<=1) return s;    //Construct a matrix, and consdier matrix[j][i] as s[i] -> s[j] is Palindrome or not.    //                                 ------^^^^^^    //                                 NOTE: it's [j][i] not [i][j]    //Using vector  could cause the `Time Limit Error`    //So, use the native array    bool **matrix  = new bool* [n];    int start=0, len=0;    // Dynamic Programming    //   1) if i == j, then matrix[i][j] = true;    //   2) if i != j, then matrix[i][j] = (s[i]==s[j] && matrix[i-1][j+1])    for (int i=0; i
     
       3, then, check s[i]==s[j] && matrix[i-1][j+1]            if ( i==j || (s[j]==s[i] && (i-j<2 || matrix[i-1][j+1]) ) )  {                matrix[i][j] = true;                if (len < i-j+1){                    start = j;                    len = i-j+1;                }            }        }    }    for (int i=0; i