# 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.

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

U can refer the wikipedia page for more details. You might learn a bit more 🙂

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