Three ways of finding the longest palindromi substring:
1.DP
2.Manacher's
These two algorithm are analyzed thoroughly in articles linked below:
http://leetcode.com/2011/11/longest-palindromic-substring-part-i.html
http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html
3.Search twice
This one is common and simple
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
My implementation:
1.DP solution: O(N2) time and O(N2) space (could be improved to use O(N) space)
string palindrome_DP(string s){ int maxStart = 0; //the smallest i among dp[i][j]s == true <span style="white-space:pre"> </span>int maxLen = 1; //maxLen = j - i + 1, is the max length among dp[i][j]s == true int n = s.size(); vector<vector<bool> > dp(n, vector<bool>(n, false)); //dp[i][j]: s[i..j] is a palindrome or not for(int i = n - 1; i >= 0; --i) for(int j = i; j < n; ++j) if(s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1])){ /*this equals (s[i] == s[j] && j - i < 2 || s[i] == s[j] && dp[i + 1][j - 1]) s[i] == s[j] && j - i < 2 is to check: when j == i, then s[i] == s[j], then dp[i][i] = true; when j == i + 1, if s[i] == s[i+1] then dp[i][i] = true, else false s[i] == s[j] && dp[i + 1][j - 1] is the dp method Notice that, s[i] == s[j] && j - i < 2 must be the first condition, or it'll cause memory read problem */ dp[i][j] = true; if(j - i + 1 > maxLen){ maxStart = i; maxLen = j - i + 1; } } return s.substr(maxStart, maxLen); }
2. Manacher’s algorithm: to find the longest palindrome substring in O(N) time and space
<pre name="code" class="cpp">//Manacher's algorithm: O(N) time and O(N) space string preprocessString(string s){ string t("#"); for(int i = 0; i < s.size(); ++i){ t += s[i]; t += "#"; } return t; } string finder(string s){ vector<int> p(s.size(), 1); int mx = 0, id = 0, len = 0, center = 0; for(int i = 0; i < s.size(); ++i){ if(mx > i) p[i] = min(p[2 * id - i], mx - i); //expand the panlindrome from the center while (i - p[i] >= 0 && i + p[i] < s.size() && s[i - p[i]] == s[i + p[i]]) p[i]++; //update info of reached panlindrome if(i + p[i] > mx){ mx = i + p[i]; id = i; } //record the info of the longest palindrome if(p[i] - 1 > len){ len = p[i] - 1; //len: the length of longest palindrome center = i; //center: the center of the longest palindrome } } //generate the longest palindrome string t; for(int i = len; i > 0; --i) t += s[center + p[center] - 2 * i]; return t; } string palindrome_Manacher(string s){ s = preprocessString(s); s = finder(s); return s;<span style="font-family: Arial, Helvetica, sans-serif;">}</span>
Time analysis: in the for loop, comparison begins at mx, and mx increases linearly, and elements between the old mx and the new mx wont be compared, so is O(N) method.
3.a simple solution: O(N2) time and O(1) spacego over the string twice to find the odd palindrome and even palindrome
string palindrome_Twice(string s){ int n = s.size(); if(n <= 1) return s; //n >= 2 int maxLen = 1; int maxStart = 0; for(int i = 1; i < n; ++i){ //find the longest even palindrome around i int low = i - 1; int high = i; while(low >= 0 && high < n && s[low] == s[high]){ if(high - low + 1 > maxLen){ maxLen = high - low + 1; maxStart = low; } low--; high++; } //find the longest odd palindrome around i low = i - 1; high = i + 1; while(low >= 0 && high < n && s[low] == s[high]){ if(high - low + 1 > maxLen){ maxLen = high - low + 1; maxStart = low; } low--; high++; } } return s.substr(maxStart, maxLen); }