## Longest Palindrome in a string 2

We use Manachers Algorithm instead of the dynamic programming algorithm which runs in O(n^2)

**Algorithm**

- Set the current center to the first letter.
- Loop while the current center is valid:
- Expand to the left and right simultaneously until we find the largest palindrome around this center.
- If the current palindrome is bigger than the stored maximum one, store the current one as the maximum one.
- Set the space following the current palindrome as the current center unless the two letters immediately surrounding it are different, in which case set the last letter of the current palindrome as the current center.

- Return the stored maximum palindrome.

Overall complexity is O(n)

Source

#include <iostream> #include <cstring> using namespace std; class Manachers { string S,T; int n; // P[i] stands for the longest palindrome centered at location i. int *P; // 1221 becomes ^#1#2#2#1#$ 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; } public: Manachers(string s) { S = s; T = preProcess(s); n = T.length(); P = new int[n]; } string longestPalindrome() { int C=0,R=0; for(int i=1; i<n-1; i++) { // Leverage previous computed P[i] when we calculate a P[x] where x>i P[i] = (R>i)?min(R-i,P[2*C-i]):0; // For a particular position, we check its left and right while(T[i+1+P[i]]==T[i-1-P[i]]) { P[i]++; } // Expand center when a larger palindrome is found if(i+P[i]>R) { C = i; R = i+P[i]; } } int max_length = 0; int centerIndex = 0; for (int i = 1; i < n-1; i++) { if (P[i] > max_length) { max_length = P[i]; centerIndex = i; } } delete[] P; return S.substr((centerIndex - 1 - max_length)/2, max_length); } }; int main() { Manachers m("dabbaracecarabbac"); cout<<m.longestPalindrome(); return 0; }

Advertisements

## Longest Palindrome in a string 1

This algorithm uses dynamic programming to compute the longest palindrome.

**Algorithm**

- Let hash[i][j] represent whether a string is a palindrome from index i to j
- hash[i][i] is always true i.e single characters
- We now iterate over all possible lengths in the string and set hash[i][j] true only when (s[i]==s[j] && hash[i+1][j-1]) is true

#include <iostream> #include <cstring> using namespace std; int dynamicLongestPalindrome(string s) { int n = s.length(); int longestBegin = 0, maxLen = 0; bool hash[n+1][n+1]; memset(hash,false,sizeof(hash)); for(int i=0; i<n; i++) { hash[i][i] = true; } for(int i=0; i<n; i++) { if(s[i]==s[i+1]) { hash[i][i+1] = true; longestBegin = i; maxLen = 2; } } for(int len=3; len<=n; len++) { for(int i=0; i<n-len+1; i++) { int j = i+len-1; if(s[i]==s[j] && hash[i+1][j-1]) { hash[i][j] = true; longestBegin = i; maxLen = len; } } } for(int i=longestBegin; i<longestBegin+maxLen; i++) { cout<<s[i]; } cout<<endl; return maxLen; } int main() { cout<<dynamicLongestPalindrome("babcbabcbaccba"); return 0; }

Advertisements