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;
}
Advertisements

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

Longest Repeated Substring

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
void preCompute(string input[],string s)
{
    int n = s.length();
    for(int i=0; i<n; i++)
        input[i] = s.substr(i,n);
}
 // return the longest common prefix of first and second
string LongestCommonSubString(string first,string second)
{
    int n = min(first.length(),second.length());
    for(int i=0; i<n; i++)
        if(first[i]!=second[i])
            return first.substr(0,i);
    return first.substr(0,n);
}
// return the longest repeated string in s
string lrs(string s)
{
    int n = s.length();
    string input[n];
    // find all suffix's of s
    preCompute(input,s);
    // sort all suffix's
    sort(input, input+n);
    string lrs = "";
    // find longest repeated substring by comparing adjacent sorted suffixes
    for(int i=0; i<n-1; i++)
    {
        string x = LongestCommonSubString(input[i],input[i+1]);
        if(x.length()>lrs.length())
        {
            lrs = x;
        }
    }
    return lrs;
}
int main()
{
    string input[2] = {"banana","missisipi"};
    for(int i=0;i<2;i++)
        cout<<lrs(input[i])<<endl;
    return 0;
}

March 8, 2012 Posted by | C++ | , , , , , , | Leave a comment

Suffix Tree

#include <cstdio>
#include <iostream>
#include <cstring>
#define ALPHABET_SIZE 26
#define MAX_LENGTH 10000
using namespace std;
struct trie_node
{
    int value;
    struct trie_node* children[ALPHABET_SIZE];
};
typedef struct trie_node Node;
struct trie
{
    int count;
    Node* root;
};
typedef struct trie Trie;
int getIndex(char s)
{
    return s - 'a';
}
Node* createNode()
{
    Node *temp = new Node();
    temp->value = 0;
    for(int i=0; i<ALPHABET_SIZE; i++)
    {
        temp->children[i]= NULL;
    }
    return temp;
}
void initializeTrie(Trie* &t)
{
    t->count = 0;
    t->root = createNode();
}
void insert(Trie* &t, char s[])
{
    int length = strlen(s);
    Node* current = t->root;
    t->count++;
    int level;
    for(level = 0; level < length; level++)
    {
        int child_index = getIndex(s[level]);
        if(current->children[child_index])
        {
            current = current->children[child_index];
        }
        else
        {
            current->children[child_index] = createNode();
            current = current->children[child_index];
        }
    }
    current->value = t->count;
}
bool search(Trie* &t, char s[])
{
    int length = strlen(s);
    Node* current = t->root;
    int level;
    for(level = 0; level < length; level++)
    {
        int child_index = getIndex(s[level]);
        if(!current->children[child_index])
        {
            return false;
        }
        current = current->children[child_index];
    }
    if(current && current->value)
    {
        return true;
    }
    return false;
}
void buildSuffixTree(Trie* &root, char s[])
{
    int length = strlen(s),i,j;
    char input[length][MAX_LENGTH];
    for(i=0; i<length; i++)
    {
        for(j=0; s[i+j]; j++)
        {
            input[i][j] = s[i+j];
        }
        input[i][j] = '\0';
    }
    for(i=0; i<length-1; i++)
        insert(root, input[i]);
    for(i=0; i<length-1; i++)
        cout<<search(root, input[i])<<endl;
}
int main()
{
    Trie* root = new Trie;
    initializeTrie(root);
    buildSuffixTree(root,"banana");
    return 0;
}

March 6, 2012 Posted by | C++ | , , , , | 2 Comments

Longest Common Substring

#include <iostream>
#include <cstring>
using namespace std;
int LongestCommonSubString(string first,string second)
{
    int n1 = first.length(), n2 = second.length(),max=0;
    if(n1==0||n2==0) return 0;
    if(n1<n2) swap(first,second);
    int *current = new int[n2];
    int *previous = new int[n2];
    for(int i=0; i<n1; i++)
    {
        for(int j=0; j<n2; j++)
        {
            if(first[i]!=second[j])
                current[j] = 0;
            else if(i==0||j==0)
                current[j] = 1;
            else
                current[j] = previous[j-1] + 1;

            if(max<current[j])
                max = current[j];
        }
        swap(previous,current);
    }
    delete [] previous;
    delete [] current;
    return max;
}
int main()
{
    cout<<LongestCommonSubString("handler","sandollar");
    return 0;
}

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

Rabin Karp Algorithm

#include<cstdio>
#include<iostream>
#include<cstring>
#define d 256
using namespace std;
void search(string pattern, string text, int prime)
{
    int M = pattern.length();
    int N = text.length();
    int h = 1;
    //The value of h would be "pow(d, M-1)%prime"
    for(int i=0; i<M-1; i++)
    {
        h = (h*d)%prime;
    }
    int p = 0,t = 0,i,j;
    // Calculate the hash value of pattern and first window of text
    for(i=0; i<M; i++)
    {
        p = (d*p+pattern[i])%prime;
        t = (d*t+text[i])%prime;
    }
    cout<<p<<endl;
    for(i=0; i<=(N-M); i++)
    {
        if ( p == t )
        {
            // Chaeck the hash values of current window of text and pattern
            // If the hash values match then only check for characters on by one
            for (j = 0; j < M; j++)
            {
                if (text[i+j] != pattern[j])
                    break;
            }
            if (j == M)  // if p == t and pat[0...M-1] = txt[i, i+1, ...i+M-1]
            {
                printf("Pattern found at index %d \n", i);
            }
        }
        // Calulate hash value for next window of text: Remove leading digit,
        // add trailing digit
        if(i<(N-M))
        {
            t = ((t - text[i]*h)*d + text[i+M])%prime;
            if(t<0)
            {
                t = t+prime;
            }
        }
    }
}
int main()
{
    string txt = "abacadabrabrarabraabracadcabracadabrabrabracad";
    string pat = "rabrabracad";
    int q = 103;  // A prime number
    search(pat, txt, q);
    return 0;
}

February 26, 2012 Posted by | C++ | , , , , , | Leave a comment