Rabin-Karp Substring Search with Python

rabinkarp.py

def rapin_karp(pat, txt):
    M = len(pat)
    N = len(txt)
    p = 0
    t = 0
    h = 1
    d = 256
    q = 101

    for i in range(M - 1):
        h = (h * d) % q

    for i in range(M):
        p = (d * p + ord(pat[i])) % q
        t = (d * t + ord(txt[i])) % q

    for i in range(N - M + 1):
        if p == t:
            for j in range(M):
                if txt[i + j] != pat[j]:
                    break
            if j == M - 1:
                print ("Pattern found at index " + str(i))
        if i < N - M:
            t = (d * (t - ord(txt[i]) * h) + ord(txt[i + M])) % q
            if t < 0:
                t = t + q