Manacher
Source：http://blog.wjin.org/posts/manacher.html
Declaration: this work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
Introduction
Question: 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, and there exists
one unique longest palindromic substring.
Analysis
It is very easy to get a dp solution with time complexity O(n^2).
// dp
// time complexity: O(n^2)
class Solution
{
public:
string longestPalindrome(string s)
{
int len = s.size();
if (len == 0)
return "";
vector<vector<bool>> dp(len, vector<bool>(len, false));
int subStrLen = 0, start = 0;
// dp[i][j] is true means s[i]...s[j] is palindrome
for (int col = 0; col < len; col++) {
for (int row = 0; row <= col; row++) {
if (row == col) { // single char is palindrome
dp[row][col] = true;
if (col - row + 1 > subStrLen) { // update the longest candidate
subStrLen = col - row + 1;
start = row;
}
} else if (s[row] == s[col]) {
// short circuit evaluation
// row + 1 == col means only have two letters, be careful
if (row + 1 == col || dp[row + 1][col - 1]) {
dp[row][col] = true;
if (col - row + 1 > subStrLen) { // update the longest candidate
subStrLen = col - row + 1;
start = row;
}
}
}
}
}
return s.substr(start, subStrLen);
}
};
As for palindrome, we can use its symmetry property to get a solution with only O(1) space complexity.
Traverse each charater in source string, and then expande it to two sides. We need to consider two situation when expande, odd and even. For example: aba and abba.
// time complexity: O(n^2)
// space complexity: O(1)
class Solution2
{
private:
string expandAroundCenter(string s, int c1, int c2)
{
int l = c1, r = c2;
int n = s.length();
while (l >= 0 && r <= n - 1 && s[l] == s[r]) {
l--;
r++;
}
return s.substr(l + 1, r - l - 1);
}
public:
string longestPalindrome(string s)
{
int n = s.length();
if (n == 0) return "";
string longest = s.substr(0, 1); // a single char itself is a palindrome
for (int i = 0; i < n - 1; i++) {
string p1 = expandAroundCenter(s, i, i); // odd
if (p1.length() > longest.length())
longest = p1;
string p2 = expandAroundCenter(s, i, i+1); // even
if (p2.length() > longest.length())
longest = p2;
}
return longest;
}
};
The most excellent solution might be Manacher's algorithm. Both time and space complexities are O(n). You can refere to
explaintation.
Of course, normally we can deal with string problems using suffix tree or suffix array to get O(n) time complexity.
So does this problem.
However, Manacher’s algorithm is simpler and easy to program compared with suffix tree or array.
// time complexity: O(n)
// space complexity: O(n)
class Solution3
{
private:
string preProcess(const string &s)
{
string ret("^"); // leading with special character
// insert delimeter
for (auto e : s) {
ret += '#';
ret += e;
}
ret += "#$"; // ending with $
return ret;
}
public:
string longestPalindrome(string s)
{
string t(preProcess(s));
int len = t.size();
vector<int> p(len, 0);
// calculate array p[i]
// p[i] means how long it can be extended to left or right to form a palindrome
// centered with i, character i itself is included in this length.
// i.e.: p[i] = 2, means p[i-1] p[i] p[i+1] is a palindrome
// p[i] - 1 is the palindroem length of original string
int id = 0, mx = 0;
for (int i = 1; i < len - 1; 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 (p[i] + i > mx) {
id = i;
mx = p[i] + i;
}
}
int maxLenId = 1;
for (int i = 1; i < len; i++) {
if (p[i] > p[maxLenId]) {
maxLenId = i;
}
}
// be careful with substr start point
return s.substr((maxLenId - p[maxLenId] ) / 2, p[maxLenId] - 1);
}
};