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

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

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

Circular Track Problem

You have a circular track containing fuel pits at irregular intervals. The total amount of fuel available from all the pits together is just sufficient to travel round the track and finish where you started. Given the the circuit perimeter, list of each fuel pit location and the amount of fuel they contain, find the optimal start point on the track such that you never run out of fuel and complete circuit.

#include <iostream>
using namespace std;
int circularTrackIndex(int dist[], int refill[],int n)
{
    if(n==0) return -1;
    int fuel = 0, start=0;
    for(int i=0; i<n; i++)
    {
        fuel+=refill[i]-dist[i];
        if(fuel<0)
        {
            start = i+1;
            fuel = 0;
        }
    }
    return start;
}
int main()
{
    // dist[i] is distance between pit i and i +1
    int dist[] = { 3, 10, 2, 4, 6, 9};
    // refill[i] is fuel available at pit[i]
    int refill[] = { 3, 4, 6, 3, 7, 11};
    int n = sizeof(refill)/sizeof(refill[0]);
    cout<<circularTrackIndex(dist,refill,n);
    return 0;
}

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

Generalized Summation

Write an algorithm to find out how many different summations you can compute using numbers range from 1 to 1000. 2 constraints
1) Each valid sum must be less than 10000
2) A number can only be used once for a sum
example:
1+2+300 < 10000 is valid
1+2+300+400 < 10000 is valid
1+2+2 is not valid (2 appear twice)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int summation(vector<int> v,int maxSumAllowed)
{
    int n = v.size();
    int sum = accumulate(v.begin(),v.end(),0);
    int *s = new int[sum+1];
    s[0] = 1;
    for(int i=1; i<=sum; i++) s[i] = 0;
    int R = 0;
    for(int i=0; i<n; i++)
    {
        for(int j = R; j>=0; j--)
        {
            if(s[j] && j+v[i]<maxSumAllowed)
            {
                s[j+v[i]]+=1;
            }
        }
        R = max(sum/2,R+s[i]);
    }
    int result = 0;
    for(int i=0; i<=maxSumAllowed; i++) result+=s[i];
    return result;
}
int main()
{
    int n = 4;
    vector<int> v;
    for(int i=1; i<=n; i++)
    {
        v.push_back(i);
    }
    cout<<summation(v,4);
    return 0;
}

 

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

Generalized Voting

Design an algorithm that, given a list of n elements in an array, finds all the elements that appear more than n/3 times in the list.
The algorithm should run in linear time. (n >=0 )

You are expected to use comparisons and achieve linear time. No hashing/excessive space/ and don’t use standard linear time deterministic selection algo

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
void generalizedVoting(vector<int> v, int m)
{
    int n = v.size();
    unordered_map<int,int> h;
    unordered_map<int,int>::iterator iter;
    // Treat numbers as blocks of size m similar to the game tetris
    // There are n/m blocks of size m
    for(int i=0; i<n; i++)
    {
        iter = h.find(v[i]);
        if(iter!=h.end())
        {
            iter->second++;
        }
        else
            h.insert(pair<int,int>(v[i],1));
        if(h.size()==m)
        {
            unordered_map<int,int>::iterator iter = h.begin();
            while(iter!=h.end())
            {
                --(*iter).second;
                if((*iter).second == 0)
                    h.erase(iter++);
                else
                    iter++;
            }
        }
    }
    // Reset values in unordered map
    for(iter = h.begin(); iter!=h.end(); iter++)
    {
        iter->second = 0;
    }
    // find exact count of numbers present in unordered map
    for(int i=0; i<n; i++)
    {
        iter = h.find(v[i]);
        if(iter!=h.end())
            iter->second++;
    }
    // Remove numbers with frequency less than equal to n/m
    for(iter = h.begin(); iter!=h.end(); iter++)
    {
        if(iter->second<=n/m)
            h.erase(iter);
    }
    for(iter = h.begin(); iter!=h.end(); iter++)
    {
        cout<<iter->first<<" ";
    }
}
int main()
{
    //int arr[] = {5,6,7,8,10,10,10,10,10,10,4,4,4,4,4,1,1,1,1};
    int arr[] = {4,3,3,2,1,2,3,4,4,7};
    //int arr[] = {5,6,7,8,10,4,4,4,4,1,1,1};
    int n = sizeof(arr)/sizeof(arr[0]);
    vector<int> v(arr,arr+n);
    int k = 4;
    generalizedVoting(v,k);
    return 0;
}

March 20, 2012 Posted by | C++, Data Structures | , , , , , | Leave a comment

Balanced Partition Problem

Follow the logic of Balanced Partition Problem from here

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <cmath>
using namespace std;
int BalancedPartition(vector<int> v)
{
    int n = v.size();
    int sum = accumulate(v.begin(),v.end(),0);
    int max_sum=sum/2,diff=INT_MAX;
    int *s = new int[sum+1];
    s[0] = 1;
    for(int i=1; i<=sum; i++) s[i] = 0;
    for(int i=0; i<n; i++)
    {
        for(int j = sum; j>=0; j--)
        {
            if(s[j])
            {
                s[j+v[i]]+=1;
            }
        }
    }
    for(int j = sum/2; j>=1; j--)
        if(s[j])
        {
            return abs(sum-2*j);
        }
}
int main()
{
    int value[] = {12,5,7,3};
    int n = sizeof(value)/sizeof(value[0]);
    vector<int> v(value,value+n);
    cout<<BalancedPartition(v);
    return 0;
}

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