Rabin | Following program is a Java 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
public class Main { public final static int d = 256 ; static void search ( String pat , String txt , int q ) { int M = pat . length ( ) ; int N = txt . length ( ) ; 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 . charAt ( i ) ) % q ; t = ( d * t + txt . charAt ( i ) ) % q ; } for ( i = 0 ; i <= N - M ; i ++ ) { if ( p == t ) { for ( j = 0 ; j < M ; j ++ ) { if ( txt . charAt ( i + j ) != pat . charAt ( j ) ) break ; } if ( j == M ) System . out . println ( " Pattern ▁ found ▁ at ▁ index ▁ " + i ) ; } if ( i < N - M ) { t = ( d * ( t - txt . charAt ( i ) * h ) + txt . charAt ( i + M ) ) % q ; if ( t < 0 ) t = ( t + q ) ; } } } public static void main ( String [ ] args ) { String txt = " GEEKS ▁ FOR ▁ GEEKS " ; String pat = " GEEK " ; int q = 101 ; search ( pat , txt , q ) ; } }