Problem:


Score : 500 points

Problem Statement

Given is a string S of length N.

Find the maximum length of a non-empty string that occurs twice or more in S as contiguous substrings without overlapping.

More formally, find the maximum positive integer len such that there exist integers l_1 and l_2 ( 1 \leq l_1, l_2 \leq N - len + 1 ) that satisfy the following:

l_1 + len \leq l_2

S[l_1+i] = S[l_2+i] (i = 0, 1, ..., len - 1)

If there is no such integer len, print 0.

Constraints

2 \leq N \leq 5 \times 10^3

|S| = N

S consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the maximum length of a non-empty string that occurs twice or more in S as contiguous substrings without overlapping. If there is no such non-empty string, print 0 instead.

Sample Input 1

5
ababa

Sample Output 1

2

The strings satisfying the conditions are: a, b, ab, and ba. The maximum length among them is 2, which is the answer.
Note that aba occurs twice in S as contiguous substrings, but there is no pair of integers l_1 and l_2 mentioned in the statement such that l_1 + len \leq l_2.

Sample Input 2

2
xy

Sample Output 2

0

No non-empty string satisfies the conditions.

Sample Input 3

13
strangeorange

Sample Output 3

5



Sample input:
5
ababa


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()

def z_algo(S):
    N = len(S)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j] and i != j:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A

ans = 0
for i in range(n-1):
	res = z_algo(s[i:])
	ans = max(ans, max(res[1:]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# suffix array
# z-algorithm
# rolling-hash
# dp
n = int(input())
s = input()

# z-algorithm
# i左端
# j iからの距離
# k i-i+jの間を進みながら比較
ans = 0
for num in range(n - 1):
    S = s[num:]
    A = [0] * (n - num)
    A[0] = n - num
    i = 1
    j = 0
    while i < n - num:
        while i + j < n - num and S[j] == S[i + j]:
            j += 1
        A[i] = j
        ans = max(ans, min(i, j))
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < n - num and k + A[k] < j:
            A[i + k] = A[k]
            ans = max(ans, min(k, A[k]))
            k += 1
        i += k
        j -= k
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def zalgo(S):
    # SとS[i:n]のlcpの長さを記録した配列を返す
    n = len(S)
    A = [0] * n
    j = 0
    for i in range(1, n):
        if i+A[i-j] < j+A[j]:
            A[i] = A[i-j]
        else:
            k = max(0, A[j]-i+j)
            while i+k < n and S[k] == S[i+k]:
                k += 1
            A[i] = k
            j = i
    A[0] = n
    return A


n = int(input())
S = input()
l = 0
for i in range(n):
    A = zalgo(S[i:])
    B = [min(j, a) for j, a in enumerate(A)]
    l = max(l, max(B))
print(l)

Submission status: Time Limit Exceeded

Solution code:
# 解説

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

    dp = [[0] * N for _ in range(N)]
    ans = 0
    for i in range(N - 1, -1, -1):
        for j in range(N - 1, -1, -1):
            if s[i] == s[j]:
                if i + 1 < N and j + 1 < N:
                    dp[i][j] = min(dp[i + 1][j + 1] + 1, j - i)
                    ans = max(ans, dp[i][j])
                else:
                    dp[i][j] = 1
            else:
                dp[i][j] = 0
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())

n = INT()
s = STR()
ans = 0
for i in range(n): #開始地点
    for j in range(1, (n - i) // 2 + 1): #長さ
        t = s[i:i + j]
        for k in range(i + j, n - j + 1):
            if s[k:k + j] == t:
                ans = max(ans, j)
                break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def ok(k):
    # 長さkの連続部分列で重ならずに2回以上現れるものがある
    for i in range(n-2*k+1):
        X = S[i:i+k]
        for j in range(i+k, n-k+1):
            Y = S[j:j+k]
            if X == Y:
                return True
    return False


n = int(input())
S = list(input())
# 二分探索でTrueになる最大のkを求める
l, r = 0, n+1
while r-l > 1:
    c = (l+r)//2
    if ok(c):
        l = c
    else:
        r = c
print(l)

Submission status: Time Limit Exceeded

Solution code:
from collections import *
from heapq import *
import sys

sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]
dij = [(1, 0), (-1, 0), (0, 1), (0, -1)]

def main():
    n=II()
    s=SI()
    for w in range(n//2,0,-1):
        for i in range(n-w):
            t=s[i:i+w]
            if t in s[i+w:]:
                print(w)
                exit()
    print(0)

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())
S = input()

def exists(length):
    que = deque()
    V = set()
    T = S[:length]
    que.append(T)
    for s in S[length:]:
        if len(que) >= length:
            V.add(que.popleft())
        T = T[1:] + s
        if T in V:
            return True
        que.append(T)
    return False

for i in range(1, (N + 1) // 2 + 1)[::-1]:
    if exists(i):
        print(i)
        exit()

print(0)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())
S = input()

def exists(length):
    que = deque()
    V = set()
    T = S[:length]
    que.append(T)
    for s in S[length:]:
        if len(que) >= length:
            V.add(que.popleft())
        T = T[1:] + s
        if T in V:
            return True
        que.append(T)
    return False

for i in range(1, N + 1)[::-1]:
    if exists(i):
        print(i)
        exit()

print(0)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())
S = input()

def exists(length):
    que = deque()
    V = set()
    for left in range(N - length + 1):
        if left > length - 1:
            V.add(que.popleft())
        T = S[left: left + length]
        if T in V:
            return True
        que.append(T)
    return False

for i in range(1, N + 1)[::-1]:
    if exists(i):
        print(i)
        exit()

print(0)

Submission status: Time Limit Exceeded

Solution code:
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()

Submission status: Time Limit Exceeded

Solution code:
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()

Submission status: Time Limit Exceeded

Solution code:
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()

Submission status: Time Limit Exceeded

Solution code:
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()

Submission status: Time Limit Exceeded

Solution code:
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()

Submission status: Time Limit Exceeded

Solution code:
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()

Submission status: Time Limit Exceeded

Solution code:
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()

Submission status: Time Limit Exceeded

Solution code:
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()

Submission status: Time Limit Exceeded

Solution code:
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()

Submission status: Time Limit Exceeded

Solution code:
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()

Submission status: Time Limit Exceeded

Solution code:
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()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
substrs = [[] for _ in range(n//2+1)]
ans = 0
for i in range(n):
    ma = min(i, n-i)
    #clipping
    for j in range(ans+1, ma+1):
        substrs[j].append(s[i-j:i])
    
    #matching
    for j in range(ma, ans, -1):
        if s[i:i+j] in substrs[j]:
            ans = j
            break
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:

import sys
import math
import fractions
import bisect
import queue
import heapq
import collections
import itertools
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''
1行のint=====================================
N, K = map(int, input().split())
N, M = map(int, input().split())
A, B = map(int, input().split())

H, W = map(int, input().split())

L, R = map(int, input().split())

1行のstring=================================
S, T = input().split()

1行の整数配列================================
P = list(map(int,input().split()))

A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
D = list(map(int,input().split()))

L = list(map(int,input().split()))
R = list(map(int,input().split()))

T = list(map(int,input().split()))

改行あり整数==================================
X = []
Y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    X.append(x1)
    Y.append(y1)

A = []
for i in range(N):
    a=int(input())
    A.append(a)

Pair = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    Pair.append((x1, y1))
    
2次元整数配列=====================================
A = []
for i in range(N):
    tmp = list(map(int,input().split()))
    A.append(tmp)


N行M列の初期化====================================
dp = [[VAL] * RETU for i in range(GYO)]

'''


        
N = int(input())
S = input()

sub = {}

for i in range(len(S)):
    for j in range(i, len(S)):
        idxs = (i, j)
        s = S[i:j+1]

        if s not in sub:
            sub[s] = [idxs]
        else:
            sub[s].append(idxs)

ans = 0
for d in sub:

    if len(d) == 1:
        continue
    else:
        s1 = sub[d][0][0]
        g1 = sub[d][0][1]
        
        s2 = sub[d][-1][0]
        g2 = sub[d][-1][1]

        if g1 < s2 or g2 < s1:
            ans = max(ans, len(d))


print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()

dp = [[0]*(n+1) for i in range(n+1)]

ans = 0
for i in range(n-1, -1, -1):
    for j in range(n-1, i, -1):
        if s[i] == s[j]:
            dp[i][j] = dp[i+1][j+1] + 1
        else:
            dp[i][j] = 0
        ans = max(ans, min(dp[i][j], j-i))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()

dp = [[0 if max(i,j) == n else -1 for i in range(n+1)] for j in range(n+1)]

ans = 0
for i in range(n-1, -1, -1):
    for j in range(n-1, i, -1):
        if s[i] == s[j]:dp[i][j] = dp[i+1][j+1] + 1
        else: dp[i][j] = 0
        ans = max(ans, min(dp[i][j], j-i))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq


def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def main():
    r = solve()
    print(r)

def solve():
    N = iip(False)
    S = input()
    S = [ord(i) for i in S]

    ln = len(S)

    def same(l):
        for l1 in range(0, ln-l):
            h1t = 0
            h2t = 0
            b1 = 26
            b2 = 27
            k1 = 1
            k2 = 1
            for i in range(l): # 検索対象のhashを作る
                ht = S[l1 + l - 1 - i]
                h1t += ht * k1
                h2t += ht * k2
                k1 *= b1
                k2 *= b2

                h1t %= mod2
                h2t %= mod2
                k1 %= mod2
                k2 %= mod2

            h1s = 0
            h2s = 0
            k1 = 1
            k2 = 1
            for i in range(l): #最初の比較対象hashを作る
                if l1 + l + l - 1 >= ln:
                    return False
                ht = S[l1 + l + l - 1 - i]
                h1s += ht*k1
                h2s += ht*k2

                k1 *= b1
                k2 *= b2

                h1s %= mod2
                h2s %= mod2
                k1 %= mod2
                k2 %= mod2
                if h1t == h1s and h2t == h2s:
                    return True

            for i in range(l1+l+l, ln):
                h1s = h1s * b1 + S[i] - S[i-l]* power(b1, l, mod2)
                h2s = h2s * b2 + S[i] - S[i-l]* power(b2, l, mod2)
                if h1t == h1s and h2t == h2s:
                    return True

        return False


    mn = 0
    mx = ln // 2+1
    while mx - mn > 1:
        l = (mx+mn) // 2

        is_same = same(l)

        if is_same:
            mn = l
        else:
            mx = l

    #print(mn, mx)
    return mn


#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1)) % mod_


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7
from collections import deque
import heapq


def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def main():
    r = solve()
    print(r)

def solve():
    N = iip(False)
    S = input()
    S = [ord(i) for i in S]

    ln = len(S)

    def same(l):
        for l1 in range(0, ln-l):
            l2 = l1 + l
            same_num = 0

            while l2 <= ln - l:
                if S[l2+same_num] == S[l1+same_num]:
                    same_num += 1
                    if same_num == l:
                        return True
                else:
                    same_num = 0
                    l2 += 1
        return False


    mn = 0
    mx = ln // 2+1
    while mx - mn > 1:
        l = (mx+mn) // 2

        is_same = same(l)

        if is_same:
            mn = l
        else:
            mx = l

    #print(mn, mx)
    return mn


#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p - 1)) % mod


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7
from collections import deque
import heapq


def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def main():
    r = solve()
    print(r)

def solve():
    N = iip(False)
    S = input()
    S = [i for i in S]

    ln = len(S)

    def same(l):
        for l1 in range(0, ln-l):
            l2 = l1 + l
            same_num = 0

            while l2 <= ln - l:
                if S[l2+same_num] == S[l1+same_num]:
                    same_num += 1
                    if same_num == l:
                        return True
                else:
                    same_num = 0
                    l2 += 1
        return False


    mn = 0
    mx = ln // 2+1
    while mx - mn > 1:
        l = (mx+mn) // 2

        is_same = same(l)

        if is_same:
            mn = l
        else:
            mx = l

    #print(mn, mx)
    return mn


#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p - 1)) % mod


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7
from collections import deque
import heapq


def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def main():
    r = solve()
    print(r)

def solve():
    N = iip(False)
    S = input()
    S = [i for i in S]

    ln = len(S)

    def same(l):
        for l1 in range(0, ln-l):
            target = S[l1:l1+l]
            for l2 in range(l1+l, ln - l+1):
                same_num = 0
                for t in target:
                    if S[l2+same_num] == t:
                        same_num += 1
                    else:
                        break
                else:
                    return True
        return False

    mn = 0
    mx = ln // 2+1
    while mx - mn > 1:
        l = (mx+mn) // 2

        is_same = same(l)

        if is_same:
            mn = l
        else:
            mx = l

    #print(mn, mx)
    return mn


#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p - 1)) % mod


if __name__ == "__main__":
    main()