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:
import re

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

def isValid(n):
    return re.search('(.{'+str(n)+'}).*\\1',S)

# 探索すべきは[0,N//2+1]の範囲
left = 0
right = N//2+1
while True:
    middle = (left + right)//2
    if left + 1 == right:
        break
    if isValid(middle):
        left = middle
    else:
        right = middle

print(left)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n = int(input())
s = input()
ind = defaultdict(list)
for i in range(n):
    for j in range(i+1, n+1):
        ss = s[i:j]
        if len(ind[ss]) != 2:
            ind[ss].append(i)
        else:
            a, b = ind[ss]
            if i < a:
                ind[ss] = [i,b]
            elif i > b:
                ind[ss] = [a, i]
l = 0
for ss in ind:
    if len(ind[ss]) != 2:
        continue
    mn, mx = ind[ss]
    if len(ss) <= mx - mn:
        l = max(l, len(ss))
print(l)

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


@mt
def slv(N, S):
    ans = 0
    t = defaultdict(list)
    for i, c in enumerate(S):
        t[c].append(i)

    def eq(i, j):
        L = min(N-j, j-i)
        for k in range(L):
            if S[i+k] != S[j+k]:
                return k
        return L
    
    ans = 0
    for c in t:
        idx = t[c]
        for i in range(len(idx)):
            for j in range(i+1, len(idx)):
                if idx[j] - idx[i] > ans and N - idx[j] > ans:
                    ans = max(ans, eq(idx[i], idx[j]))
    return ans


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


    # N = 5000
    # S = ''.join(random.choices('abcdefghijklmnopqrstuwzxyz', k=N))
    # S = ''.join(random.choices('a', k=N))
    # print(slv(N, S))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC141 E

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
S = input()
ans = 0
for k in range(1,math.ceil(n/2)+1):
    if k <= ans or n-k <= ans:
        continue
    s = S[:k]
    t = S[k:]
    dp = [[0 for _ in range(n - k+1)] for _ in range(k+1)]
    for i in range(k):
        for j in range(n-k):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i][j+1],dp[i+1][j])
    ans = max(ans,dp[-1][-1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
ans=0
for i in range(n):
    if i<n-1:
        if s[i]==s[i+1]:
            ans=max(ans,1)
    for j in range(i+2,n):
        if s[i]==s[j] and j-i>1:
            ii=i
            jj=j
            if j<n-1:
                while s[ii+1]==s[jj+1]:
                    ii+=1
                    jj+=1
                    if ii==j-1 or jj==n-1:
                        break
                ans=max(ans,ii-i+1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
l, r = 0, N-1


def can(m):
    for j in range(N - 2*m + 1):
        for k in range(j + m, N - m + 1):
            if S[j:j+m] == S[k:k+m]:
                return True
    return False


for i in range(13):
    m = (l + r + 1) // 2
    if can(m):
        l = m
    else:
        r = m
print(l)

Submission status: Time Limit Exceeded

Solution code:
import collections
def main():

    N = int(input())
    S = input()
    d = collections.defaultdict(dict)
    for l in range(1, N//2+1):
        for i in range(N-l+1):
            if S[i:i+l] not in d[l]:
                d[l][S[i:i+l]] = [[i, i+l-1]]
            else:
                d[l][S[i:i+l]].append([i, i+l-1])


    for l in range(N//2, 0, -1):
        if l in d:
            for s in d[l]:
                if len(d[l][s]) > 1:
                    # print(d[l][s], l)
                    i, j = d[l][s][0]
                    k, m = d[l][s][-1]
                    if j < k:
                        return l
    return 0

if __name__ == '__main__':
    print(main())

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
p = 0
def check(l):
  global p
  for i in range(p, N-l):
    s = S[i:i+l]
    if not S.find(s, i+l) < 0:
      p = i
      return True
  return False
a = 1
b = N
while a < b:
  i = (a + b)//2
  if not check(i):
    b = i
  else:
    if a == i:
      break
    a = i
r = b-1
print(r)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, S: str):
    half = N // 2
    for i in range(N // 2):
        length = half - i
        for i in range(N - length * 2 + 1):
            org = S[i:length + i]
            rest = S[length + i:N]
            #print(org, rest)
            if org in rest:
                print(length)
                return
    print('0')
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def lcs_length(a, b):
    table = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i, ca in enumerate(a, 1):
        for j, cb in enumerate(b, 1):
            table[i][j] = (
                table[i - 1][j - 1] + 1 if ca == cb else
                max(table[i][j - 1], table[i - 1][j]))
    return table[-1][-1]

n=int(input())
s=list(input())
ans=[]
for i in range(1,n):
  s1=s[0:i];s2=s[i:n]
  ans.append(lcs_length(s1,s2))
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N = int(input())
S = input()
D = defaultdict(list)
for i in range(N):
    for j in range(i, min(N, i+N//2)):
        D[S[i:j+1]].append((i, j))

ans = 0
for key in D:
    max_i = -1
    min_j = N
    for i, j in D[key]:
        max_i = max(i, max_i)
        min_j = min(j, min_j)
        if min_j < max_i:
            ans = max(ans, j-(i-1))
            break
print(ans)

Submission status: Time Limit Exceeded

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


def long_substr(data):
    substr = ''
    if len(data) > 1 and len(data[0]) > 0:
        for i in range(len(data[0])):
            for j in range(len(data[0])-i+1):
                if j > len(substr) and is_substr(data[0][i:i+j], data):
                    substr = data[0][i:i+j]
    return substr


def is_substr(find, data):
    if len(data) < 1 and len(find) < 1:
        return False
    for i in range(len(data)):
        if find not in data[i]:
            return False
    return True


ans = 0
for i in range(1, N):
    ls = long_substr([S[:i], S[i:]])
    # print(ls)
    if len(ls) > ans:
        ans = len(ls)


print(ans)

Submission status: Time Limit Exceeded

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

def e():
    for l in range(n//2, 0, -1):
        for i in range(n-l+1):
            s=S[i:i+l]
            if len(S.split(s))>=3:
                return l
    return 0

print(e())

Submission status: Time Limit Exceeded

Solution code:

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

nowlen = N // 2
flag = False
while True:

    if nowlen == 0:
        break

    dic = {}

    for i in range(N - nowlen + 1):

        if S[i:i+nowlen] not in dic:
            dic[S[i:i+nowlen]] = i

        elif i - dic[S[i:i+nowlen]] >= nowlen:
            flag = True
            break

    if flag:
        break

    
    nowlen -= 1



print (nowlen)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
ans = 0
for le in range(n // 2, 0, -1):
  for l1 in range(0, n - le * 2 + 1):
    if s[l1:l1+le] in s[l1+le:]:
      ans = le
      break
  else:
    continue
  break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N = int(input())
S = input()
d = defaultdict(lambda:[0,0])

for i in range(N):
    s = S[i]
    d[s][0] += 1
    d[s][1] = i
    for j in range(i+1,N):
        s = s+S[j]
        if i>d[s][1]:
            d[s][0] += 1
            d[s][1] = j

ans = 0
for s in d:
    if d[s][0]>=2:
        ans = max(ans,len(s))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import defaultdict

n = ni()
s = ns()

dic = defaultdict(list)

for st in range(n):
    for ed in range(st+1, min(st+n//2+2, n+1)):
        dic[s[st:ed]].append(st)

ans = 0
for stri, stsi in dic.items():
    if len(stsi) <= 1:
        continue

    if stsi[-1] - stsi[0] >= len(stri):
        ans = max(ans, len(stri))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
ans = 0
ok = 0
ng = n//2+2
while ok+1 < ng:
  flag = False
  mid = (ok+ng)//2
  for j in range(n):
    if s[j+mid:].find(s[j:j+mid]) != -1:
      flag = True
      break
  if flag:
    ok = mid
  else:
    ng = mid

print(ok)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
now=0
now2=1
plus=0
answer=0
swit=0
while now<n:
    while now2<n:
        if swit==0:
            if s[now]==s[now2]:
                swit=1
                plus=1
            else:
                now2+=1
        if swit==1:
            if now2+plus<n:
                if s[now+plus]==s[now2+plus] and now+plus<now2:
                    plus+=1
                    if plus>=answer:
                        answer=plus
                else:
                    now2+=1
                    plus=0
            else:
                now2+=1
                plus=0
        if now2+answer>=n+1:
            break
    now+=1
    now2=now+1
    if now+answer>=n+1:
        break

print(answer)

Submission status: Time Limit Exceeded

Solution code:
def LCS(S,T):
  #初期化
  dp=[[0 for i in range(len(T)+1)] for j in range(len(S)+1)]

  #DP
  for i in range(len(S)):
    for j in range(len(T)):
      dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])
      if S[i]==T[j]:
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+1)
  return dp[len(S)][len(T)]

N = int(input())
St = input()
ans = 0
for i in range(1,N):
  S = St[:i]
  T = St[i:]
  ans = max(LCS(S,T), ans)
        
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
s = input()

d = {}
res = 0
for l1 in range(n):
    for l2 in range(l1+1,n+1):
        ss = s[l1:l2]
        if ss not in d:
            d[ss] = l1
        else:
            if d[ss]+len(ss)<=l1:
                res = max(res,len(ss))
print(res)

Submission status: Time Limit Exceeded

Solution code:
N=int(input());S=input()
for wordlen in range(N//2,-1,-1):
 for l in range(N-wordlen):
  if S.count(S[l:l+wordlen])>1:print(wordlen);quit()

Submission status: Time Limit Exceeded

Solution code:
def atcoderD(str):
    n = len(str)
    LCSRe = [[0]*(n+1) for y in range(n + 1)]
    res_length = 0
    index = 0
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            if str[i - 1] == str[j - 1] and LCSRe[i - 1][j - 1] < (j - i):
                LCSRe[i][j] = LCSRe[i - 1][j - 1] + 1
                if LCSRe[i][j] > res_length:
                    res_length = LCSRe[i][j]
                    index = max(i, index)
            else:
                LCSRe[i][j] = 0
    return res_length
n = int(input())
s = input()
print(atcoderD(s))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC141 E

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def lcs_length(a, b):
    table = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i, ca in enumerate(a, 1):
        for j, cb in enumerate(b, 1):
            table[i][j] = (
                table[i - 1][j - 1] + 1 if ca == cb else
                max(table[i][j - 1], table[i - 1][j]))
    return table[-1][-1]
n = I()
S = list(input())
ans = 0
for k in range(1,n):
    if k <= ans or n - k <= ans:
        continue
    s = S[:k]
    t = S[k:]
    ans = max(ans,lcs_length(s,t))
print(ans)

Submission status: Time Limit Exceeded

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

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

A[0].append(s[0])


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

ans=0
for i in range(len(A)-1):
	for j in range(i+1,len(A)):
		for t in A[i]:
			if t in A[j] and j-i>=len(t):
				ans=max(ans,len(t))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
import sys
for l in range(n//2,0,-1):
	t=[[s[i:i+l],i] for i in range(n-l+1)]
	t.sort()
	last=t[0][0]
	lasti=t[0][1]
	for i in range(1,len(t)):
		if t[i][0]==last:
			if lasti+l<=t[i][1]:
				print(l)
				sys.exit()
		else:
			last=t[i][0]
			lasti=t[i][1]
print(0)

Submission status: Time Limit Exceeded

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

s_closed = set()

max_len = 0

for i in range(1,(n//2+1)):
    for j in range(n-i+1):
        ss = s[j:j+i]
        if ss in s_closed:
            continue
        s_closed.add(ss)
        for k in range(j+i,n-i+1):
            sss = s[k:k+i]
            if ss == sss:
                max_len = i
                i+=1
                continue

print(max_len)

Submission status: Time Limit Exceeded

Solution code:
#
import sys
sys.setrecursionlimit(12345678)
import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop


def main():
    n = int(input())
    s = input()
    if len(set(s)) == n:
        print(0)
        return

    if len(set(s)) == 1:
        print(n // 2)
        return 

    def same_length(i1, i2):
        i = 0
        count = 0
        while i1 + i < i2 and i2 + i < n:
            if s[i1 + i] != s[i2 + i]:
                break

            count += 1
            i += 1

        return count

    char_positions = defaultdict(list)
    for i, c in enumerate(s):
        char_positions[c].append(i)

    ans = 0
    for char in char_positions:
        char_count = len(char_positions[char])
        # print(char, char_count)
        if char_count < 2:
            continue
        for i in range(char_count - 1):
            for j in range(i + 1, char_count):
                ans = max(ans, same_length(char_positions[char][i], char_positions[char][j]))
                # print(char_positions[char][i], char_positions[char][j], ans)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

def sol():
    N = int(input())
    S = input().rstrip()

    ans = 0

    for length in range(1, N // 2 + 2):
        for left in range(N - length + 1):
            sub = S[left: left + length]
            if S[left + length:].find(sub) != -1:
                ans = max(ans, length)

    print(ans)

sol()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
maxn = N//2

for i in range(maxn, 0, -1):
  for j in range(N - i):
    s1 = S[j:j+i]
    for k in range(j + i, N):
      s2 = S[k:k+i]
      if s1 == s2:
        print(i)
        exit()
print(0)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
m=n//2
for i in range(n//2):
    for j in range(n-m):
        tmp1=s[j:j+m]
        for k in range(n-j-2*m+1):
            tmp2=s[j+m+k:j+m*2+k]
            if tmp1==tmp2:
                print(m)
                exit()
    m-=1
print(0)

Submission status: Time Limit Exceeded

Solution code:
import sys

def solve():
    N = int(input())
    S = input()
    words = dict()
    longest = 0
    for i in range(N-1):
        if (N - i) // 2 < longest: break
        else:
            current = S[i]
            if current in words: longest = max(longest, 1)
            else: words[current] = i
            for j in range(1, N - i):
                current += S[i + j]
                if current in words:
                    if words[current] + j + 1 <= i: longest = max(longest, j + 1)
                else: words[current] = i
    if S[N-1] in words: longest = max(longest, 1)

    #print(words)

    print(longest)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N = I()
    S = ST()
    # めぐる式二分探索
    def meguru_bisect(ok, ng):
        while abs(ok - ng) > 1:
            mid=(ok + ng) // 2
            if is_ok(mid):
                ok=mid
            else:
                ng=mid
        return ok

    def is_ok(length):
        for i,s in enumerate(S[:-length + 1]):
            st = S[i:i+length]
            if st in S[i+length:]:
                return True
        return False

    ans = meguru_bisect(0,len(S))
    print(ans)



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

ans=0
for i in range(N//2):
    for j in range(N-i):
        for k in range(j+i+1,N-i):
            #print(i,S[j:j+i+1],S[k:k+i+1])
            if S[j:j+i+1]==S[k:k+i+1]:
                ans=i+1
                break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
res = 0
for i in range(1, n//2 + 1):
    found = False
    for j in range(0, n - i - i+1):
        s1 = s[j:j+i]
        for k in range(j+i, n-i+1):
            if s[k:k+i] == s1:
                res = i
                found = True
                #print(res, s1, s[k:k+i])
            if found:
                break
        if found:
            break
print(res)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
def check(l):
  for i in range(N-l):
    s = S[i:i+l]
    if not S.find(s, i+l) < 0:
      return True
  return False
a = 1
b = N
while a < b:
  i = (a + b)//2
  if not check(i):
    b = i
  else:
    if a == i:
      break
    a = i
r = b-1
print(r)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def get_substrings(length, string):
    substrings = [''.join(string[i:i+length]) for i in range(len(string)-length+1)]
    return substrings

N = int(input())
S = input()
ans = 0
for i in range(1, N//2 + 1):
    substrings = Counter(get_substrings(i, S))
    if substrings.most_common(1)[0][1] >= 2:
        ans = i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
m=n//2
ans=0
for length in range(1,m+1):
    for one in range(n-2*length):
        for two in range(one+length,n-length+1):
            if s[one:one+length]==s[two:two+length]:
                ans=max(ans,length)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def check(S, l):
    for i in range(len(S)-l*2+1):
        x = S[i:i+l]
        if S[i+l:].find(x) != -1:
            return True
    return False


def main():
    N = int(input())
    S = input()
    lo = 0
    hi = N//2
    while lo < hi:
        mid = -(-(lo+hi)//2)
        if check(S, mid):
            lo = mid
        else:
            hi = mid - 1
    print(lo)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N = I()
    S = ST()
    # めぐる式二分探索
    def meguru_bisect(ok, ng):
        while abs(ok - ng) > 1:
            mid=(ok + ng) // 2
            if is_ok(mid):
                ok=mid
            else:
                ng=mid
        return ok

    def is_ok(length):
        for i,s in enumerate(S):
            st = S[i:i+length]
            if st in S[i+length:]:
                return True
        return False

    ans = meguru_bisect(0,len(S))
    print(ans)



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

lcs = [[0 for i in range(n + 1)] for j in range(n + 1)]
ans = 0
for i in range(1, n + 1):
    for j in range(i + 1, n + 1):
        if (s[i - 1] == s[j - 1] and lcs[i - 1][j - 1] < j - i):
            lcs[i][j] = lcs[i - 1][j - 1] + 1
            ans = max(lcs[i][j], ans)
        else:
            lcs[i][j] = 0
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
def main():

    N = int(input())
    S = input()
    d = collections.defaultdict(list)
    for l in range(1, N+1):
        for i in range(N-l+1):
            d[S[i:i+l]].append([i, i+l-1])

    ans = 0
    for s in d:
        if len(d[s]) > 1:
            i, j = d[s][0]
            k, l = d[s][-1]
            if j < k:
                ans = max(ans, j-i+1)

    return ans

if __name__ == '__main__':
    print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys

def solve():
    N = int(input())
    S = input()
    words = dict()
    longest = 0
    for i in range(N-1):
        current = S[i]
        if current in words: longest = max(longest, 1)
        else: words[current] = i
        for j in range(1, N - i):
            current += S[i + j]
            if current in words:
                if words[current] + j + 1 <= i: longest = max(longest, j + 1)
            else: words[current] = i
    if S[N-1] in words: longest = max(longest, 1)

    #print(words)

    print(longest)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
a=[[0]*n for i in range(n)]
buf=0
for i in range(n):
    for j in range(i+1,n):
        if i==0:
            if s[i]==s[j]:
                a[i][j]=1
            continue
        if s[i]==s[j]:
            a[i][j]=min(j-i,a[i-1][j-1]+1)
            buf=max(buf,a[i][j])
print(buf)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
now=0
now2=1
plus=0
answer=0
swit=0
while now<n:
    while now2<n:
        if swit==0:
            if s[now]==s[now2]:
                swit=1
                plus=1
            else:
                now2+=1
        if swit==1:
            if now2+plus<n:
                if s[now+plus]==s[now2+plus] and now+plus<now2:
                    plus+=1
                    if plus>=answer:
                        answer=plus
                else:
                    now2+=1
                    plus=0
            else:
                now2+=1
                plus=0
    now+=1
    now2=now+1

print(answer)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
def isok(n):
    for i in range(N-2*n+1):
        now = S[i:i+n]
        for j in range(i+n, N-n+1):
            if now == S[j:j+n]:
                return True
    return False

left = 0
right = N//2+1

while right - left > 1:
    mid = left + (right-left)//2
    if not isok(mid):
        right = mid
    else:
        left = mid




print(left)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
ans = 0
for i in range(1, n//2+1):
  for j in range(n):
    if s[j+i:].find(s[j:j+i]) != -1:
      ans = i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC141 E

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
S = input()
ans = 0
for k in range(1,n):
    s = S[:k]
    t = S[k:]
    dp = [[0 for _ in range(n - k+1)] for _ in range(k+1)]
    for i in range(k):
        for j in range(n-k):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i][j+1],dp[i+1][j])
    ans = max(ans,dp[-1][-1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def z_algorithm(S):
    """Zアルゴリズム
    https://snuke.hatenablog.com/entry/2014/12/03/214243 の二番目のコード
    """
    N = len(S)
    Z = [0]*N

    c = 0
    for i in range(1, N):
        if i+Z[i-c] < c+Z[c]:
            Z[i] = Z[i-c]
        else:
            j = max(0, c+Z[c]-i)
            while i+j < N and S[j] == S[i+j]:
                j += 1
            Z[i] = j
            c = i
    Z[0] = len(S)
    return Z


def solve(N: int, S: str):

    ans = 0
    for i in range(N-1):        # N
        z = z_algorithm(S[i:])  # N
        for j, zz in enumerate(z):  # N
            ans = max(min(j, zz), ans)
    print(ans)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

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

    ok = False
    for w in range(N//2, 0, -1):
        for i in range(N-2*w+1):
            for j in range(i+w, N-w+1):
                if s[i:i+w] == s[j:j+w]:
                    print(w)
                    return
    
    if not ok:
        print(0)


if __name__ == "__main__":
    main()