Buggy python submission (verdict: Time Limit Exceeded):

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

    dp = [[0 for _ in range(N+10)] for _ in range(N+10)]
    ans = 0
    for i in reversed(range(N)):
        for j in reversed(range(i+1,N)):
            if S[i] != S[j]:
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i+1][j+1] + 1
            if i >= j: continue
            tmp = min(dp[i][j], j-i)
            ans = max(ans, tmp)


    print(ans)

if __name__ == "__main__":
    main()

Fixed submission:

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

    """
    他言語ならこれで行けるはずだが、pythonだとTLE
    dp = [[0 for _ in range(N+10)] for _ in range(N+10)]
    for i in reversed(range(N)):
        for j in reversed(range(i+1,N)):
            if S[i] != S[j]:
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i+1][j+1] + 1
            if i >= j: continue
            tmp = min(dp[i][j], j-i)
            ans = max(ans, tmp)
    """
    i = j = 0

    while  j <= N-1:
        # 頭から見ていき、部分文字列が、その後ろのどこかにあれば範囲を広げる。かぶってはいけないのでj-iが最大
        if S[i:j] in S[j:]:
            ans = max(ans, j-i)
            j += 1
        else:
            i += 1
        

    print(ans)

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):

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

    dp = [[0 for _ in range(N+10)] for _ in range(N+10)]
    ans = 0
    for i in reversed(range(N)):
        for j in reversed(range(N)):
            if S[i] != S[j]:
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i+1][j+1] + 1
            if i >= j: continue
            tmp = min(dp[i][j], j-i)
            ans = max(ans, tmp)


    print(ans)

if __name__ == "__main__":
    main()

Fixed submission:

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

    """
    他言語ならこれで行けるはずだが、pythonだとTLE
    dp = [[0 for _ in range(N+10)] for _ in range(N+10)]
    for i in reversed(range(N)):
        for j in reversed(range(i+1,N)):
            if S[i] != S[j]:
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i+1][j+1] + 1
            if i >= j: continue
            tmp = min(dp[i][j], j-i)
            ans = max(ans, tmp)
    """
    i = j = 0

    while  j <= N-1:
        # 頭から見ていき、部分文字列が、その後ろのどこかにあれば範囲を広げる。かぶってはいけないのでj-iが最大
        if S[i:j] in S[j:]:
            ans = max(ans, j-i)
            j += 1
        else:
            i += 1
        

    print(ans)

if __name__ == "__main__":
    main()

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

dp = [[0 for _ in range(N+10)] for _ in range(N+10)]
ans = 0
for i in reversed(range(N)):
    for j in reversed(range(N)):
        if S[i] != S[j]:
            dp[i][j] = 0
        else:
            dp[i][j] = dp[i+1][j+1] + 1
        if i >= j: continue
        tmp = min(dp[i][j], j-i)
        ans = max(ans, tmp)


print(ans)


Fixed submission:

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

    """
    他言語ならこれで行けるはずだが、pythonだとTLE
    dp = [[0 for _ in range(N+10)] for _ in range(N+10)]
    for i in reversed(range(N)):
        for j in reversed(range(i+1,N)):
            if S[i] != S[j]:
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i+1][j+1] + 1
            if i >= j: continue
            tmp = min(dp[i][j], j-i)
            ans = max(ans, tmp)
    """
    i = j = 0

    while  j <= N-1:
        # 頭から見ていき、部分文字列が、その後ろのどこかにあれば範囲を広げる。かぶってはいけないのでj-iが最大
        if S[i:j] in S[j:]:
            ans = max(ans, j-i)
            j += 1
        else:
            i += 1
        

    print(ans)

if __name__ == "__main__":
    main()