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

Prime Subsets

Given a set of numbers [1-N] . Find the number of subsets such that the sum of numbers in the subset is a prime number.
Algorithm

  1. Generate prime numbers using sieve of eratosthenes (O(n^2))
  2. Generate all subsets using 0-1 Knapsack i.e this helps determine the number of ways it is possible get the value i, input ranging from 1 to n. The general complexity of 0-1 Knapsack is O(nK) where K is the sum of all elements in the vector. Since there are numbers ranging from 1 to n i.e sum is n(n-1)/2. The overall complexity becomes O(n^3)
  3. Iterate all subsets which are prime. O(K)
#include <iostream>
#include <bitset>
#include <vector>
#include <algorithm>
#define SIZE 1000
#define MAX (int)(SIZE-3)/2
using namespace std;
unsigned long long primes[MAX+1];
bitset<MAX+1> bset;
void setPrimes()
{
    unsigned long long i,j;
    for(i=0; i*i<=SIZE; i++)
        if(!bset.test(i))
            for(j=i+1; (2*j+1)*(2*i+3)<=SIZE; j++)
                bset.set(((2*j+1)*(2*i+3)-3)/2);
    primes[0]=2;
    for(i=1,j=0; j<MAX+1; j++)
        if(!bset.test(j))
            primes[i++]=2*j+3;
}
int knapsack(int n)
{
    vector<int> v;
    for(int i=1; i<=n; i++)
        v.push_back(i);
    int sum = accumulate(v.begin(),v.end(),0);
    int *s = new int[sum];
    for(int i=0; i<sum; i++) s[i] = 0;
    s[0] = 1;
    for(int i=0; i<v.size(); i++)
    {
        for(int j = sum-v[i]; j>=0; j--)
        {
            if(s[j])
            {
                s[j+v[i]]+=1;
            }
        }
    }
    int total = 0;
    for(int i=0; i<n; i++)
    {
        cout<<primes[i]<<" "<<s[primes[i]]<<endl;
        total+=s[primes[i]];
    }
    return total;
}
int main()
{
    setPrimes();
    cout<<knapsack(10);
    return 0;
}

March 26, 2012 Posted by | C++, Dynamic Programming | , , , , , | 2 Comments

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

Project Euler Problem 18,67

#include <iostream>
using namespace std;
int main ()
{
    int row;
    int array [102] [102];
    cin >> row;
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j <= i; j++)
            cin >> array [i] [j];
    }
    for( int i = row - 2; i >= 0; i--)
    {
        for(int j = 0; j <= i; j++ )
        {
            array[i][j]+=max( array[i + 1][j],array[i + 1][j + 1]);
        }
    }
    cout<<array[0][0];
    return 0;
}

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

Longest Increasing Subsequence 2

#include <iostream>
#include <vector>
using namespace std;
/* Finds longest strictly increasing subsequence. O(n log k) algorithm. */
void find_lis(vector<int> &a, vector<int> &b)
{
    vector<int> p(a.size());
    int u,v;
    if(a.empty()) return;
    b.push_back(0);
    for(int i=1; i<a.size(); i++)
    {
        // Add element to LIS
        if(a[b.back()]<a[i])
        {
            p[i] = b.back();
            b.push_back(i);
            continue;
        }
        // Binary Search in current LIS an index u which is an element just larger than a[i]
        for(u=0,v=b.size()-1; u<v;)
        {
            int c = (u+v)/2;
            if(a[b[c]]<a[i]) u = c+1;
            else v = c;
        }
        // If u is found, then update
        if(a[i]<a[b[u]])
        {
            if (u > 0) p[i] = b[u-1];
            b[u] = i;
        }
    }
    for (u = b.size(), v = b.back(); u--; v = p[v]) b[u] = v;
}
int main()
{
    int a[] = {10,22,11,2,4,91,17,18,21,41,8};
    vector<int> seq(a, a+sizeof(a)/sizeof(a[0]));
    vector<int> lis;
    find_lis(seq, lis);
    for (int i = 0; i < lis.size(); i++)
        cout<<seq[lis[i]]<<" ";
    return 0;
}

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

Binomial Coefficients

class Binomial
{
public:
    Binomial(int Max)
    {
        max = Max+1;
        table = new unsigned int * [max]();
        for (int i=0; i < max; i++)
        {
            table[i] = new unsigned int[max]();

            for (int j = 0; j < max; j++)
            {
                table[i][j] = 0;
            }
        }
    }

    ~Binomial()
    {
        for (int i =0; i < max; i++)
        {
            delete table[i];
        }
        delete table;
    }

    unsigned int Choose(unsigned int n, unsigned int k);

private:
    bool Contains(unsigned int n, unsigned int k);

    int max;
    unsigned int **table;
};
unsigned int Binomial::Choose(unsigned int n, unsigned int k)
{
    if (n < k) return 0;
    if (k == 0 || n==1 ) return 1;
    if (n==2 && k==1) return 2;
    if (n==2 && k==2) return 1;
    if (n==k) return 1;


    if (Contains(n,k))
    {
        return table[n][k];
    }
    table[n][k] = Choose(n-1,k) + Choose(n-1,k-1);
    return table[n][k];
}

bool Binomial::Contains(unsigned int n, unsigned int k)
{
    if (table[n][k] == 0)
    {
        return false;
    }
    return true;
}

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

Permute Dictionary

Let’s say you have a phrase without any spaces – eg. “thisisawesome”. Given a dictionary, how would you add spaces in this string?
This algorithm is similar to how matrix multiplication works. (O(n^3) solution)

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
const string dictionary[] = { "this", "i","it","was", "saw", "is", "awesome", "some", "a" };
const int dictionary_size = sizeof(dictionary)/sizeof(dictionary[0]);
class PermuteDictionary
{
    vector < vector<int> > path;
    vector < vector<bool> > word,map;
    string s;
    int n;
    bool search(string t)
    {
        if(find(dictionary,dictionary+dictionary_size,t)!= dictionary+dictionary_size)
            return true;
        return false;
    }
public:
    PermuteDictionary(string input)
    {
        s = input;
        n = s.length();
        path.resize(n,vector<int> (n, -1) ) ;
        word.resize(n,vector<bool> (n, 0) ) ;
        map.resize(n,vector<bool> (n, 0) ) ;
        createMap();
        permute();
        getWords();
    }
    void createMap()
    {
        for(int i=0; i<n; i++)
        {
            for(int j=i; j<n; j++)
            {
                map[i][j] = search(s.substr(i,j-i+1));
                if(map[i][j])
                    path[i][j] = i;
            }
        }
        for(int i = 0; i < n; i++)
            word[i][i] = map[i][i];
    }
    void permute()
    {
        for(int len=2; len<=n; len++)
        {
            for(int i=0; i<=n-len; i++)
            {
                int j = i + len-1;
                word[i][j] = map[i][j] ;
                for(int k=i; k<j; k++)
                {
                    if(word[i][k] && word[k+1][j])
                    {
                        word[i][j] = true;
                        path[i][j] = k;
                    }
                }
            }
        }
    }
    void getWords()
    {
        if ( word[0][n-1] == false )
            cout<<"No parition is possible"<<endl;
        else if ( map[0][n-1] )
            cout<<s<<endl;
        else
            printSpacedWords(0,n-1);
    }
    void printSpacedWords(int start, int end)
    {
        if(end==0) return;
        int k = path[start][end];
        if(map[start][k])
            cout<<s.substr(start, k-start+1)<<" ";
        else
            printSpacedWords(start,k);
        if(map[k+1][end])
            cout<<s.substr(k+1,end-k)<<" ";
        else
            printSpacedWords(k+1,end);
    }
};
int main()
{
    string s = "isawthisitwasawesome";
    PermuteDictionary p(s);
    return 0;
}

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