5. Longest Palindromic Substring

Description:

https://leetcode.com/problems/longest-palindromic-substring/#/description

Boundary:

No

Algorithm:

1. DP (Easy to understand, but slow. Time complexity O(n^2) )
2. Manacher (fast, time complexity O(n)) http://www.cnblogs.com/grandyang/p/4475985.html

Code:

DP:

class Solution {
public:
string longestPalindrome(string s) {
int dp[s.size()][s.size()];
int left = 0,right = 0, len = 0;

for (int i = 0; i < s.size();i++)
{
for (int j = 0; j < i; j++)
{
dp[j][i] = s[i] == s[j] && (i-j < 2 || dp[j + 1][i – 1] == 1);
if(dp[j][i] && len < i – j + 1)
{
left = j;
right = i;
len = i – j + 1;
}
}
dp[i][i] = 1;
}
return s.substr(left, right – left + 1);
}
};

 

Manacher:

class Solution {
public:
// Transform S into T.
// For example, S = “abba”, T = “^#a#b#b#a#$”.
// ^ and $ signs are sentinels appended to each end to avoid bounds checking
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);
const int n = T.length();
// 以T[i] 为中心，向左/右扩张的长度，不包含T[i] 自己，
// 因此P[i] 是源字符串中回文串的长度
vector<int> P = vector<int>(n,-1);
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 max_len = 0;
int center_index = 0;
for (int i = 1; i < n – 1; i++) {
if (P[i] > max_len) {
max_len = P[i];
center_index = i;
}
}
return s.substr((center_index – 1 – max_len) / 2, max_len);
}
};

 

Tips:

1. Get a substring of a string: s.substr(start, LengthOfString);