Rabin | Following program is a C ++ implementation of Rabin Karp Algorithm given in the CLRS book ; d is the number of characters in the input alphabet ; pat -> pattern txt -> text q -> A prime number ; hash value for pattern ; hash value for txt ; The value of h would be " pow ( d , ▁ M - 1 ) % q " ; Calculate the hash value of pattern and first window of text ; Slide the pattern over text one by one ; Check the hash values of current window of text and pattern . If the hash values match then only check for characters on by one ; Check for characters one by one ; if p == t and pat [ 0. . . M - 1 ] = txt [ i , i + 1 , ... i + M - 1 ] ; Calculate hash value for next window of text : Remove leading digit , add trailing digit ; We might get negative value of t , converting it to positive ; Driver code ; A prime number ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define d  256 NEW_LINE void search ( char pat [ ] , char txt [ ] , int q ) { int M = strlen ( pat ) ; int N = strlen ( txt ) ; int i , j ; int p = 0 ; int t = 0 ; int h = 1 ; for ( i = 0 ; i < M - 1 ; i ++ ) h = ( h * d ) % q ; for ( i = 0 ; i < M ; i ++ ) { p = ( d * p + pat [ i ] ) % q ; t = ( d * t + txt [ i ] ) % q ; } for ( i = 0 ; i <= N - M ; i ++ ) { if ( p == t ) { for ( j = 0 ; j < M ; j ++ ) { if ( txt [ i + j ] != pat [ j ] ) break ; } if ( j == M ) cout << " Pattern ▁ found ▁ at ▁ index ▁ " << i << endl ; } if ( i < N - M ) { t = ( d * ( t - txt [ i ] * h ) + txt [ i + M ] ) % q ; if ( t < 0 ) t = ( t + q ) ; } } } int main ( ) { char txt [ ] = " GEEKS ▁ FOR ▁ GEEKS " ; char pat [ ] = " GEEK " ; int q = 101 ; search ( pat , txt , q ) ; return 0 ; }