Buggy python submission (verdict: Runtime Error):
def rabin_karp(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 + P[i]) % q
        t0 = (d * t0 + T[i]) % q
    for s in range(n - m + 1):
        if p == t0:
            if P[0:(m - 1)] == T[s:(s + m - 1)]:
                print(s)
        if s < n - m:
            t0 = (d * (t0 - T[s] * h) + T[s + m]) % q


d = 122
q = 127
t = list(map(ord, input()))
p = list(map(ord, input()))

rabin_karp(t, p, d, q)


Fixed submission:
def compute_prefix_function(p):
    m = len(p)
    pi = [0 for _ in range(m + 1)]
    pi[1] = 0
    k = 0
    for q in range(2, m + 1):
        while k > 0 and p[k] != p[q - 1]:
            k = pi[k]
        if p[k] == p[q - 1]:
            k += 1
        pi[q] = k
    return pi


def kmp_matcher(t, p):
    n = len(t)
    m = len(p)
    pi = compute_prefix_function(p)
    q = 0
    for i in range(1, n + 1):
        while q > 0 and p[q] != t[i - 1]:
            q = pi[q]
        if p[q] == t[i - 1]:
            q += 1
        if q == m:
            print(i - m)
            q = pi[q]


t = input()
p = input()
kmp_matcher(t, p)

Buggy python submission (verdict: Time Limit Exceeded):
def rabin_karp(T, P, d, q):
    n = len(T)
    m = len(P)
    if n < m:
        return
    h = pow(d, m - 1) % q
    p = 0
    t0 = 0
    for i in range(m):
        p = (d * p + P[i]) % q
        t0 = (d * t0 + T[i]) % q
    for s in range(n - m + 1):
        if p == t0:
            if P[0:(m - 1)] == T[s:(s + m - 1)]:
                print(s)
        if s < n - m:
            t0 = (d * (t0 - T[s] * h) + T[s + m]) % q


d = 122
q = 127
t = list(map(ord, input()))
p = list(map(ord, input()))

rabin_karp(t, p, d, q)


Fixed submission:
def compute_prefix_function(p):
    m = len(p)
    pi = [0 for _ in range(m + 1)]
    pi[1] = 0
    k = 0
    for q in range(2, m + 1):
        while k > 0 and p[k] != p[q - 1]:
            k = pi[k]
        if p[k] == p[q - 1]:
            k += 1
        pi[q] = k
    return pi


def kmp_matcher(t, p):
    n = len(t)
    m = len(p)
    pi = compute_prefix_function(p)
    q = 0
    for i in range(1, n + 1):
        while q > 0 and p[q] != t[i - 1]:
            q = pi[q]
        if p[q] == t[i - 1]:
            q += 1
        if q == m:
            print(i - m)
            q = pi[q]


t = input()
p = input()
kmp_matcher(t, p)

Buggy python submission (verdict: Time Limit Exceeded):
def rabin_karp(T, P, d, q):
    n = len(T)
    m = len(P)
    if n < m:
        return
    h = 1
    p = 0
    t0 = 0
    for _ in range(m - 1):
        h = int((h * d) % q)
    for i in range(m):
        p = int((d * p + P[i]) % q)
        t0 = int((d * t0 + T[i]) % q)
    # print("h = ", h)
    # print("p = ", p)
    for s in range(n - m + 1):
        # print("t0 = ", t0)
        if p == t0:
            for i in range(m):
                if P[i] != T[s + i]:
                    # print(i, s+i)
                    break
                if i == m - 1:
                    print(s)
        if s < n - m:
            # print("     ", t0 - T[s] * h)
            # print("     ",  d)
            # print("     ", T[s + m])
            t0 = int((d * (t0 - T[s] * h) + T[s + m]) % q)


d = 999999937
q = 1000000007
t = list(map(ord, input()))
p = list(map(ord, input()))

rabin_karp(t, p, d, q)


Fixed submission:
def compute_prefix_function(p):
    m = len(p)
    pi = [0 for _ in range(m + 1)]
    pi[1] = 0
    k = 0
    for q in range(2, m + 1):
        while k > 0 and p[k] != p[q - 1]:
            k = pi[k]
        if p[k] == p[q - 1]:
            k += 1
        pi[q] = k
    return pi


def kmp_matcher(t, p):
    n = len(t)
    m = len(p)
    pi = compute_prefix_function(p)
    q = 0
    for i in range(1, n + 1):
        while q > 0 and p[q] != t[i - 1]:
            q = pi[q]
        if p[q] == t[i - 1]:
            q += 1
        if q == m:
            print(i - m)
            q = pi[q]


t = input()
p = input()
kmp_matcher(t, p)

Buggy python submission (verdict: Time Limit Exceeded):
def rabin_karp(T, P, d, q):
    n = len(T)
    m = len(P)
    if n < m:
        return
    h = 1
    p = 0
    t0 = 0
    #for _ in range(m - 1):
    #    h = int((h * d) % q)
    h = int(pow(d, m - 1))
    for i in range(m):
        p = int((d * p + P[i]) % q)
        t0 = int((d * t0 + T[i]) % q)
    # print("h = ", h)
    # print("p = ", p)
    for s in range(n - m + 1):
        # print("t0 = ", t0)
        if p == t0:
            for i in range(m):
                if P[i] != T[s + i]:
                    # print(i, s+i)
                    break
                if i == m - 1:
                    print(s)
        if s < n - m:
            # print("     ", t0 - T[s] * h)
            # print("     ",  d)
            # print("     ", T[s + m])
            t0 = int((d * (t0 - T[s] * h) + T[s + m]) % q)


d = 999999937
q = 1000000007
t = list(map(ord, input()))
p = list(map(ord, input()))

rabin_karp(t, p, d, q)


Fixed submission:
def compute_prefix_function(p):
    m = len(p)
    pi = [0 for _ in range(m + 1)]
    pi[1] = 0
    k = 0
    for q in range(2, m + 1):
        while k > 0 and p[k] != p[q - 1]:
            k = pi[k]
        if p[k] == p[q - 1]:
            k += 1
        pi[q] = k
    return pi


def kmp_matcher(t, p):
    n = len(t)
    m = len(p)
    pi = compute_prefix_function(p)
    q = 0
    for i in range(1, n + 1):
        while q > 0 and p[q] != t[i - 1]:
            q = pi[q]
        if p[q] == t[i - 1]:
            q += 1
        if q == m:
            print(i - m)
            q = pi[q]


t = input()
p = input()
kmp_matcher(t, p)

Buggy python submission (verdict: Time Limit Exceeded):
def finite_automation_matcher(T, delta, m):
    n = len(T)
    q = 0
    for i in range(n):
        q = delta[q][con(T[i])]
        if q == m:
            print(i - m + 1)


def con(x):
    if 48 <= ord(x) <= 57:
        return ord(x) - 48
    elif 65 <= ord(x) <= 90:
        return ord(x) - 55
    else:
        return ord(x) - 61


def i_con(a):
    if 0 <= a <= 9:
        return chr(a + 48)
    elif 10 <= a <= 35:
        return chr(a + 55)
    else:
        return chr(a + 61)


def compute_transition_function(P):
    sigma = list(range(62))
    m = len(P)
    delta = [[0 for _ in range(62)] for _ in range(m+1)]
    for q in range(m + 1):
        for a in sigma:
            k = min(m + 1, q + 2)
            while True:
                k = k - 1
                # print(m, q, k, P[0:k])
                if is_suffix(P[0:k], P[0:q], i_con(a)):
                    break
            delta[q][a] = k
    # print(delta)
    return delta


def is_suffix(x, y, a):
    if len(x) == 0:
        return True
    if x[len(x) - 1] != a:
        return False
    for i in range(len(x) - 1):
        if x[i] != y[len(y) - len(x) + 1 + i]:
            return False
    return True


t = input()
p = input()
m = len(p)
delta = compute_transition_function(p)
finite_automation_matcher(t, delta, m)


Fixed submission:
def compute_prefix_function(p):
    m = len(p)
    pi = [0 for _ in range(m + 1)]
    pi[1] = 0
    k = 0
    for q in range(2, m + 1):
        while k > 0 and p[k] != p[q - 1]:
            k = pi[k]
        if p[k] == p[q - 1]:
            k += 1
        pi[q] = k
    return pi


def kmp_matcher(t, p):
    n = len(t)
    m = len(p)
    pi = compute_prefix_function(p)
    q = 0
    for i in range(1, n + 1):
        while q > 0 and p[q] != t[i - 1]:
            q = pi[q]
        if p[q] == t[i - 1]:
            q += 1
        if q == m:
            print(i - m)
            q = pi[q]


t = input()
p = input()
kmp_matcher(t, p)

Buggy python submission (verdict: Time Limit Exceeded):
def finite_automation_matcher(T, delta, m):
    n = len(T)
    q = 0
    for i in range(n):
        q = delta[q * 62 + con(T[i])]
        if q == m:
            print(i - m + 1)


def con(x):
    if 48 <= ord(x) <= 57:
        return ord(x) - 48
    elif 65 <= ord(x) <= 90:
        return ord(x) - 55
    else:
        return ord(x) - 61


def i_con(a):
    if 0 <= a <= 9:
        return chr(a + 48)
    elif 10 <= a <= 35:
        return chr(a + 55)
    else:
        return chr(a + 61)


def compute_transition_function(P):
    sigma = list(range(62))
    m = len(P)
    delta = [0 for _ in range(62 * (m+1))]
    for q in range(m + 1):
        for a in sigma:
            k = min(m + 1, q + 2)
            while True:
                k = k - 1
                # print(m, q, k, P[0:k])
                if is_suffix(P[0:k], P[0:q], i_con(a)):
                    break
            delta[q * 62 + a] = k
    # print(delta)
    return delta


def is_suffix(x, y, a):
    if len(x) == 0:
        return True
    if x[len(x) - 1] != a:
        return False
    for i in range(len(x) - 1):
        if x[i] != y[len(y) - len(x) + 1 + i]:
            return False
    return True


t = input()
p = input()
m = len(p)
delta = compute_transition_function(p)
finite_automation_matcher(t, delta, m)


Fixed submission:
def compute_prefix_function(p):
    m = len(p)
    pi = [0 for _ in range(m + 1)]
    pi[1] = 0
    k = 0
    for q in range(2, m + 1):
        while k > 0 and p[k] != p[q - 1]:
            k = pi[k]
        if p[k] == p[q - 1]:
            k += 1
        pi[q] = k
    return pi


def kmp_matcher(t, p):
    n = len(t)
    m = len(p)
    pi = compute_prefix_function(p)
    q = 0
    for i in range(1, n + 1):
        while q > 0 and p[q] != t[i - 1]:
            q = pi[q]
        if p[q] == t[i - 1]:
            q += 1
        if q == m:
            print(i - m)
            q = pi[q]


t = input()
p = input()
kmp_matcher(t, p)

Buggy python submission (verdict: Time Limit Exceeded):
def rabin_karp(T, P, d):
    n = len(T)
    m = len(P)
    if n < m:
        return
    h = 1
    p = 0
    t0 = 0
    for _ in range(m - 1):
        h *= d
    for i in range(m):
        p = d * p + P[i]
        t0 = d * t0 + T[i]
    # print("h = ", h)
    # print("p = ", p)
    for s in range(n - m + 1):
        # print("t0 = ", t0)
        if p == t0:
            print(s)
        if s < n - m:
            # print("     ", t0 - T[s] * h)
            # print("     ",  d)
            # print("     ", T[s + m])
            t0 = d * (t0 - T[s] * h) + T[s + m]


d = 1009
t = list(map(ord, input()))
p = list(map(ord, input()))

rabin_karp(t, p, d)


Fixed submission:
def compute_prefix_function(p):
    m = len(p)
    pi = [0 for _ in range(m + 1)]
    pi[1] = 0
    k = 0
    for q in range(2, m + 1):
        while k > 0 and p[k] != p[q - 1]:
            k = pi[k]
        if p[k] == p[q - 1]:
            k += 1
        pi[q] = k
    return pi


def kmp_matcher(t, p):
    n = len(t)
    m = len(p)
    pi = compute_prefix_function(p)
    q = 0
    for i in range(1, n + 1):
        while q > 0 and p[q] != t[i - 1]:
            q = pi[q]
        if p[q] == t[i - 1]:
            q += 1
        if q == m:
            print(i - m)
            q = pi[q]


t = input()
p = input()
kmp_matcher(t, p)

Buggy python submission (verdict: Time Limit Exceeded):
def rabin_karp(T, P, d):
    n = len(T)
    m = len(P)
    if n < m:
        return
    h = 1
    p = 0
    t0 = 0
    for _ in range(m - 1):
        h *= d
    for i in range(m):
        p = d * p + P[i]
        t0 = d * t0 + T[i]
    # print("h = ", h)
    # print("p = ", p)
    for s in range(n - m + 1):
        # print("t0 = ", t0)
        if p == t0:
            print(s)
        if s < n - m:
            # print("     ", t0 - T[s] * h)
            # print("     ",  d)
            # print("     ", T[s + m])
            t0 = d * (t0 - T[s] * h) + T[s + m]


d = 167
t = list(map(ord, input()))
p = list(map(ord, input()))

rabin_karp(t, p, d)


Fixed submission:
def compute_prefix_function(p):
    m = len(p)
    pi = [0 for _ in range(m + 1)]
    pi[1] = 0
    k = 0
    for q in range(2, m + 1):
        while k > 0 and p[k] != p[q - 1]:
            k = pi[k]
        if p[k] == p[q - 1]:
            k += 1
        pi[q] = k
    return pi


def kmp_matcher(t, p):
    n = len(t)
    m = len(p)
    pi = compute_prefix_function(p)
    q = 0
    for i in range(1, n + 1):
        while q > 0 and p[q] != t[i - 1]:
            q = pi[q]
        if p[q] == t[i - 1]:
            q += 1
        if q == m:
            print(i - m)
            q = pi[q]


t = input()
p = input()
kmp_matcher(t, p)

Buggy python submission (verdict: Time Limit Exceeded):
def rabin_karp(T, P, d):
    n = len(T)
    m = len(P)
    if n < m:
        return
    h = 1
    p = 0
    t0 = 0
    for _ in range(m - 1):
        h *= d
    for i in range(m):
        p = d * p + P[i]
        t0 = d * t0 + T[i]
    for s in range(n - m + 1):
        if p == t0:
            print(s)
        if s < n - m:
            t0 = d * (t0 - T[s] * h) + T[s + m]


d = 167
t = list(map(ord, input()))
p = list(map(ord, input()))

rabin_karp(t, p, d)


Fixed submission:
def compute_prefix_function(p):
    m = len(p)
    pi = [0 for _ in range(m + 1)]
    pi[1] = 0
    k = 0
    for q in range(2, m + 1):
        while k > 0 and p[k] != p[q - 1]:
            k = pi[k]
        if p[k] == p[q - 1]:
            k += 1
        pi[q] = k
    return pi


def kmp_matcher(t, p):
    n = len(t)
    m = len(p)
    pi = compute_prefix_function(p)
    q = 0
    for i in range(1, n + 1):
        while q > 0 and p[q] != t[i - 1]:
            q = pi[q]
        if p[q] == t[i - 1]:
            q += 1
        if q == m:
            print(i - m)
            q = pi[q]


t = input()
p = input()
kmp_matcher(t, p)

Buggy python submission (verdict: Time Limit Exceeded):
def rabin_karp(T, P, d):
    n = len(T)
    m = len(P)
    if n < m:
        return
    h = 1
    p = 0
    t0 = 0
    for _ in range(m - 1):
        h *= d
    for i in range(m):
        p = d * p + P[i]
        t0 = d * t0 + T[i]
    ans = []
    for s in range(n - m + 1):
        if p == t0:
            ans.append(s)
        if s < n - m:
            t0 = d * (t0 - T[s] * h) + T[s + m]
    for s in ans:
        print(s)


d = 167
t = list(map(ord, input()))
p = list(map(ord, input()))

rabin_karp(t, p, d)


Fixed submission:
def compute_prefix_function(p):
    m = len(p)
    pi = [0 for _ in range(m + 1)]
    pi[1] = 0
    k = 0
    for q in range(2, m + 1):
        while k > 0 and p[k] != p[q - 1]:
            k = pi[k]
        if p[k] == p[q - 1]:
            k += 1
        pi[q] = k
    return pi


def kmp_matcher(t, p):
    n = len(t)
    m = len(p)
    pi = compute_prefix_function(p)
    q = 0
    for i in range(1, n + 1):
        while q > 0 and p[q] != t[i - 1]:
            q = pi[q]
        if p[q] == t[i - 1]:
            q += 1
        if q == m:
            print(i - m)
            q = pi[q]


t = input()
p = input()
kmp_matcher(t, p)