Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
def main():
    n = int(input())
    s = input().rstrip()
    dp = [0]*(n-1)
    ans = 0
    for i in range(1, n):
        for j in reversed(range(i-ans)):
            if s[i] == s[j]:
                dp[j] = 1
                if 0 < j:
                    dp[j] += dp[j-1]
                if i-j < dp[j]:
                    dp[j] = i-j
                if ans < dp[j]:
                    ans = dp[j]
            else:
                dp[j] = 0
    print(ans)

if __name__ == "__main__":
    main()


Fixed submission:
def check(x, N, S):
    candidate = set()
    for i in range(N - 2*x + 1):
        candidate.add(S[i:i+x])
        if S[i+x:i+2*x] in candidate:
            return True
    return False

def main():
    n = int(input())
    s = input().rstrip()
    l = 0
    r = n
    while l < r:
        mid = (l+r+1) // 2
        if check(mid, n, s):
            l = mid
        else:
            r = mid-1
    print((l+r+1)//2)

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
def main():
    n = int(input())
    s = input().rstrip()
    dp = [0]*(n-1)
    ans = 0
    for i in range(1, n):
        tmp = 0
        for j in reversed(range(i)):
            if s[i] == s[j]:
                dp[j] = 1
                if 0 < j:
                    dp[j] += dp[j-1]
                if i-j < dp[j]:
                    dp[j] = i-j
                if ans < dp[j]:
                    ans = dp[j]
                if tmp < dp[j]:
                    tmp = dp[j]
            else:
                dp[j] = 0
        if tmp + (n-i) <= ans:
            break
    print(ans)

if __name__ == "__main__":
    main()


Fixed submission:
def check(x, N, S):
    candidate = set()
    for i in range(N - 2*x + 1):
        candidate.add(S[i:i+x])
        if S[i+x:i+2*x] in candidate:
            return True
    return False

def main():
    n = int(input())
    s = input().rstrip()
    l = 0
    r = n
    while l < r:
        mid = (l+r+1) // 2
        if check(mid, n, s):
            l = mid
        else:
            r = mid-1
    print((l+r+1)//2)

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
def main():
    n = int(input())
    s = input().rstrip()
    dp = [0]*(n-1)
    ans = 0
    a = 1
    b = 1
    for k in range((n)*(n-1)//2):
        i = a
        j = b-k-1
        if s[i] == s[j]:
            dp[j] = 1
            if 0 < j:
                dp[j] += dp[j-1]
            if i-j < dp[j]:
                dp[j] = i-j
            if ans < dp[j]:
                ans = dp[j]
        else:
            dp[j] = 0
        if j == 0:
            a += 1
            b += a
    print(ans)

if __name__ == "__main__":
    main()


Fixed submission:
def check(x, N, S):
    candidate = set()
    for i in range(N - 2*x + 1):
        candidate.add(S[i:i+x])
        if S[i+x:i+2*x] in candidate:
            return True
    return False

def main():
    n = int(input())
    s = input().rstrip()
    l = 0
    r = n
    while l < r:
        mid = (l+r+1) // 2
        if check(mid, n, s):
            l = mid
        else:
            r = mid-1
    print((l+r+1)//2)

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
def main():
    n = int(input())
    s = input().rstrip()
    dp = [0]*(n-1)
    ans = 0
    i = 1
    while i < n:
        j = i-1
        while -1 < j:
            if s[i] == s[j]:
                dp[j] = 1
                if 0 < j:
                    dp[j] += dp[j-1]
                if i-j < dp[j]:
                    dp[j] = i-j
                if ans < dp[j]:
                    ans = dp[j]
            else:
                dp[j] = 0
            j -= 1
        i += 1
    print(ans)

if __name__ == "__main__":
    main()


Fixed submission:
def check(x, N, S):
    candidate = set()
    for i in range(N - 2*x + 1):
        candidate.add(S[i:i+x])
        if S[i+x:i+2*x] in candidate:
            return True
    return False

def main():
    n = int(input())
    s = input().rstrip()
    l = 0
    r = n
    while l < r:
        mid = (l+r+1) // 2
        if check(mid, n, s):
            l = mid
        else:
            r = mid-1
    print((l+r+1)//2)

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n = int(input())
    s = input()
    dp = [0]*(n-1)
    ans = 0
    for i in range(1, n):
        for j in reversed(range(i)):
            if s[i] == s[j]:
                dp[j] = 1
                if 0 < j:
                    dp[j] += dp[j-1]
                if i-j < dp[j]:
                    dp[j] = i-j
                if ans < dp[j]:
                    ans = dp[j]
            else:
                dp[j] = 0
    print(ans)

if __name__ == "__main__":
    main()


Fixed submission:
def check(x, N, S):
    candidate = set()
    for i in range(N - 2*x + 1):
        candidate.add(S[i:i+x])
        if S[i+x:i+2*x] in candidate:
            return True
    return False

def main():
    n = int(input())
    s = input().rstrip()
    l = 0
    r = n
    while l < r:
        mid = (l+r+1) // 2
        if check(mid, n, s):
            l = mid
        else:
            r = mid-1
    print((l+r+1)//2)

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
def main():
    n = int(input())
    s = input().rstrip()
    dp = [0]*(n-1)
    ans = 0
    for i in range(1, n):
        for j in reversed(range(i)):
            if s[i] == s[j]:
                dp[j] = 1
                if 0 < j:
                    dp[j] += dp[j-1]
                if i-j < dp[j]:
                    dp[j] = i-j
                if ans < dp[j]:
                    ans = dp[j]
            else:
                dp[j] = 0
    print(ans)

if __name__ == "__main__":
    main()


Fixed submission:
def check(x, N, S):
    candidate = set()
    for i in range(N - 2*x + 1):
        candidate.add(S[i:i+x])
        if S[i+x:i+2*x] in candidate:
            return True
    return False

def main():
    n = int(input())
    s = input().rstrip()
    l = 0
    r = n
    while l < r:
        mid = (l+r+1) // 2
        if check(mid, n, s):
            l = mid
        else:
            r = mid-1
    print((l+r+1)//2)

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n = int(input())
    s = input().rstrip()
    dp = [[0]*(i+1) for i in range(n)]
    ans = 0
    for i in range(1, n):
        for j in range(i):
            if s[i] == s[j]:
                dp[i][j] += 1
                if 0 < i and 0 < j:
                    dp[i][j] += dp[i-1][j-1]
                dp[i][j] = i-j if i-j < dp[i][j] else dp[i][j]
                ans = dp[i][j] if dp[i][j] > ans else ans
    print(ans)

if __name__ == "__main__":
    main()


Fixed submission:
def check(x, N, S):
    candidate = set()
    for i in range(N - 2*x + 1):
        candidate.add(S[i:i+x])
        if S[i+x:i+2*x] in candidate:
            return True
    return False

def main():
    n = int(input())
    s = input().rstrip()
    l = 0
    r = n
    while l < r:
        mid = (l+r+1) // 2
        if check(mid, n, s):
            l = mid
        else:
            r = mid-1
    print((l+r+1)//2)

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n = int(input())
    s = input().rstrip()
    dp = [[0]*(i+1) for i in range(n)]
    for i in range(1, n):
        for j in range(i):
            if s[i] == s[j]:
                dp[i][j] += 1
                if 0 < i and 0 < j:
                    dp[i][j] += dp[i-1][j-1]
                dp[i][j] = i-j if i-j < dp[i][j] else dp[i][j]
    print(max(max(dp, key=lambda x: max(x))))

if __name__ == "__main__":
    main()


Fixed submission:
def check(x, N, S):
    candidate = set()
    for i in range(N - 2*x + 1):
        candidate.add(S[i:i+x])
        if S[i+x:i+2*x] in candidate:
            return True
    return False

def main():
    n = int(input())
    s = input().rstrip()
    l = 0
    r = n
    while l < r:
        mid = (l+r+1) // 2
        if check(mid, n, s):
            l = mid
        else:
            r = mid-1
    print((l+r+1)//2)

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
def main():
    n = int(input())
    s = input().rstrip()
    dp = np.zeros((n, n), dtype=np.int64)
    for i in range(1, n):
        for j in range(i):
            if s[i] == s[j]:
                dp[i][j] += 1
                if 0 < i and 0 < j:
                    dp[i][j] += dp[i-1][j-1]
                dp[i][j] = i-j if i-j < dp[i][j] else dp[i][j]
    print(np.max(dp))

if __name__ == "__main__":
    main()

Fixed submission:
def check(x, N, S):
    candidate = set()
    for i in range(N - 2*x + 1):
        candidate.add(S[i:i+x])
        if S[i+x:i+2*x] in candidate:
            return True
    return False

def main():
    n = int(input())
    s = input().rstrip()
    l = 0
    r = n
    while l < r:
        mid = (l+r+1) // 2
        if check(mid, n, s):
            l = mid
        else:
            r = mid-1
    print((l+r+1)//2)

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n = int(input())
    s = input().rstrip()
    dp = [[0]*(i+1) for i in range(n)]
    for i in range(n):
        for j in range(i+1):
            if s[i] == s[j]:
                dp[i][j] += 1
                if 0 < i and 0 < j:
                    dp[i][j] += dp[i-1][j-1]
                dp[i][j] = min(i-j, dp[i][j])
    print(max(max(dp, key=lambda x: max(x))))

if __name__ == "__main__":
    main()

Fixed submission:
def check(x, N, S):
    candidate = set()
    for i in range(N - 2*x + 1):
        candidate.add(S[i:i+x])
        if S[i+x:i+2*x] in candidate:
            return True
    return False

def main():
    n = int(input())
    s = input().rstrip()
    l = 0
    r = n
    while l < r:
        mid = (l+r+1) // 2
        if check(mid, n, s):
            l = mid
        else:
            r = mid-1
    print((l+r+1)//2)

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n = int(input())
    s = input().rstrip()
    dp = [[0]*(i+1) for i in range(n)]
    for i in range(n):
        for j in range(i+1):
            if s[i] == s[j]:
                dp[i][j] += 1
                if 0 < i and 0 < j:
                    dp[i][j] += dp[i-1][j-1]
    ans = 0
    for i in range(n):
        for j in range(i+1):
            tmp = min(dp[i][j], i-j)
            ans = max(ans, tmp)
    print(ans)

if __name__ == "__main__":
    main()

Fixed submission:
def check(x, N, S):
    candidate = set()
    for i in range(N - 2*x + 1):
        candidate.add(S[i:i+x])
        if S[i+x:i+2*x] in candidate:
            return True
    return False

def main():
    n = int(input())
    s = input().rstrip()
    l = 0
    r = n
    while l < r:
        mid = (l+r+1) // 2
        if check(mid, n, s):
            l = mid
        else:
            r = mid-1
    print((l+r+1)//2)

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def Z_algo(S):
    n = len(S)
    LCP = [0]*n
    i = 1
    j = 0
    c = 0
    for i in range(1, n):
        if i+LCP[i-c] < c+LCP[c]:
            LCP[i] = LCP[i-c]
        else:
            j = max(0, c+LCP[c]-i)
            while i+j < n and S[j] == S[i+j]: j+=1
            LCP[i] = j
            c = i
    LCP[0] = n
    return LCP

def main():
    n = int(input())
    s = input().rstrip()
    ans = 0
    for i in range(n):
        lcp = Z_algo(s[i:])
        for j, l in enumerate(lcp):
            x = min(l, j)
            ans = max(ans, x)
    print(ans)

if __name__ == "__main__":
    main()

Fixed submission:
def check(x, N, S):
    candidate = set()
    for i in range(N - 2*x + 1):
        candidate.add(S[i:i+x])
        if S[i+x:i+2*x] in candidate:
            return True
    return False

def main():
    n = int(input())
    s = input().rstrip()
    l = 0
    r = n
    while l < r:
        mid = (l+r+1) // 2
        if check(mid, n, s):
            l = mid
        else:
            r = mid-1
    print((l+r+1)//2)

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n = int(input())
    s = input().rstrip()
    sets_l = [set() for _ in range(n)]
    sets_r = [set() for _ in range(n)]
    sets_l[0].add(s[0])
    for i in range(1, len(s)):
        #sets_l[i] = sets_l[i] | sets_l[i-1]
        for j in range(i+1):
            sets_l[i].add(s[j:i+1])
    sets_r[n-1].add(s[n-1:])
    for i in reversed(range(len(s)-1)):
        sets_r[i] = sets_r[i] | sets_r[i+1]
        for j in reversed(range(i, len(s))):
            sets_r[i].add(s[i:j+1])
    ans = 0
    for i in range(i, len(s)-1):
        for v in sets_l[i]:
            if v in sets_r[i+1]:
                if ans < len(v):
                    ans = len(v)
    print(ans)

if __name__ == "__main__":
    main()

Fixed submission:
def check(x, N, S):
    candidate = set()
    for i in range(N - 2*x + 1):
        candidate.add(S[i:i+x])
        if S[i+x:i+2*x] in candidate:
            return True
    return False

def main():
    n = int(input())
    s = input().rstrip()
    l = 0
    r = n
    while l < r:
        mid = (l+r+1) // 2
        if check(mid, n, s):
            l = mid
        else:
            r = mid-1
    print((l+r+1)//2)

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n = int(input())
    s = input().rstrip()
    sets_l = [set() for _ in range(n)]
    sets_r = [set() for _ in range(n)]
    sets_l[0].add(s[0])
    for i in range(1, len(s)):
        sets_l[i] = sets_l[i] | sets_l[i-1]
        for j in range(i+1):
            sets_l[i].add(s[j:i+1])
    sets_r[n-1].add(s[n-1:])
    for i in reversed(range(len(s)-1)):
        sets_r[i] = sets_r[i] | sets_r[i+1]
        for j in reversed(range(i, len(s))):
            sets_r[i].add(s[i:j+1])
    ans = 0
    for i in range(i, len(s)-1):
        for v in sets_l[i]:
            if v in sets_r[i+1]:
                if ans < len(v):
                    ans = len(v)
    print(ans)

if __name__ == "__main__":
    main()

Fixed submission:
def check(x, N, S):
    candidate = set()
    for i in range(N - 2*x + 1):
        candidate.add(S[i:i+x])
        if S[i+x:i+2*x] in candidate:
            return True
    return False

def main():
    n = int(input())
    s = input().rstrip()
    l = 0
    r = n
    while l < r:
        mid = (l+r+1) // 2
        if check(mid, n, s):
            l = mid
        else:
            r = mid-1
    print((l+r+1)//2)

if __name__ == "__main__":
    main()