def Compute_Prefix_Function(P):
    m = len(P)
    pi = [0] * m
    k = 0

    for q in range(1, m):
        while k > 0 and P[k] != P[q]:
            k = pi[k - 1]

        if P[k] == P[q]:
            k += 1

        pi[q] = k

    return pi


def KMP_Matcher(S, P):
    n = len(S)
    m = len(P)

    pi = Compute_Prefix_Function(P)
    q = 0

    for i in range(n):
        while q > 0 and P[q] != S[i]:
            q = pi[q - 1]

        if P[q] == S[i]:
            q += 1

        if q == m:
            print("Pattern occurs with shift", i - m + 1)
            q = pi[q - 1]


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

KMP_Matcher(S, P)