Rabin Karp String Search Algorithm
February 16, 2010 3 Comments
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.


Recent Activity