Buggy python submission (verdict: Time Limit Exceeded):

def z_algorithm(S):
    # 文字列が与えられた時、各 i について
    # 「S と S[i:|S|-1] の最長共通接頭辞の長さ」を記録した配列 A を
    #  O(|S|) で構築するアルゴリズム
    # S: aaabaaaab
    # A: 921034210
    # 例えば、A[5] = 4だが、これは、S[0:4] == S[5:5+4] 
    # (Sの0文字目からと5文字目からは、4文字一致している(aaab)) ことを意味する。

    lenS = len(S)
    A = [0] * lenS
    i = 1; j = 0
    A[0] = lenS
    # i: 調査開始点
    # iを1文字目からlen(S)-1文字目まで左から順に動かしていく
    while i < lenS:
        # j: 何文字目まで一致するか(iからの距離)
        # 一致しなくなるまでjを左から右へ動かしていく
        while i + j < lenS and S[j] == S[i + j]:
            j += 1
        # 1文字も一致しない場合は調査開始点を一つ右にずらす
        if j == 0:
            i += 1
            continue

        A[i] = j

        # 例）S: momomosumomomomo
        # A[1] = 0, A[2] = 4 (A[0:4] == A[2:2+4] = "momo")

        # i=2の調査が終わった段階で、
        # S[3] = S[2 + 1] = S[1] = "o" 
        # で、A[3] = A[1] = 0（Sの1文字目からと3文字目からは一致しない）
        # のは明らかなので、i = 3の結果はi = 1の結果を流用して0とする。
        # つまり、A[3] = A[2 + 1] = A[1] = 0

        # 今回、i + j 文字目まで、一致するか調べたので、
        # A[i + 1] ~ A[i + j - 1] までの間で、計算結果を流用できるところは流用する
        # j <= k + A[k] となるようなkの場合、
        # j文字目以降は今回調べてないので一致するか本当に分からないので、流用をやめる
        # 今回の場合、
        # k = 1: 1 + A[1] = 1 + 0 = 1 < j = 4 なので、流用できる
        # k = 2: 2 + A[2] = 2 + 4 = 6 > j = 4 なので、流用できない
        # つなり、k=2となった瞬間、流用をせずにループを抜ける。
        k = 1
        while k + A[k] < j and i + k < lenS:
            A[i + k] = A[k]
            k += 1
        # 今回 1回 (=k-1回) 流用できた、つまり A[3] = A[2(=i) + 2(=k) - 1] まで確定したので、
        # 次は A[4] = A[i + k] から調べる
        i += k

        # また、k = 2 のとき、k + A[k] >= j となって流用を打ち切られたということは、
        # k + A[i + k] >= j  => A[i + k] >= j - k
        # A[4] は少なくとも j - k = 4 - 2 = 2 以上となることが確定する。
        # つまり、S[4:]とSは、少なくとも最初の2文字 (j-k文字) は一致する。
        # よって、A[4]を調べるときは、j=2から調査を開始すればよい。
        # （つまり、S[6]とS[4:][2]が一致しているか調べるところから始める）

        #             0123456
        # S         = momomosumomomomo
        # S[2:]     =   momosumomomomo   <- 5文字目が違う
        # S[2:][2:] =     mosumomomomo   <- 3文字目が違う
        # S[4:]     =     mosumomomomo   <- 3文字目が違う
        # S[4:][2:] =       sumomomomo   <- 1文字目が違う
        j -= k
    return A

def main():
    N = int(input())
    S = input()

    ans = 0

    # Z-algorithm で、最長共通接頭辞の長さを調べる。
    # Z-algorithm は、「S と S[i:|S|-1] の最長共通接頭辞の長さ」を記録するので、
    # S[1]以降の部分文字列同士の長さは、
    # S=S[i:]としてiをずらしながら最長共通接頭辞を調べることで分かる

    for i in range(N-1):
        A = z_algorithm(S[i:])
        # print(A)
        # 例えばS = ababa のとき、
        # A = [5, 0, 3, 0, 1] となる。
        # A[2] = 3 だが、範囲が被ってしまっているので、
        # A[i] > i の場合、一致する文字数はiまでにしておく。
        ans = max(ans, max([min(i, a) for i, a in enumerate(A)]))

    print(ans)

if __name__ == '__main__':
    main()

Fixed submission:

def z_algorithm(S):
    # 文字列が与えられた時、各 i について
    # 「S と S[i:|S|-1] の最長共通接頭辞の長さ」を記録した配列 A を
    #  O(|S|) で構築するアルゴリズム
    # S: aaabaaaab
    # A: 921034210
    # 例えば、A[5] = 4だが、これは、S[0:4] == S[5:5+4] 
    # (Sの0文字目からと5文字目からは、4文字一致している(aaab)) ことを意味する。

    lenS = len(S)
    A = [0] * lenS
    i = 1; j = 0
    A[0] = lenS
    # i: 調査開始点
    # iを1文字目からlen(S)-1文字目まで左から順に動かしていく
    while i < lenS:
        # j: 何文字目まで一致するか(iからの距離)
        # 一致しなくなるまでjを左から右へ動かしていく
        while i + j < lenS and S[j] == S[i + j]:
            j += 1
        # 1文字も一致しない場合は調査開始点を一つ右にずらす
        if j == 0:
            i += 1
            continue

        A[i] = j

        # 例）S: momomosumomomomo
        # A[1] = 0, A[2] = 4 (A[0:4] == A[2:2+4] = "momo")

        # i=2の調査が終わった段階で、
        # S[3] = S[2 + 1] = S[1] = "o" 
        # で、A[3] = A[1] = 0（Sの1文字目からと3文字目からは一致しない）
        # のは明らかなので、i = 3の結果はi = 1の結果を流用して0とする。
        # つまり、A[3] = A[2 + 1] = A[1] = 0

        # 今回、i + j 文字目まで、一致するか調べたので、
        # A[i + 1] ~ A[i + j - 1] までの間で、計算結果を流用できるところは流用する
        # j <= k + A[k] となるようなkの場合、
        # j文字目以降は今回調べてないので一致するか本当に分からないので、流用をやめる
        # 今回の場合、
        # k = 1: 1 + A[1] = 1 + 0 = 1 < j = 4 なので、流用できる
        # k = 2: 2 + A[2] = 2 + 4 = 6 > j = 4 なので、流用できない
        # つなり、k=2となった瞬間、流用をせずにループを抜ける。
        k = 1
        while k + A[k] < j and i + k < lenS:
            A[i + k] = A[k]
            k += 1
        # 今回 1回 (=k-1回) 流用できた、つまり A[3] = A[2(=i) + 2(=k) - 1] まで確定したので、
        # 次は A[4] = A[i + k] から調べる
        i += k

        # また、k = 2 のとき、k + A[k] >= j となって流用を打ち切られたということは、
        # k + A[i + k] >= j  => A[i + k] >= j - k
        # A[4] は少なくとも j - k = 4 - 2 = 2 以上となることが確定する。
        # つまり、S[4:]とSは、少なくとも最初の2文字 (j-k文字) は一致する。
        # よって、A[4]を調べるときは、j=2から調査を開始すればよい。
        # （つまり、S[6]とS[4:][2]が一致しているか調べるところから始める）

        #             0123456
        # S         = momomosumomomomo
        # S[2:]     =   momosumomomomo   <- 5文字目が違う
        # S[2:][2:] =     mosumomomomo   <- 3文字目が違う
        # S[4:]     =     mosumomomomo   <- 3文字目が違う
        # S[4:][2:] =       sumomomomo   <- 1文字目が違う
        j -= k
    return A

def main():
    N = int(input())
    S = input()

    ans = 0

    # Z-algorithm で、最長共通接頭辞の長さを調べる。
    # Z-algorithm は、「S と S[i:|S|-1] の最長共通接頭辞の長さ」を記録するので、
    # S[1]以降の部分文字列同士の長さは、
    # S=S[i:]としてiをずらしながら最長共通接頭辞を調べることで分かる

    for i in range(N-1):
        A = z_algorithm(S[i:])
        # print(A)
        # 例えばS = ababa のとき、
        # A = [5, 0, 3, 0, 1] となる。
        # A[2] = 3 だが、範囲が被ってしまっているので、
        # A[i] > i の場合、一致する文字数はiまでにしておく。
        ans = max(ans, max([min(i, a) for i, a in enumerate(A)]))

    print(ans)

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
# from collections import deque
def main():
    N = int(input())
    S = input()

    # d = deque()
    max_len = N // 2
    ans = 0

    for L in reversed(range(1, max_len + 1)):
        found = False
        for i in range(N-L):
            if S[i:i+L] in S[i+L:]:
                found = True
                break
        if found:
            ans = L
            break
    print(ans)

if __name__ == '__main__':
    main()

Fixed submission:

def z_algorithm(S):
    # 文字列が与えられた時、各 i について
    # 「S と S[i:|S|-1] の最長共通接頭辞の長さ」を記録した配列 A を
    #  O(|S|) で構築するアルゴリズム
    # S: aaabaaaab
    # A: 921034210
    # 例えば、A[5] = 4だが、これは、S[0:4] == S[5:5+4] 
    # (Sの0文字目からと5文字目からは、4文字一致している(aaab)) ことを意味する。

    lenS = len(S)
    A = [0] * lenS
    i = 1; j = 0
    A[0] = lenS
    # i: 調査開始点
    # iを1文字目からlen(S)-1文字目まで左から順に動かしていく
    while i < lenS:
        # j: 何文字目まで一致するか(iからの距離)
        # 一致しなくなるまでjを左から右へ動かしていく
        while i + j < lenS and S[j] == S[i + j]:
            j += 1
        # 1文字も一致しない場合は調査開始点を一つ右にずらす
        if j == 0:
            i += 1
            continue

        A[i] = j

        # 例）S: momomosumomomomo
        # A[1] = 0, A[2] = 4 (A[0:4] == A[2:2+4] = "momo")

        # i=2の調査が終わった段階で、
        # S[3] = S[2 + 1] = S[1] = "o" 
        # で、A[3] = A[1] = 0（Sの1文字目からと3文字目からは一致しない）
        # のは明らかなので、i = 3の結果はi = 1の結果を流用して0とする。
        # つまり、A[3] = A[2 + 1] = A[1] = 0

        # 今回、i + j 文字目まで、一致するか調べたので、
        # A[i + 1] ~ A[i + j - 1] までの間で、計算結果を流用できるところは流用する
        # j <= k + A[k] となるようなkの場合、
        # j文字目以降は今回調べてないので一致するか本当に分からないので、流用をやめる
        # 今回の場合、
        # k = 1: 1 + A[1] = 1 + 0 = 1 < j = 4 なので、流用できる
        # k = 2: 2 + A[2] = 2 + 4 = 6 > j = 4 なので、流用できない
        # つなり、k=2となった瞬間、流用をせずにループを抜ける。
        k = 1
        while k + A[k] < j and i + k < lenS:
            A[i + k] = A[k]
            k += 1
        # 今回 1回 (=k-1回) 流用できた、つまり A[3] = A[2(=i) + 2(=k) - 1] まで確定したので、
        # 次は A[4] = A[i + k] から調べる
        i += k

        # また、k = 2 のとき、k + A[k] >= j となって流用を打ち切られたということは、
        # k + A[i + k] >= j  => A[i + k] >= j - k
        # A[4] は少なくとも j - k = 4 - 2 = 2 以上となることが確定する。
        # つまり、S[4:]とSは、少なくとも最初の2文字 (j-k文字) は一致する。
        # よって、A[4]を調べるときは、j=2から調査を開始すればよい。
        # （つまり、S[6]とS[4:][2]が一致しているか調べるところから始める）

        #             0123456
        # S         = momomosumomomomo
        # S[2:]     =   momosumomomomo   <- 5文字目が違う
        # S[2:][2:] =     mosumomomomo   <- 3文字目が違う
        # S[4:]     =     mosumomomomo   <- 3文字目が違う
        # S[4:][2:] =       sumomomomo   <- 1文字目が違う
        j -= k
    return A

def main():
    N = int(input())
    S = input()

    ans = 0

    # Z-algorithm で、最長共通接頭辞の長さを調べる。
    # Z-algorithm は、「S と S[i:|S|-1] の最長共通接頭辞の長さ」を記録するので、
    # S[1]以降の部分文字列同士の長さは、
    # S=S[i:]としてiをずらしながら最長共通接頭辞を調べることで分かる

    for i in range(N-1):
        A = z_algorithm(S[i:])
        # print(A)
        # 例えばS = ababa のとき、
        # A = [5, 0, 3, 0, 1] となる。
        # A[2] = 3 だが、範囲が被ってしまっているので、
        # A[i] > i の場合、一致する文字数はiまでにしておく。
        ans = max(ans, max([min(i, a) for i, a in enumerate(A)]))

    print(ans)

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N = int(input())
    S = input()

    max_len = N // 2

    ans = 0
    for L in range(1, max_len + 1):
        found = False
        for i in range(N-L):
            if S[i:i+L] in S[i+L:]:
                found = True
                break
        if found:
            ans = L
    print(ans)

if __name__ == '__main__':
    main()

Fixed submission:

def z_algorithm(S):
    # 文字列が与えられた時、各 i について
    # 「S と S[i:|S|-1] の最長共通接頭辞の長さ」を記録した配列 A を
    #  O(|S|) で構築するアルゴリズム
    # S: aaabaaaab
    # A: 921034210
    # 例えば、A[5] = 4だが、これは、S[0:4] == S[5:5+4] 
    # (Sの0文字目からと5文字目からは、4文字一致している(aaab)) ことを意味する。

    lenS = len(S)
    A = [0] * lenS
    i = 1; j = 0
    A[0] = lenS
    # i: 調査開始点
    # iを1文字目からlen(S)-1文字目まで左から順に動かしていく
    while i < lenS:
        # j: 何文字目まで一致するか(iからの距離)
        # 一致しなくなるまでjを左から右へ動かしていく
        while i + j < lenS and S[j] == S[i + j]:
            j += 1
        # 1文字も一致しない場合は調査開始点を一つ右にずらす
        if j == 0:
            i += 1
            continue

        A[i] = j

        # 例）S: momomosumomomomo
        # A[1] = 0, A[2] = 4 (A[0:4] == A[2:2+4] = "momo")

        # i=2の調査が終わった段階で、
        # S[3] = S[2 + 1] = S[1] = "o" 
        # で、A[3] = A[1] = 0（Sの1文字目からと3文字目からは一致しない）
        # のは明らかなので、i = 3の結果はi = 1の結果を流用して0とする。
        # つまり、A[3] = A[2 + 1] = A[1] = 0

        # 今回、i + j 文字目まで、一致するか調べたので、
        # A[i + 1] ~ A[i + j - 1] までの間で、計算結果を流用できるところは流用する
        # j <= k + A[k] となるようなkの場合、
        # j文字目以降は今回調べてないので一致するか本当に分からないので、流用をやめる
        # 今回の場合、
        # k = 1: 1 + A[1] = 1 + 0 = 1 < j = 4 なので、流用できる
        # k = 2: 2 + A[2] = 2 + 4 = 6 > j = 4 なので、流用できない
        # つなり、k=2となった瞬間、流用をせずにループを抜ける。
        k = 1
        while k + A[k] < j and i + k < lenS:
            A[i + k] = A[k]
            k += 1
        # 今回 1回 (=k-1回) 流用できた、つまり A[3] = A[2(=i) + 2(=k) - 1] まで確定したので、
        # 次は A[4] = A[i + k] から調べる
        i += k

        # また、k = 2 のとき、k + A[k] >= j となって流用を打ち切られたということは、
        # k + A[i + k] >= j  => A[i + k] >= j - k
        # A[4] は少なくとも j - k = 4 - 2 = 2 以上となることが確定する。
        # つまり、S[4:]とSは、少なくとも最初の2文字 (j-k文字) は一致する。
        # よって、A[4]を調べるときは、j=2から調査を開始すればよい。
        # （つまり、S[6]とS[4:][2]が一致しているか調べるところから始める）

        #             0123456
        # S         = momomosumomomomo
        # S[2:]     =   momosumomomomo   <- 5文字目が違う
        # S[2:][2:] =     mosumomomomo   <- 3文字目が違う
        # S[4:]     =     mosumomomomo   <- 3文字目が違う
        # S[4:][2:] =       sumomomomo   <- 1文字目が違う
        j -= k
    return A

def main():
    N = int(input())
    S = input()

    ans = 0

    # Z-algorithm で、最長共通接頭辞の長さを調べる。
    # Z-algorithm は、「S と S[i:|S|-1] の最長共通接頭辞の長さ」を記録するので、
    # S[1]以降の部分文字列同士の長さは、
    # S=S[i:]としてiをずらしながら最長共通接頭辞を調べることで分かる

    for i in range(N-1):
        A = z_algorithm(S[i:])
        # print(A)
        # 例えばS = ababa のとき、
        # A = [5, 0, 3, 0, 1] となる。
        # A[2] = 3 だが、範囲が被ってしまっているので、
        # A[i] > i の場合、一致する文字数はiまでにしておく。
        ans = max(ans, max([min(i, a) for i, a in enumerate(A)]))

    print(ans)

if __name__ == '__main__':
    main()