非常经典的题目，求字符串中的最长回文子串。
（1）最朴素的解法 ---暴力 复杂度O(N³)
这也是最easy想到的方法。最外层循环枚举起点i，第二层循环从i+1開始向后枚举，第三层推断是不是回文串。最后取最长子串的返回。
代码比較简单，这里没有列出。
（2）中心扩展法。复杂度O(N²)
枚举每个字符作为中心点向左右扩展。
可是这里要注意，对于每一次扩展要分奇偶两种情况。
否则可能会漏掉情况。
一发现不满足的情况立即break进行下一个中心字符的推断，代码例如以下：
class Solution {
public:
string longestPalindrome(string s) {
string ans;
int len=s.length();
int maxLength=-1,CurLen,Sbegin;
for(int i=0;i<len;i++)
{
int left=i-1,right=i+1;
while(left>=0&&right<len&&s[left]==s[right])//奇数情况
{
CurLen=right-left+1;
if(CurLen>maxLength)
{
maxLength=CurLen;
Sbegin=left;
}
left--,right++;
}
left=i,right=i+1;
while(left>=0&&right<len&&s[left]==s[right])//偶数情况
{
CurLen=right-left+1;
if(CurLen>maxLength)
{
maxLength=CurLen;
Sbegin=left;
}
left--,right++;
}
}
ans=s.substr(Sbegin,maxLength);
return ans;
}
};（3）Manacher算法。复杂度仅仅有O(n)
详细算法介绍：点击打开链接
附上静止的代码：
class Solution {
public:
string preProcess(string s) {
int n = s.length();
if (n == 0) return "^$";
string ret = "^";
for (int i = 0; i < n; i++)
ret += "#" + s.substr(i, 1);
ret += "#$";
return ret;
}
string longestPalindrome(string s) {
string T = preProcess(s);
int n = T.length();
int *P = new int[n];
int C = 0, R = 0;
for (int i = 1; i < n-1; i++) {
int i_mirror = 2*C-i; // equals to i' = C - (i-C)
P[i] = (R > i) ? min(R-i, P[i_mirror]) : 0;
// Attempt to expand palindrome centered at i
while (T[i + 1 + P[i]] == T[i - 1 - P[i]])
P[i]++;
// If palindrome centered at i expand past R,
// adjust center based on expanded palindrome.
if (i + P[i] > R) {
C = i;
R = i + P[i];
}
}
// Find the maximum element in P.
int maxLen = 0;
int centerIndex = 0;
for (int i = 1; i < n-1; i++) {
if (P[i] > maxLen) {
maxLen = P[i];
centerIndex = i;
}
}
delete[] P;
return s.substr((centerIndex - 1 - maxLen)/2, maxLen);
}
};（4）后缀树的解法，待补充