Problem p02962 (python)

Fixed submission:
def z_alg(S):
    N = len(S)
    Z = [0] * N
    Z[0] = N
    i, j = 1, 0
    while i < N:
        while i + j < N and S[j] == S[i + j]:
            j += 1
        Z[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < N and k + Z[k] < j:
            Z[i + k] = Z[k]
            k += 1
        i += k
        j -= k
    return Z


def main():
    S = input()
    T = input()
    REP_S = ''
    target_len = len(S) + len(T) - 1
    while len(REP_S) < target_len:
        REP_S += S

    # Z-algorithmでREP_S中に含まれるTの場所を調べる
    T_REP_S = T + REP_S
    z = z_alg(T_REP_S)
    location_list = list()
    for i in range(len(S)):
        if z[i + len(T)] >= len(T):
            location_list.append(i)

    # Tがなければ0を出力して終了
    if len(location_list) == 0:
        print(0)
        return

    # グラフを作り、最長パスに含まれるノード数が答え（ループがあったら-1）
    node_flag_list = [0] * len(S)
    for n in location_list:
        node_flag_list[n] = 1
    depth_list = [-1] * len(S)
    for n in location_list:
        if depth_list[n] >= 0:
            continue
        cur_node = n
        d, has_loop = 0, False
        while node_flag_list[cur_node] == 1:
            depth_list[cur_node] = d
            d += 1
            cur_node = (cur_node + len(T)) % len(S)
            if cur_node == n:
                has_loop = True
                break
        if has_loop:
            print(-1)
            return

    print(max(depth_list) + 1)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys


sys.setrecursionlimit(10**6)


def z_alg(S):
    N = len(S)
    Z = [0] * N
    Z[0] = N
    i, j = 1, 0
    while i < N:
        while i + j < N and S[j] == S[i + j]:
            j += 1
        Z[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < N and k + Z[k] < j:
            Z[i + k] = Z[k]
            k += 1
        i += k
        j -= k
    return Z


S = input()
T = input()
REP_S = ''
target_len = len(S) + len(T) - 1
while len(REP_S) < target_len:
    REP_S += S

# Z-algorithmでREP_S中に含まれるTの場所を調べる
T_REP_S = T + REP_S
z = z_alg(T_REP_S)
location_list = list()
for i in range(len(S)):
    if z[i + len(T)] >= len(T):
        location_list.append(i)

# Tがなければ0を出力して終了
if len(location_list) == 0:
    print(0)
    exit(0)

# グラフを作り、最長パスに含まれるノード数が答え（ループがあったら-1）
node_flag_list = [0] * len(S)
for n in location_list:
    node_flag_list[n] = 1
node_num_list = [-1] * len(S)

def dfs(node, depth=0):
    # return (has_loop, node_num)
    if depth > len(location_list):
        return True, -1
    if node_num_list[node] >= 0:
        return False, node_num_list[node]
    next_node = (node + len(T)) % len(S)
    if node_flag_list[next_node] == 0:
        node_num_list[node] = 0
        return False, 0
    has_loop, node_num = dfs(next_node, depth + 1)
    if has_loop:
        return True, -1
    node_num_list[node] = 1 + node_num
    return False, 1 + node_num

for n in location_list:
    has_loop, _ = dfs(n)
    if has_loop:
        print(-1)
        exit(0)

print(max(node_num_list) + 1)

Buggy submission (verdict: Runtime Error):
import sys


sys.setrecursionlimit(10**6)


def z_alg(S):
    N = len(S)
    Z = [0] * N
    Z[0] = N
    i, j = 1, 0
    while i < N:
        while i + j < N and S[j] == S[i + j]:
            j += 1
        Z[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < N and k + Z[k] < j:
            Z[i + k] = Z[k]
            k += 1
        i += k
        j -= k
    return Z


def main():
    S = input()
    T = input()
    REP_S = ''
    target_len = len(S) + len(T) - 1
    while len(REP_S) < target_len:
        REP_S += S

    # Z-algorithmでREP_S中に含まれるTの場所を調べる
    T_REP_S = T + REP_S
    z = z_alg(T_REP_S)
    location_list = list()
    for i in range(len(S)):
        if z[i + len(T)] >= len(T):
            location_list.append(i)

    # Tがなければ0を出力して終了
    if len(location_list) == 0:
        print(0)
        return

    # グラフを作り、最長パスに含まれるノード数が答え（ループがあったら-1）
    node_flag_list = [0] * len(S)
    for n in location_list:
        node_flag_list[n] = 1
    node_num_list = [-1] * len(S)

    def dfs(node, depth=0):
        # return (has_loop, node_num)
        if depth > len(location_list):
            return True, -1
        if node_num_list[node] >= 0:
            return False, node_num_list[node]
        next_node = (node + len(T)) % len(S)
        if node_flag_list[next_node] == 0:
            node_num_list[node] = 0
            return False, 0
        has_loop, node_num = dfs(next_node, depth + 1)
        if has_loop:
            return True, -1
        node_num_list[node] = 1 + node_num
        return False, 1 + node_num

    for n in location_list:
        has_loop, _ = dfs(n)
        if has_loop:
            print(-1)
            return

    print(max(node_num_list) + 1)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys


sys.setrecursionlimit(10**7)


def z_alg(S):
    N = len(S)
    Z = [0] * N
    Z[0] = N
    i, j = 1, 0
    while i < N:
        while i + j < N and S[j] == S[i + j]:
            j += 1
        Z[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < N and k + Z[k] < j:
            Z[i + k] = Z[k]
            k += 1
        i += k
        j -= k
    return Z


def main():
    S = input()
    T = input()
    REP_S = ''
    target_len = len(S) + len(T) - 1
    while len(REP_S) < target_len:
        REP_S += S

    # Z-algorithmでREP_S中に含まれるTの場所を調べる
    T_REP_S = T + REP_S
    z = z_alg(T_REP_S)
    location_list = list()
    for i in range(len(S)):
        if z[i + len(T)] >= len(T):
            location_list.append(i)

    # Tがなければ0を出力して終了
    if len(location_list) == 0:
        print(0)
        return

    # グラフを作り、最長パスに含まれるノード数が答え（ループがあったら-1）
    node_flag_list = [0] * len(S)
    for node in location_list:
        node_flag_list[node] = 1
    node_num_list = [-1] * len(S)

    def dfs(node, depth=0):
        # return (has_loop, node_num)
        if depth > len(location_list):
            return True, -1
        if node_num_list[node] >= 0:
            return False, node_num_list[node]
        next_node = (node + len(T)) % len(S)
        if node_flag_list[next_node] == 0:
            node_num_list[node] = 0
            return False, 0
        has_loop, node_num = dfs(next_node, depth + 1)
        if has_loop:
            return True, -1
        n = 1 + node_num
        node_num_list[node] = n
        return False, n

    for node in location_list:
        has_loop, _ = dfs(node)
        if has_loop:
            print(-1)
            return

    print(max(node_num_list) + 1)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys


sys.setrecursionlimit(10**6)


def z_alg(S):
    N = len(S)
    Z = [0] * N
    Z[0] = N
    i, j = 1, 0
    while i < N:
        while i + j < N and S[j] == S[i + j]:
            j += 1
        Z[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < N and k + Z[k] < j:
            Z[i + k] = Z[k]
            k += 1
        i += k
        j -= k
    return Z


def main():
    S = input()
    T = input()
    REP_S = ''
    target_len = len(S) + len(T) - 1
    while len(REP_S) < target_len:
        REP_S += S

    # Z-algorithmでREP_S中に含まれるTの場所を調べる
    T_REP_S = T + REP_S
    z = z_alg(T_REP_S)
    location_list = list()
    for i in range(len(S)):
        if z[i + len(T)] >= len(T):
            location_list.append(i)

    # Tがなければ0を出力して終了
    if len(location_list) == 0:
        print(0)
        return

    # グラフを作り、最長パスに含まれるノード数が答え（ループがあったら-1）
    node_flag_list = [0] * len(S)
    for node in location_list:
        node_flag_list[node] = 1
    node_num_list = [-1] * len(S)

    def dfs(node, depth=0):
        # return (has_loop, node_num)
        if depth > len(location_list):
            return True, -1
        if node_num_list[node] >= 0:
            return False, node_num_list[node]
        next_node = (node + len(T)) % len(S)
        if node_flag_list[next_node] == 0:
            node_num_list[node] = 0
            return False, 0
        has_loop, node_num = dfs(next_node, depth + 1)
        if has_loop:
            return True, -1
        n = 1 + node_num
        node_num_list[node] = n
        return False, n

    for node in location_list:
        has_loop, _ = dfs(node)
        if has_loop:
            print(-1)
            return

    print(max(node_num_list) + 1)


if __name__ == '__main__':
    main()