# Write a Python Program for Rabin-Karp Algorithm for Pattern Searching # Following program is the python implementation of# Rabin Karp Algorithm given in CLRS book  # d is the number of characters in the input alphabetd = 256  # pat  -> pattern# txt  -> text# q    -> A prime number  def search(pat, txt, q):    M = len(pat)    N = len(txt)    i = 0    j = 0    p = 0    # hash value for pattern    t = 0    # hash value for txt    h = 1      # The value of h would be "pow(d, M-1)% q"    for i in xrange(M-1):        h = (h * d)% q      # Calculate the hash value of pattern and first window    # of text    for i in xrange(M):        p = (d * p + ord(pat[i]))% q        t = (d * t + ord(txt[i]))% q      # Slide the pattern over text one by one    for i in xrange(N-M + 1):        # Check the hash values of current window of text and        # pattern if the hash values match then only check        # for characters on by one        if p == t:            # Check for characters one by one            for j in xrange(M):                if txt[i + j] != pat[j]:                    break              j+= 1            # if p == t and pat[0...M-1] = txt[i, i + 1, ...i + M-1]            if j == M:                print "Pattern found at index " + str(i)          # Calculate hash value for next window of text: Remove        # leading digit, add trailing digit        if i < N-M:            t = (d*(t-ord(txt[i])*h) + ord(txt[i + M]))% q              # We might get negative values of t, converting it to            # positive            if t < 0:                t = t + q  # Driver program to test the above functiontxt = "GEEKS FOR GEEKS"pat = "GEEK"q = 101 # A prime numbersearch(pat, txt, q)  # This code is contributed by Bhavya Jain