Rabin Karp String Search Algorithm

I came across the Rabin–Karp string search algorithm when I was looking for a method to implement strstr as a C program. The obvious brute-force method was a waste, so I found the Rabin-Karp, Knuth-Morris-Pratt Algorithm and Boyer-Moore Algorithm . The KMP is hectic to understand and code as well but Boyer-Moore is very practical and can be coded quickly. I had less time so coded only the Rabin-Karp Algorithm.
The code which I had made.

#include<iostream>
#include<string>
#include<vector>
#include<cmath>

using namespace std;

int main()
{
	string T, P;
	cin >> T;
	cin >> P;
	long long int PRIME = atoll("10002949999");
	int l_T = T.length(), l_P = P.length(), t=0, h = 1, d = 26, H = 0;
	for (int i=1; i < l_P; i++)
		h = (h * d) % PRIME;
	for (int i=0;i<l_P;i++)
	{
		H = ( (d*H)  + P[i] - 'a')%PRIME ;
		t = ( (d*t)  + T[i] - 'a')%PRIME ;
	}
	for (int i = 0, j = l_T - l_P - 1 ; i < j ; i++)
	{
		if (t == H)
		{
			int state = 1;
			for (int k = 0 ;k < l_P; k++)
				if (T[i+k] != P[k])
				{
					state = -1;
					break;
				}
			if (state == 1 )
			{
				cout << " Match found at index : " << i << "\n";
			}
		}
		else
		{
			t =  ( (d * (t - h*(T[i]-'a')) + T[i+l_P] - 'a')%PRIME );
		}
	}
	return 0;
}

The algorithm can be found on wiki, I had used the pseudo-code from CLRS.

Advertisements

About Avi Dullu
Jaako rakhe saiyan, maar sake na koi!

3 Responses to Rabin Karp String Search Algorithm

  1. Algoseekar says:

    @what d vale of prime ..i mean what value we have to choose of that prime

  2. fred says:

    Thanks a ton 🙂 really helped to understand the algorithm.i was struggling since i dint have a fair knowledge of hash functions.thanks 🙂

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: