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[], maxID = , ID = , m = , i;
string ss;
ss.resize(l * + );
ss[] = '@';
ss[] = '#';
for (i = ; i < l; i++)
{
ss[i * + ] = s[i];
ss[i * + ] = '#';
}
ss[l * + ] = '\n';
l = l * + ;
for (i = ; i < l; i++)
{
if (maxID > i)
r[i] = min(r[(ID << ) - i], maxID - i);
else
r[i] = ;
while (ss[i + r[i]] == ss[i - r[i]])
r[i]++;
if ((i + r[i] - ) > maxID)
{
maxID = i + r[i] - ;
ID = i;
}
if (r[i] > r[m])
m = i;
}
return s.substr((m-r[m])>>, r[m]-);
}
};
（2）DP
string longestPalindrome_dp_opt_way(string s) {
int n = s.size();
if (n<=) 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=, len=;
// 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=; i<n; i++){
matrix[i] = new bool[i+];
memset(matrix[i], false, (i+)*sizeof(bool));
matrix[i][i]=true;
for (int j=; j<i; j++){
// The following if statement can be broken to
// 1) j==i, matrix[i][j] = true
// 2) the length from j to i is 2 or 3, then, check s[i] == s[j]
// 3) the length from j to i > 3, then, check s[i]==s[j] && matrix[i-1][j+1]
if ( i==j || (s[j]==s[i] && (i-j< || matrix[i-][j+]) ) ) {
matrix[i][j] = true;
if (len < i-j+){
start = j;
len = i-j+;
}
}
}
}
for (int i=; i<n; i++) {
delete [] matrix[i];
}
delete [] matrix;
return s.substr(start, len);
}