def Rabin_Karp_Matcher(T, P, d, q):
    n = len(T)
    m = len(P)

    h = pow(d, m - 1, q)
    p = 0
    t0 = 0

    for i in range(m):
        p = (d * p + ord(P[i])) % q
        t0 = (d * t0 + ord(T[i])) % q

    for s in range(n - m + 1):
        if p == t0:
            if P == T[s:s + m]:
                print("Pattern occurs with shift", s)

        if s < n - m:
            t0 = (d * (t0 - ord(T[s]) * h) + ord(T[s + m])) % q
            if t0 < 0:
                t0 += q


# Example
T = input("Enter text: ")
P = input("Enter pattern: ")

d = 256      # number of characters
q = 101      # prime number

Rabin_Karp_Matcher(T, P, d, q)