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:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque

ans = 0

def check(ind, num, s, left, right):

    if right - left <= 1:
        global ans
        # print(left, right)
        ans = max(ans, left)
        return

    half = (left + right) // 2

    flg = 1

    for j in range(ind + half, num - half + 1):
        for k in range(half):
            if ind + k >= j or j + k >= num:
                break
            if s[ind + k] != s[j + k]:
                break
        else:
            # print(left, half, right, 'eee')
            check(ind, num, s, half, right)
            flg = 0
        # print(left, half, right)

    if flg:
        check(ind, num, s, left, half)

def main():
    global ans
    num = int(input())
    s = list(input())

    for i in range(num):
        if num - i <= ans:
            break
        left, right = ans, num // 2 + 1
        # print(left, right, 'yyy')
        check(i, num, s, left, right)
    print(ans)




if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd

N = int(input())
S = input()
r = 0
moji = dd(int)
basyo = dd(list)
for i in range(N):
	for j in range(N):
		ito = S[i:j+1]
		if ito in S and len(ito):
			if i in basyo[ito]: continue
			moji[ito] += 1
			basyo[ito].extend(range(i, j+1))

okbokujo = dd(int)
maxi = 0
for i in moji:
	if moji[i] > 1:
		maxi = max(maxi, len(i))
print(maxi)

Submission status: Time Limit Exceeded

Solution code:
from string import ascii_lowercase
N=int(input());S=input();l=[(i,i)for i in range(N)];m=0
while l:
    p,q=l.pop()
    m=max(m,q-p)
    if q+1<N and S.count(S[p:q+1])>1:l.append((p,q+1))
print(m)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline
exit = sys.exit


def main():
    N = int(input().strip())
    S = input().strip()
    half_N = N//2
    cand = []
    flag = True
    cappend = cand.append
    for i in range(N):
        tmp = []
        tappend = tmp.append
        for j in range(1, N-i-1):
            if S[i] == S[i+j]:
                flag = False
                tappend(i+j)
        cappend(tmp)
    if flag:
        print(0)
        exit()

    for length in range(1, N//2+1):
        flag = True
        new_cand = []
        ncappend = new_cand.append
        for i in range(N-length):
            tmp = []
            now_check = S[i+length]
            tappend = tmp.append
            for c in cand[i]:
                if i + length >= c or c + length >= N:
                    continue
                if S[c+length] == now_check:
                    flag = False
                    tappend(c)
            ncappend(tmp)
        cand = new_cand
        if flag:
            print(length)
            exit()

    print(length+1)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = int(input())
S = input()
ans = 0
D = Counter(S)
id = 0
dic = {}
for k in D.keys():
    dic[k] = id
    id += 1
m = 0
OB = [-1]*N
for i in range(N):
    if D[S[i]]<=1:
        pass
    else:
        OB[i] = dic[S[i]]
        m = max(m,dic[S[i]])
SSS = []
for j in range(m+1):
    SS = [i for i in range(N) if OB[i]==j]
    SSS.append(SS)
for n in range(len(SSS)):
    lss = len(SSS[n])
    for i in range(lss):
        for j in range(lss):
            if i==j or ans>SSS[n][j]-SSS[n][i] or ans>N-SSS[n][j]:
                continue
            id = 0
            while True:

                if SSS[n][i]+id>=N or SSS[n][j]+id>=N or SSS[n][i]+id>=SSS[n][j]:
                    break
                if S[SSS[n][i]+id]==S[SSS[n][j]+id]:
                    id += 1
                else:
                    break
            ans = max(ans,id)


print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
u = set()
k = [0]
for x in range(1, n // 2 + 1):
    for _ in range(x):
        for y in range(n//x):
            t = s[y*x+_:y*x+x+_]
            if t in u:
                continue
            u.add(t)
            if t in s.replace(t, '', 1):
                k.append(len(t))


print(max(k))

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(n//2,-1,-1):
    for j in range(n - i - i + 1):
        if s[j:j+i] in s[j+i:]:
            ans = i
            break
    if ans != 0:
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n1 = int(input())
s1 = input()

r1 = 0
for i1 in range (n1):
    for i2 in range((n1 - i1) // 2):
        if s1[i1:((n1 - i1) // 2) + i1 - i2] in s1[((n1 - i1) // 2) + i1 - i2:]:
            if ((n1 - i1) // 2) - i2 > r1:
                r1 = ((n1 - i1) // 2) - i2
            break

print(r1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections


def main():
    n = int(sys.stdin.readline().strip())
    s = sys.stdin.readline().strip()
    # s = 'strangeorange'

    index_sets = [set() for _ in range(26)]
    pointers = []

    longest = 0
    for i in range(len(s)):
        c = s[i]
        order = ord(c) - ord('a')
        index_set = index_sets[order]
        next_pointers = []
        for _ in range(len(pointers)):
            cur, length, origin = pointers.pop()
            if s[cur+1] == c and cur+1 != origin:
                next_pointers.append([cur+1, length+1, origin])
                longest = max(longest, length+1)
        pointers = next_pointers

        for index in index_set:
            longest = max(longest, 1)
            pointers.append([index, 1, i])
        index_sets[order].add(i)

    print(longest)


main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
f1 = False
t = dict()
for z in range(n):
    t[s[z]] = t.get(s[z],0) + 1
    if t[s[z]] >= 2:
        f1 = True
        break

for i in range(n//2,1,-1):
    for j in range(n-2*i+1):
        for k in range(j+i,n-i+1):
            if (s[j:j+i] == s[k:k+i]):
                print(i)
                exit(0)
if f1:
    print(1)
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

N = int(input())
S = input()
ans = 0
found = False
for l in range(N//2, 0, -1):
    checked = defaultdict(bool)
    for i in range(N-(2*l)+1):
        target = S[i:i+l]
        if checked[target]: continue
        if target in S[i+l:]:
            ans = l
            found = True
        else:
            checked[target] = True
        if found: break
    if found: break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
ans = 0
for i in range(N-1):
  for j in range(i+1,N):
    S1 = S[i:j]
    S2 = S[j:]
    tmp = 0
    M = min(j-i,N-j)
    for k in range(M):
      if S1[k] == S2[k]:
        tmp += 1
      else:
        break
    ans = max(tmp,ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
ans = 0
for i in reversed(range(N)):
  for j in range(N):
    if (j + i) <= N and S.count(S[j:j+i]) == 2:
      ans = i
      print(ans)
      exit()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=input()
k=[]
p=[]
ans=0

for i in range(N):
    for j in range(i+1,N):
        if (S[i:j] in k):
            a=k.index(S[i:j])
            if (p[a][0]>=j) or (p[a][1]<=i):
                ans=max(ans,j-i)
        else:
            k.append(S[i:j])
            p.append([i,j])
    if (S[i:] in k):
        a=k.index(S[i:])
        if (p[a][0]>=N) or (p[a][1]<=i):
            ans=max(ans,N-i)
    else:
        k.append(S[i:])
        p.append([i,N])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()

ans = 0
for i in range(1, N):
    if ans >= i or ans >= N - i:
        continue
    tmp = 0
    for j in range(N - i):
        if S[j] == S[i + j]:
            if tmp < i:
                tmp += 1
            else:
                continue
            if tmp > ans:
                ans = tmp
        else:
            tmp = 0

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
ans = 0
count = 0
maximum = 0

for i in range(n):
	for j in range(i+1,n):
		if s[i] == s[j]:
			i_dash = i
			j_dash = j
			while True:
				if i_dash == j or j_dash == n:
					break
				elif j_dash - i_dash < maximum:
					break

				if s[i_dash] == s[j_dash]:
					count+=1
				else:
					break
				i_dash += 1
				j_dash += 1
			if ans < count:
				ans = count
			count = 0
			maximum = ans

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
s = set()
res = 0
for i in range(N):
  for j in range(i, N):
    if j - i + 1 > N // 2:
      break
    p = S[i: j + 1]
    if p in s:
      res = max(res, len(p))
    else:
      s.add(p)
print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n=int(input())
s=input()

dic=defaultdict(list)
ans=0
for i in range(n-1):
    if (n-i)<=ans:
        break
    for j in range(i+1,n+1):
        ss=s[i:j]
        if dic[ss]==[]:
            dic[ss]+=[j]
            continue
    
        elif max(dic[ss])<=i:
            dic[ss]+=[j]
        if len(dic[ss])>=2 and len(ss)>ans:
            ans=len(ss)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
    def input():
        return sys.stdin.readline()[:-1]
    N = int(input())
    S = [ord(x) for x in input()] + [-1]
    ans = 0
    for s in range(N-1):
        for e in range(s+1,N):
            if S[s] == S[e]:
                k = 0
                while s+k < e and e+k < N and S[s+k] == S[e+k]:
                    k += 1
                    if e+k == N:
                        break
                ans = max(ans,k)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline
exit = sys.exit
def main():
    N = int(input().strip())
    S = input().strip()
    half_N = N//2
    cand = []
    flag = True
    for i in range(N):
        tmp = []
        for j in range(1, N-i-1):
            if S[i] == S[i+j]:
                flag = False
                tmp.append(i+j)
        cand.append(tmp)
    if flag:
        print(0)
        exit()

    for length in range(1, N//2+1):
        flag = True
        new_cand = []
        for i in range(N-length):
            tmp = []
            now_check = S[i+length]
            for c in cand[i]:
                if i + length >= c or c + length >= N:
                    continue
                if S[c+length] == now_check:
                    flag = False
                    tmp.append(c)
            new_cand.append(tmp)
        cand = new_cand
        if flag:
            print(length)
            exit()

    print(length+1)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy
n = int(input())

s = input()

sl = set(s)

ans = 0

f = True

if len(s) == len(sl):
    f = False

d = {}
que = []

for i in sl:
    d[i] = []

for i,x in enumerate(s):
    d[x].append(i)

for i in d.values():
    que.append(i)

while f:
    ans += 1
    prev = copy.deepcopy(que)
    que = []

    for x in prev:
        for i in sl:
            d[i] = []
        for y in x:
            if y + ans >= n:
                continue
            d[s[y + ans]].append(y)

        for y in d.values():
            if len(y) > 1:
                que.append(y)
    if len(que) == 0:
        break

    if ans + 1 > len(s)//2:
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# A, B = [int(i) for i in input().split(" ")]
# A = int(input())
# As = [int(i) for i in input().split(" ")]
# Ss = ["".join(sorted(input())) for _ in range(N)]
N = int(input())
S = input()
class Node(dict):
  def __init__(self, v=-1):
    self.value = v

root = Node()
def insert(i, word):
  node, depth, branch = root, 0, False
  for j, c in enumerate(word):
    if c not in node:
       node[c] = Node(i + j)
       branch = True
    elif not branch and node[c].value < i:
      depth += 1 
    node = node[c]
  return depth
ans = 0
for i in range(N):
  ans = max(ans, insert(i, S[i: ]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs,heapq as hq
sys.setrecursionlimit(100000)
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def search(a,n):
    se = dict()
    data = []
    for i in range(0,len(a)-n+1):
        kkk = a[i:i+n]
        kkk = "".join(kkk)
        if In(kkk,data):
            for j in range(len(se[kkk])):
                if se[kkk][j] <= i-n:
                    return True
            else:
                se[kkk].append(i)
        else:
            bs.insort(data,kkk)
            se[kkk] = [i]
    return False
def solver():
    n = onem()

    s = list(input())
    l = 0
    r = n//2
    for i in range(n):
        mid = -(-(l+r)//2)
        ans = search(s,mid)
        if l == mid:
            break
        if ans:
            l = mid
        else:
            r = mid-1
    print(l)




solver()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
from bisect import bisect_left

def hantei(mid, s, suffix):
    # print(mid, s, suffix)
    for i in range(n - mid + 1):
        tmp = (s[i:i+mid], i)
        idx = bisect_left(suffix, tmp)

        # if mid == 4:
        #     print(tmp, idx)
        flag = True
        while(flag):
            tgt = suffix[idx]
            # print(tgt)
            if tgt[0].startswith(tmp[0]):
                if tgt[1] >= i + mid:
                    return True
                else:
                    idx += 1
                    if idx >= n:
                        flag = False
            else:
                flag = False

n = getN()
s = input().strip()

suffix = []

for i in range(n):
    suffix.append((s[i:], i))

suffix.sort()

mn = 0
mx = n // 2 + 1
while(mx-mn>1):
    mid = (mx + mn) // 2
    is_succ = hantei(mid, s, suffix)
    if is_succ:
        mn = mid
    else:
        mx = mid

if hantei(mx, s, suffix):
    print(mx)
else:
    print(mn)

"""
17
aaaaaaaaaaaaaaaaa -> 8
10
absoabsoab -> 4
6
abcabc -> 3
10
abcdefghij -> 0
15
rangerangerange -> 5
2
xx -> 1
2
xy -> 0
12
abcdxxxxabcd -> 4

14
abcxxxxxxxxabc
3????????????????
"""

Submission status: Time Limit Exceeded

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

ans = 0

while ans <= len(s)//2:
    prev_s = ''
    for i in range(1, len(s)//2+1):
        if s[:i] in s[i:]:
            prev_s = s[:i]
        else:
            ans = max(ans, len(prev_s))
            break
    else:
        ans = max(ans, len(prev_s))
    s = s[1:]
    if len(s) == 1:
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
input()
s = input()
ls = list(s)
cols = Counter(ls)
# ２個以上ある文字のリスト作成
dbls =[]
for k, v in cols.items():
  if v >= 2:
    dbls.append(k)

left = 0
right = 0
word = ""
ans = 0
# 順番に見ていく

while right < len(s):
  if s[right] in dbls:
    word += s[right]
    if s[right+1:].find(word) >= 0:
      ans = max(ans, len(word))
      right += 1
    else:
      word = ""
#      left = max(left + 1, right)
      left += 1
      right = left
  else:
    word = ""
#    left = max(left + 1, right)
    left += 1
    right = left

print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
for j in range(n):
    for i in range(j + ans):
        while (i + ans < n) & (i + ans < j):
            if (s[i:i+ans+1] == s[j:j+ans+1]):
                ans += 1
            else:
                break
print(ans)

Submission status: Time Limit Exceeded

Solution code:

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


try_no = N // 2

ans = 0

for i in range(1, try_no+1):
    for ii in range(N//i+1): 
        chk1 = S[ii:ii+i]
        for iii in range(i+ii, N-i+1):
            chk2 = S[iii:iii+i]
            if chk1 == chk2:
                ans = i

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline
exit = sys.exit
N = int(input().strip())
S = input().strip()
half_N = N//2
cand = []
flag = True
for i in range(N):
    tmp = []
    for j in range(1, N-i-1):
        if S[i] == S[i+j]:
            flag = False
            tmp.append(i+j)
    cand.append(tmp)
if flag:
    print(0)
    exit()

for length in range(1, N//2+1):
    flag = True
    new_cand = []
    for i in range(N-length):
        tmp = []
        now_check = S[i+length]
        for c in cand[i]:
            if i + length >= c or c + length >= N:
                continue
            if S[c+length] == now_check:
                flag = False
                tmp.append(c)
        new_cand.append(tmp)
    cand = new_cand
    if flag:
        print(length)
        exit()

print(length+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
N = int(input())
S = input()

ans_max = N//2 + 1

ans = [0] * N

for j in range(N-1):
    if S[j] in S[j+1:]:
        ans[j] += 1

if max(ans) == 0:
    print(0)
    sys.exit()

for k in range(2, ans_max):
    for j in range(N-k):
        if ans[j] + 1 == k:
            if S[j:j+k] in S[j+k:]:
                ans[j] += 1


print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = list(input())
mx = 0

for i in range(N-1):
    J = (N-i+1)//2 + 1
    for j in range(J):
        if j == 0:
            target = S[i]
        else:
            target = "".join(S[i:i+j+1])
        if target in "".join(S[i+j+1:]):
            mx = max(mx, len(target))

print(mx)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == "__main__":
    N = int(input())
    S = input()

    for i in range(N//2, 0, -1):
        if N-i*2 == 0:
            tmp = S[i:]
            if tmp.find(S[:i]) != -1:
                print(i)
                exit()
        else:
            for index in range(N-i*2):
                # 仮の文字列の生成
                tmp = S[index+i:]
                if tmp.find(S[index:index+i]) != -1:
                    print(i)
                    exit()

    print('0')

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()

def find_longest_substr(s1, s2):
    for length in range(len(s2), 0, -1):
        for p0 in range(len(s2) - length + 1):
            substr = s2[p0:(p0 + length)]
            if substr in s1:
                return(substr)
    return ""

ans = 0
for i in range(1, N):
    ans = max(len(find_longest_substr(S[0:i], S[i:N])), ans)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()

S_dict = {}
for i, s in enumerate(list(S)):
    if s in S_dict:
        S_dict[s].append(i)
    else:
        S_dict[s] = [i]
#print(S_dict)

S_set = set()
for nums in S_dict.values():
    for i, a in enumerate(nums):
        for b in nums[i+1:]:
            S_set.add((a, b))
#print(S_set)
#print("---")

ans = 0
for a, b in sorted(S_set):
    i = 0
    if not (a, b) in S_set:
        continue
    while 1:
        #print(i, a+i, b+i)
        if (a+i, b+i) in S_set and a+i < b:
            S_set.discard((a+i, b+i))
            i += 1
        else:
            break
    ans = max(ans, i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
n=int(input())
s=input()
count=0
mojiretu=defaultdict(tuple)
for i in range(n-1):
    for j in range(i+1,n+1):
        if mojiretu[s[i:j]]:
            if j <= mojiretu[s[i:j]][0] or mojiretu[s[i:j]][1]<=i:
                count=max(count,j-i)
        else:mojiretu[s[i:j]]=(i,j)
# while True:
#     for i in range(n)
print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n=int(input())
s=input()

dic=defaultdict(list)
ans=0
for i in range(n-1):
    if (n-i-1)<=ans:
        break
    for j in range(i+1,n+1):
        ss=s[i:j]
        if dic[ss]==[]:
            dic[ss]+=[j]
            continue
    
        elif max(dic[ss])<=i:
            dic[ss]+=[j]
        if len(dic[ss])>=2 and len(ss)>ans:
            ans=len(ss)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
import math
import heapq
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()

n = ni()
s = input()
d = {}
ln = len(s)
flag = False
for l in range(ln//2)[::-1]:
    for i in range(ln - l):
        c = s[i:i+l+1]
        if c not in d.keys():
            d[c] = i
        else:
            ll = len(c)
            if i >= d[c] + ll:
                print(len(c))
                flag = True
                break
    if flag:
        break
if flag is False:
    print(0)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(1,n-1):
    t = s[i:n]
    count = 0
    l = 0
    r = n
    if len(t) >= ans:
        start = False
        for j in range(len(t)):
            if s[j] == t[j] and l < r-1:
                if not start:
                    r = j + i
                    start = True
                count += 1
                l = j
            elif start:
                ans = max(count,ans)
                count = 0
                start = False
                r = n
                l = 0
            else:
                ans = max(count,ans)
        ans = max(count,ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

N=int(input())
s=input()

A=[['']*N for i in range(N)]

A[0][0]=s[0]


for i in range(1,N):
	A[i][0]=s[i]
	for j in range(i):
		A[i][j+1]=A[i-1][j]+s[i]

ans=0
for i in range(N):
	t=[]
	lent=0
	for j in range(i,N):
		u=bisect.bisect_left(t,[A[j][i],0])
		if lent<=u or A[j][i]!=t[u][0]:
			bisect.insort_left(t,[A[j][i],j])
			lent+=1
		else:
			if (j-t[u][1])>=(i+1):
				ans=i+1
				break
			else:
				lent+=1
				

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def do():
    N = int(input())
    S = str(input())
    answer = 0
    for i in range(len(S)-1):
        if answer < len(S)-i:
            for k in range(i+1,len(S)):
                if S[i] == S[k] and k+answer <= len(S):
                    temp = 0
                    betw = k-i-1
                    if betw+1 > answer:
                        for j in range(betw+1):
                            if k+j <= (len(S)-1) and S[i+j] == S[k+j]:
                                temp += 1
                            else:
                                break
                    answer = max(answer, temp)
        else:
            break
                

    print(answer)
    
if __name__ == '__main__':
    do()

Submission status: Time Limit Exceeded

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

check_list = [ [ 0 for i in range(n) ] for i in range(n) ]


ans = 0
for i in range(n-1):
    for j in range(i+1,n):
        q = check_list[i][j]
        p = check_list[i][j]
        for k in range(min(j-i-q,n-1-j+1-q)):
            if s[i+q+k] == s[j+q+k]:
                p += 1
            else:
                break
        if p > q:
            for k in range(1,p):
                check_list[i+k][j+k] = p - k
        ans = max(ans,p)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo

@mt
def slv(N, S):

    def func(l):
        for j in range(N-l):
            for k in range(j+l, N-l+1):
                # print(j, k, S[j:j+l], S[k:k+l])
                for i in range(l):
                    if S[j+i] != S[k+i]:
                        break
                else:
                    return -l
        return 0

    b = Bisect(func)
    a = b.bisect_left(0, 0, N//2)
    if func(a) == 0 and a != 0:
        a -= 1
    return a


def main():
    N = read_int()
    S = read_str()
    print(slv(N, S))


    # N = 5000
    # for _ in range(1000):
    #     # S = ''.join(random.choices('abcdefghijklmnopqrstuwzxyz', k=N))
    #     S = ''.join(random.choices('abcdefghijklmnopqrstuwzxyz'[:random.randint(1, 26)], k=N))
    #     # S = ''.join(random.choices('a', k=N))
    #     # print(S)
    #     print(slv(N, S))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = list(input())
M = 13 # 2**13 > 5 000

table = []

table_1 = [[j for j in range(i+1, N) if S[i] == S[j]] for i in range(N)]
if sum([sum(t) for t in table_1]) == 0:
	print(0)
	exit()
table.append(table_1)
for m in range(1,M+1):
	l = 2**m
	update = False
	tbl = [[] for i in range(N)]
	for i in range(N-2*l+1):
		for j in table[m-1][i]:
			if j < i + l:
				continue
			l_bef = l // 2
			if j + l_bef in table[m-1][i + l_bef]:
				tbl[i].append(j)
				update = True
	if not update:
		M = m
		break
	table.append(tbl)
M -= 1
ans = 2 ** M
l = 2 ** (M-1)
candidates = []
for i in range(N):
	for j in table[M][i]:
		candidates.append((i,j))

m = M-1
while m >= 0:
	new_candidates = []
	update = False
	l = 2 ** m
	for c in candidates:
		i,j = c[0], c[1]
		if j >= i + ans + l and j + ans in table[m][i+ans]:
			update = True
			new_candidates.append((i,j))
	if update:
		candidates = new_candidates
		ans += l
	m -= 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
ans = 0
for i in range(N):
    for j in range(i + 1, N):
        if S[i] != S[j]:
            continue
        c = 0
        for k in range(i, j):
            if k + j - i >= N:
                break
            if S[k] == S[k + j - i]:
                c += 1
        ans = max(ans, c)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
from bisect import bisect_left

def hantei(mid, s, suffix):
    # print(mid, s, suffix)
    for i in range(n - mid + 1):
        tmp = (s[i:i+mid], i)
        idx = bisect_left(suffix, tmp)

        # if mid == 4:
        #     print(tmp, idx)
        flag = True
        while(flag):
            tgt = suffix[idx]
            # print(tgt)
            if tmp[0] == tgt[0][:mid]:
                if tgt[1] >= i + mid:
                    return True
                else:
                    idx += 1
                    if idx >= n:
                        flag = False
            else:
                flag = False

n = getN()
s = input().strip()

suffix = []

for i in range(n):
    suffix.append((s[i:], i))

suffix.sort()

mn = 0
mx = n // 2 + 1
while(mx-mn>1):
    mid = (mx + mn) // 2
    is_succ = hantei(mid, s, suffix)
    if is_succ:
        mn = mid
    else:
        mx = mid

if hantei(mx, s, suffix):
    print(mx)
else:
    print(mn)

"""
17
aaaaaaaaaaaaaaaaa -> 8
10
absoabsoab -> 4
6
abcabc -> 3
10
abcdefghij -> 0
15
rangerangerange -> 5
2
xx -> 1
2
xy -> 0
12
abcdxxxxabcd -> 4

14
abcxxxxxxxxabc
3????????????????
"""

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
m = n//2 #答えのMAX値

#ngramを作る
def n_gram(target, n):
  return [ target[idx:idx + n] for idx in range(len(target) - n + 1)]

yet = True

for l in reversed(range(1,m+1)): #答えを上から探っていく
  if not yet:
    break
  else:
    for j in range(n-2*l+1):
      if not yet:
        break
      else:
        left = s[j:j+l] #最初の文字列
        target = s[j+l:]
        ngr = n_gram(target,l)
        if ngr.count(left)>0:
          ans = l
          yet = False

if yet:
  print(0)
else:
  print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(1, n//2 + 1):
    d = {}
    for j in range(n - i + 1):
        v = s[j:j+i]
        if v in d:
            d[v] += 1
        else:
            d[v] = 1
    for dd in d.values():
        if dd > 1:
            ans = i
    if ans != i:
        break
print(ans)