Longest common substring problem using Suffix Array

Problem:
find the longest string (or strings) that is a substring (or are substrings) of two or more strings.

Algorithm:

SuffixArray

LCPArray

How to use

Enjoy!

Cyclic Buffer

Sharing the cyclic buffer code here. I used this for the cyclic pattern.

template<class T>
class CyclicBuffer
{
    int tail_;
    int head_;
    int size_;
    T *data_;
    public:
    CyclicBuffer(int size=10):tail_(0),head_(0),size_(size),data_(new T[size_]){}
    ~CyclicBuffer(){ delete [] data_;}

    void push_back(T t)
    {
        if(tail_ == size_-1)
            tail_ =head_;

        data_[tail_++] = t;
    }
    T &operator[] (int index)
    {
        if (index < size_)
            return data_[index];
        else
            throw std::out_of_range("out of range");
    }

};


int main()
{
    CyclicBuffer<int> cb(3);
    cb.push_back(1);
    cb.push_back(2);
    cb.push_back(3);
    cout << cb[1] << endl;
    cb.push_back(4);

    cout << cb[1] << endl;
    




    return 0;
}

Rabin – Karp string matcher.

#include<iostream>
#include<vector>
using namespace std;


int mod(int n,int q)
{
	cout << "n=" << n << endl;
	while(n <0)
		n = n + q;
	return n%q;
}
//d - radix
// q - modulus
template<class T>
int RabinKarpStringMatcher(vector<T> &Text,vector<T> &Pattern,int d,int q)
{
	int n = Text.size();
	int m = Pattern.size();
	int h = int( pow(float(d),float(m-1))) % q;
	int p = 0;
	int t_0 = 0;
	for(int i =0;i<m;i++)
	{
		p = (d*p + Pattern[i]) % q;
		t_0 = (d*t_0 + Text[i])%q;
	}
	
	cout << "p=" << p << endl;
	cout << "t_0=" << t_0 << endl;
	int *t= new int[n-m];
	memset(t,0,n-m-1);
	t[0] = t_0;
	for(int s =0; s<(n-m);s++)
	{
		cout << "s=" << s << endl;
		cout << "p = " << p << " t[ = " << s << "]=" << t[s] << endl;
		if (p == t[s])
		{
			cout << "spurious or valid shift found\n";
			//check for valid shift
			bool isValidShift = true;
			for(int i = 0;i<m;i++)
			{
				if(Text[s+i] == Pattern[i])
					continue;
				else
				{
					isValidShift = false;
					break;
				}

			}
			if (isValidShift)
				return s;
		}
		if( s == n-m-1)
			break;
		if(s < n-m)
			t[s+1] = mod(d*(t[s]-Text[s]*h) + Text[s+m],q);

	}


	return -1;
}

int main()
{
	vector<int> T,P;
	T.push_back(3);
	T.push_back(4);
	T.push_back(1);
	T.push_back(6);
	T.push_back(7);
	T.push_back(7);

	P.push_back(6);
	P.push_back(7);

	cout << RabinKarpStringMatcher(T,P,10,13);

	system("PAUSE");

	return 0;
}

Average case analysis of Binary Tree Traversal

Tree Traversal

I know it looks pretty straightforward. but how can we prove this?

where is the # of nodes at one of the subtree and at the other subtree.

Analysis of Partial Sorting

Problem: Rearrange a given array with n elements, so that m places contain the m smallest elements in ascending order.

Using substitution method;

PARTIAL SORTING

Problem: Rearrange a given array with n elements, so that m places contain the m smallest elements in ascending order.

Solution 1: Make a heap with n given elements in linear time and then perform m successive extraction of the minimum element.

Solution 2: using QuickSort method approach.

C++ STL provides a function for partial sorting.

#include<algorithm>

vector vec;
vec.push_back(10);
vec.push_back(20);
vec.push_back(90);
vec.push_back(30);
vec.push_back(43);
vec.push_back(3);
vec.push_back(13);
vec.push_back(4);
vec.push_back(40);

//using operator &lt; here.
partial_sort(vec.begin(),vec.begin() + 2; vec.end());

Analysis of worst case RANDOMIZED-SELECT

Worst case:
It happens when we always partition around largest element i.e. RANDOMIZE-PARTITION returns the index of largest element.
e.g.

hence