题目：
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is , and there exists one unique longest palindromic substring.
解题思路：
1、简单思路：暴力破解法，时间复杂度O(n^3)，肯定通不过。
2、动态规划法：（一般含“最XX”等优化词义的题意味着都可以动态规划求解），时间复杂度O(n^2)，空间复杂度O(n^2)。
形如"abba", "abbba"这样的字符串，如果用dp[i][j]表示从下标i到j之间的子字符串所构成的回文子串的长度，则有：
dp[i][j] = dp[i+1][j-1] && s[i] == s[j]
初始化：
奇数个字符：dp[i][i] = 1; 偶数个字符：dp[i][i+1] = 1
//动态规划法
string LongestPalindromicStringDP(string str)
{
size_t n = str.size();
if (n == || n == )
return str;
//创建dp二维数组
//d[i][j] = dp[i+1][j-1] && s[i] == s[j]
bool **dp = new bool *[n];
for (size_t i = ; i < n; ++ i)
dp[i] = new bool[n]; int nLongestIndex = ; //最长回文子串的开始下标
int nMaxLen = ; //长度 for (size_t i = ; i < n; i ++)
for (size_t j = ; j < n; j ++)
dp[i][j] = false;
for (size_t i = ; i < n; ++ i)
dp[i][i] = true; //初始化一个字母 for (size_t i = ; i < n - ; ++ i) {
if (str[i] == str[i+]) {
dp[i][i+] = true; //初始化两个相同的字母"aa"
nLongestIndex = i;
nMaxLen = ;
}
}
//从长度3开始操作, (aba)ba, a(bab)a, ab(aba)
for (size_t len = ; len <= n; ++ len) {
for (size_t i = ; i < n-len+; ++ i) {
size_t j = i + len - ;
if (str[i] == str[j] && dp[i+][j-]){
dp[i][j] = true;
nLongestIndex = i;
nMaxLen = len;
}
}
} //释放dp
for (size_t i = ; i < n; ++ i)
delete []dp[i];
delete []dp; return str.substr(nLongestIndex, nMaxLen);
}
3、中心扩散法：时间复杂度O(n^2)，空间复杂度O(1)
顾名思义，从一个节点，分别向两边扩散，用两个指针分别向前向后遍历。
//中心扩散法
string LongestPalindromicString(string str)
{
size_t n = str.size();
if (n == || n == )
return str; size_t start = ;
size_t nMaxLen = ; for (size_t i = ; i < n; ++ i) {
size_t j = i, k = i; //分别从中心向两边扩散
while(k < n- && str[k] == str[k+])
k++; //有相同字母的情况："aaa"
while(j > && k < n- && str[j-] == str[k+]){
k++; //不同字母情况: "aba"
j--;
}
if(k-j+ > nMaxLen){
nMaxLen = k-j+;
start = j;
}
}
return str.substr(start, nMaxLen);
}
4、很明显，这两种方法时间复杂度还是太高了，还有一种算法叫Manacher，时间复杂度能够降为O(n)，空间复杂度也为O(n)，先记下，以后再做研究吧。