Rabin | d is the number of characters in the input alphabet ; pat -> pattern txt -> text q -> A prime number ; hash value ; for pattern hash value ; 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
< ? php $ d = 256 ; function search ( $ pat , $ txt , $ q ) { $ M = strlen ( $ pat ) ; $ N = strlen ( $ txt ) ; $ i ; $ j ; $ p = 0 ; $ t = 0 ; $ h = 1 ; $ d = 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 ) echo " Pattern ▁ found ▁ at ▁ index ▁ " , $ i , " STRNEWLINE " ; } if ( $ i < $ N - $ M ) { $ t = ( $ d * ( $ t - $ txt [ $ i ] * $ h ) + $ txt [ $ i + $ M ] ) % $ q ; if ( $ t < 0 ) $ t = ( $ t + $ q ) ; } } } $ txt = " GEEKS ▁ FOR ▁ GEEKS " ; $ pat = " GEEK " ; $ q = 101 ; search ( $ pat , $ txt , $ q ) ; ? >