Rabin | d is the number of characters in the input alphabet ; pat -> pattern txt -> text q -> A prime number ; hash value for pattern t = 0 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 values of t , converting it to positive ; Driver Code ; A prime number ; Function Call
d = 256 NEW_LINE def search ( pat , txt , q ) : NEW_LINE INDENT M = len ( pat ) NEW_LINE N = len ( txt ) NEW_LINE i = 0 NEW_LINE j = 0 NEW_LINE h = 1 NEW_LINE for i in xrange ( M - 1 ) : NEW_LINE INDENT h = ( h * d ) % q NEW_LINE DEDENT for i in xrange ( M ) : NEW_LINE INDENT p = ( d * p + ord ( pat [ i ] ) ) % q NEW_LINE t = ( d * t + ord ( txt [ i ] ) ) % q NEW_LINE DEDENT for i in xrange ( N - M + 1 ) : NEW_LINE INDENT if p == t : NEW_LINE INDENT for j in xrange ( M ) : NEW_LINE INDENT if txt [ i + j ] != pat [ j ] : NEW_LINE INDENT break NEW_LINE DEDENT else : j += 1 NEW_LINE DEDENT if j == M : NEW_LINE INDENT print " Pattern ▁ found ▁ at ▁ index ▁ " + str ( i ) NEW_LINE DEDENT DEDENT if i < N - M : NEW_LINE INDENT t = ( d * ( t - ord ( txt [ i ] ) * h ) + ord ( txt [ i + M ] ) ) % q NEW_LINE if t < 0 : NEW_LINE INDENT t = t + q NEW_LINE DEDENT DEDENT DEDENT DEDENT txt = " GEEKS ▁ FOR ▁ GEEKS " NEW_LINE pat = " GEEK " NEW_LINE q = 101 NEW_LINE search ( pat , txt , q ) NEW_LINE