Ronzii's Blog

Just your average geek's blog

Longest Palindrome in a string 2

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

Algorithm

  1. Set the current center to the first letter.
  2. Loop while the current center is valid:
    1. Expand to the left and right simultaneously until we find the largest palindrome around this center.
    2. If the current palindrome is bigger than the stored maximum one, store the current one as the maximum one.
    3. 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.
  3. 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;
}

March 27, 2012 Posted by | C++, Dynamic Programming | , , , , , | Leave a comment

Longest Palindrome in a string 1

This algorithm uses dynamic programming to compute the longest palindrome.

Algorithm

  1. Let hash[i][j] represent whether a string is a palindrome from index i to j
  2. hash[i][i] is always true i.e single characters
  3. 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;
}

March 26, 2012 Posted by | C++, Dynamic Programming | , , , , | Leave a comment