Longest Palindromic Substring 最长回文子字符串

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Difficulty:Medium

Example:

``````Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.
``````

Example:

``````Input: "cbbd"

Output: "bb"
``````

解法1: O(n^2)

``````class Solution {
public:
public:
string longestPalindrome(string s) {
int startIdx = 0, left = 0, right = 0, len = 0;
for (int i = 0; i < s.size() - 1; ++i) {
if (s[i] == s[i + 1])
{
left = i;
right = i+1;
searchPalindrome(s, left, right, startIdx, len);
}
left = right = i;
searchPalindrome(s, left, right, startIdx, len);
}
if (len==0)
len = s.size();
return s.substr(startIdx,len);
}
private:
void searchPalindrome(string s,int left,int right,int& startIdx,int& len)
{
int step = 1;
while ((left-step)>=0&&(right+step)<s.size())
{
if (s[left-step]!=s[right+step])
break;
++step;
}
int wide = right-left+2*step-1;
if (len < wide)
{
len = wide;
startIdx = left-step+1;
}
}
};
``````

解法2

``````class Solution {
public:
public:
string longestPalindrome(string s) {
int size = s.size();
//int dp[size][size]={0}编译不过的话试试int dp[size][size]; dp[size][size]={0};
int dp[size][size]={0},left=0,right=0,len=0;
for (int i=0;i<size;i++)
{
for (int j=0; j<i; j++) {
dp[j][i] = (s[i]==s[j] && (i-j<2||dp[j+1][i-1]));
if (dp[j][i] && len<i-j+1) {
len=i-j+1;
left=j;
right=i;
}
}
dp[i][i] = 1;
}
return s.substr(left,right-left+1);
}
};
``````

解法3 O(n) 马拉车Manacher

``````class Solution {
public:
string longestPalindrome(string s) {
string t ="\$#";
for (int i = 0; i < s.size(); ++i) {
t += s[i];
t += '#';
}
int p[t.size()] = {0}, id = 0, mx = 0, resId = 0, resMx = 0;
for (int i = 0; i < t.size(); ++i) {
p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;
while (t[i + p[i]] == t[i - p[i]]) ++p[i];
if (mx < i + p[i]) {
mx = i + p[i];
id = i;
}
if (resMx < p[i]) {
resMx = p[i];
resId = i;
}
}
return s.substr((resId - resMx) / 2, resMx - 1);
}
};
``````