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())
sarr = input()

maxlen = 0

i = 0
while i < n:
  s = sarr[i]
  j, l = 1, 1
  while i + j < n:
    candidate = sarr[i + j]
    if s == candidate:
      l = 1
      while (i + j + l < n) and (i + l < i + j) and (sarr[i + l] == sarr[i + j + l]):
        l += 1
      if l > maxlen:
        maxlen = l
    j += 1
  i += l

print(maxlen)

Submission status: Time Limit Exceeded

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

slen = len(sarr)
maxlen = 0
for i, s in enumerate(sarr):
  for j, candidate in enumerate(sarr[i+1:]):
    if s == candidate:
      l = 1
      while (i + 1 + j + l < slen) and (i + l < i + 1 + j) and (sarr[i + l] == sarr[i + 1 + j + l]):
        l += 1
      if l > maxlen:
        maxlen = l

print(maxlen)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
ca = ord('a')
T = [ord(c) - ca for c in S]

ans = 0
nds = [[None]*26 for i in range(N**2)]
root = nds[0]
cs = [root]*N
gen = 0
for i in range(N):
    j = i
    cur = root
    while j < N and cur[T[j]] is not None:
        cur = cur[T[j]]
        j += 1
    ans = max(ans, j - i)
    e = T[i]
    for k in range(i):
        c = cs[k]
        if c[e] is None:
            cs[k] = c[e] = nds[gen]
            gen += 1
        else:
            cs[k] = c[e]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
ca = ord('a')
T = [ord(c) - ca for c in S]

ans = 0
nds = [[None]*26 for i in range(N**2)]
root = nds[0]
cs = [root]*N
gen = 0
for i in range(N):
    j = i
    cur = root
    while j < N and cur[T[j]] is not None:
        cur = cur[T[j]]
        j += 1
    ans = max(ans, j - i)
    e = T[i]
    for k in range(i):
        c = cs[k]
        if c[e] is None:
            cs[k] = c[e] = nds[gen]
            gen += 1
        else:
            cs[k] = c[e]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
s = input()
dp = [[0]*(n+1) for y in range(n+1)]
ans = 0
for i in reversed(range(n)):
    for j in reversed(range(n)):
        if s[i] == s[j] and i > j:
            dp[i][j] = min(dp[i+1][j+1] + 1, i-j)
            ans = max(ans, dp[i][j])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
dp = [[0]*(n+1) for _ in range(n+1)]
ans = 0
for i in reversed(range(n)):
    for j in reversed(range(n)):
        if s[i] == s[j] and i > j:
            dp[i][j] = min(dp[i+1][j+1] + 1, i-j)
            ans = max(ans, dp[i][j])
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
w=[[0]*n for i in range(n)]
ans=chk=0
for i in range(n-1,-1,-1):
    for j in range(n-1,-1,-1):
        if s[i]==s[j]:
            if i==n-1 or j==n-1:
                w[i][j]=1
            else:
                w[i][j]=w[i+1][j+1]+1
for i in range(1,n):
    for j in range(i):
        ans=max(ans,w[i][j]-[0,w[i][j]-(i-j-w[i][j]+1)][j+w[i][j]>=i+1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:

n = int(input())
ab = str(input())

ans = 0
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

lenab = len(ab)
for i in range(0, lenab):
    if ans > lenab - i - 1:
        break
    S = ab[i:]
    o = z_algo(S)
    p = o[1:]
    p.append(ans)
    ans = max(p)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
from heapq import *
sys.setrecursionlimit(200000)
input = sys.stdin.readline

N, = map(int, input().split())
# L = [int(v) for v in input().split()]
# L = [int(input()) for _ in range(Q)]
S = input().strip()

class RollingHash:
    def __init__(self, data):
        self.len = len(data)
        self.row = [0] * self.len
        for i in range(self.len):
            self.row[i] = ord(data[i]) * 73

    def build(self, count):
        self.data = [0] * (self.len - count + 1)
        first = 0
        for i in range(count):
            c = 10 ** (count - i - 1)
            first += self.row[i] * c

        self.data[0] = first

        for i in range(1, len(self.data)):
            c = self.data[i - 1] - self.row[i - 1] * (10 ** (count - 1))
            self.data[i] = c * 10 + self.row[i + count - 1]

    def get(self, index):
        return self.data[index]

roll = RollingHash(S)
t = N // 2 + 1
ans = 0
for i in range(2, t):
    roll.build(i)

    f = False
    for j in range(t - i + 1):
        ll = j + i
        rr = N - i + 1
        data = roll.data[ll:ll+rr]
        ta = roll.get(j)

        if ta in set(data):
            f = True
            break
    if f:
        ans = i

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    S = input()
    ok, ng = 0, N + 1
    while abs(ok - ng) > 1:
        x = (ok + ng) // 2
        for i in range(N - x + 1):
            if S.find(S[i: i + x], i + x) > 0:
                ok = x
                break
        else:
            ng = x
 
    print(ok)
 
 
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
s=[]
x=int(input())
st = input()
for i in range(len(st)):
  for j in range(len(st)-i):
   s.append(st[i:j+i+1])
a=[]
for i in s:
  a.append(st.count(i))
b=[]
for i in range(len(a)):
  if a[i]>=2:
    b.append(len(s[i]))
if len(b)==0:
  print(0)
else:  
  print(max(b))

Submission status: Time Limit Exceeded

Solution code:

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

    for i in range(N // 2, max(N // 2 - 100, 0), -1):
        for j in range(N - i + 1):
            if S.find(S[j: i + j], i + j) > 0:
                print(i)
                exit()

    ok, ng = 0, N + 1
    while abs(ok - ng) > 1:
        x = (ok + ng) // 2
        for i in range(N - x + 1):
            if S.find(S[i: i + x], i + x) > 0:
                ok = x
                break
        else:
            ng = x

    print(ok)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

n = int(input())
ab = str(input())
a = list(ab)
b = list(range(0, len(a)+1))

e = list(zip(a,b))
visited = []
count = [0]
while len(e) >0:
    x,y = e.pop()
    lenx = len(x)
    z = ab[y+lenx:].find(x)
    if z == -1:
        visited.append((x,y))
    else:
        f = y+z+1
        g = (x, y)
        count.append(lenx)
        visited.append(g)

        h = (ab[y:y+lenx+1], y)
        e.insert(0, h)

print(count[-1])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
S = input()

def Z_algorithm(S):
    N = len(S)
    res = [0] * N
    res[0] = N
    i = 1
    j = 0
    while i < N:
        while i+j < N and S[j] == S[i+j]:
            j += 1
        res[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k+res[k] < j:
            res[i+k] = res[k]
            k += 1
        i += k
        j -= k
    return res

ans = 0
for i in range(N):
    # Z-algorithmでLCP(最長共通接頭辞の長さ)を取得
    LCP = Z_algorithm(S[i:])
    for j, lcp in enumerate(LCP):
        # 最大値更新の際は、共通部分が重複していないことを確認する
        if lcp > ans and j >= lcp:
            ans = lcp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
from heapq import *
sys.setrecursionlimit(200000)
input = sys.stdin.readline

N, = map(int, input().split())
# L = [int(v) for v in input().split()]
# L = [int(input()) for _ in range(Q)]
S = input().strip()

class RollingHash:
    def __init__(self, data):
        self.len = len(data)
        self.row = [0] * self.len
        for i in range(self.len):
            self.row[i] = ord(data[i]) * 73

    def build(self, count):
        self.data = [0] * (self.len - count + 1)
        first = 0
        for i in range(count):
            c = 10 ** (count - i - 1)
            first += self.row[i] * c

        self.data[0] = first

        for i in range(1, len(self.data)):
            c = self.data[i - 1] - self.row[i - 1] * (10 ** (count - 1))
            self.data[i] = c * 10 + self.row[i + count - 1]

    def get(self, index):
        return self.data[index]

roll = RollingHash(S)
t = N // 2 + 1
ans = 0
for i in range(2, t):
    roll.build(i)

    for j in range(t - i + 1):
        for k in range(j + i, N - i + 1):
            if roll.get(j) == roll.get(k):
                ans = i

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(i,-1,-1):
    if S[i] == S[j]:
      dp[i][j] = dp[i+1][j+1] + 1
      tmp = min(dp[i][j],i-j)
      ans = max(ans,tmp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
s = input()
dp = [[0 for _ in range(N+1)]for _ in range(N+1)]
now = 0
ans = 0

for i in range(N-1,-1,-1):
    for j in range(N-1,-1,-1):
        if s[i] != s[j]:
            dp[i][j] = 0
        else:
            dp[i][j] = dp[i+1][j+1]+1
            if i >= j:
              continue
            now = min(dp[i][j],j-i)
            ans = max(ans,now)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

n = int(input())
s = input()

for m in range(n//2+1,0,-1):
    d = {}
    for l in range(n-m+1):
        ss = s[l:l+m]
        if ss not in d:
            d[ss] = l
        else:
            l2 = d[ss]
            if l2+m<=l:
                print(m)
                exit()
print(0)

Submission status: Time Limit Exceeded

Solution code:

def main():
    import time
    start_time = time.time()

    N = int(input())
    S = input()
    ok, ng = 0, N + 1
    while abs(ok - ng) > 1:
        if time.time() - start_time > 1.7:
            print(0)
            exit()

        x = (ok + ng) // 2
        for i in range(N - x + 1):
            if S.find(S[i: i + x], i + x) > 0:
                ok = x
                break
        else:
            ng = x

    print(ok)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

def main():
    N = int(input())
    S = input()
    ok, ng = 0, N + 1
    while abs(ok - ng) > 1:
        x = (ok + ng) // 2
        for i in range(N - x + 1):
            if S.find(S[i: i + x], i + x) > 0:
                ok = x
                break
        else:
            ng = x

    print(ok)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
ok, ng = 0, N + 1
while abs(ok - ng) > 1:
    x = (ok + ng) // 2
    for i in range(N - x + 1):
        target = S[i: i + x]
        if S.find(target, i + x) > 0:
            ok = x
            break
    else:
        ng = x

print(ok)

Submission status: Time Limit Exceeded

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

ok, ng = 0, N + 1
while abs(ok - ng) > 1:
    x = (ok + ng) // 2
    for i in range(N - x + 1):
        target = S[i: i + x]
        regex = re.compile('{}.*{}'.format(target, target))
        mo = regex.search(S)
        if mo:
            ok = x
            break
    else:
        ng = x

print(ok)

Submission status: Time Limit Exceeded

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

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

res = 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] = max(dp[i][j], dp[i + 1][j + 1] + 1)
        res = max(res, min(dp[i][j], j - i))
print(res)

Submission status: Time Limit Exceeded

Solution code:
import collections
mod=10**9+7
base=37
n=int(input())
S=list(ord(s)-96 for s in input())
ans=0
d=collections.defaultdict(int)
for i in range(n):
  h=0
  for j in range(i,n):
    h=(h*base+S[j])%mod
    if d[h]==0:
      d[h]=j
    else:
      if d[h]<i:
        ans=max(ans,j-i+1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

n = I()
s = S()



left = 0
right = n//2
flag = 0
while left <= right:
    mid = (left + right) // 2
    str_len = mid
    for sousa_point in range(n - str_len + 1):
        string = s[sousa_point: sousa_point + str_len]
        if string in s[:sousa_point] or string in s[sousa_point + str_len:]:
            left = mid + 1
            flag = 1
            break
    else:
        right = mid - 1
        flag = False


if flag:
    print(mid)
else:
    print(mid - 1)

Submission status: Time Limit Exceeded

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

MOD=5005
dp=[[0]*MOD for i in range(MOD)]

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

Submission status: Time Limit Exceeded

Solution code:
#動画解法
#18:30
n = int(input())
s = input()
dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
for i in range(n-1,-1,-1):
  for j in range(n-1,-1,-1):
    if s[i] == s[j]:
      dp[i][j] = dp[i+1][j+1]+1
can = []
for i in range(n):
  for j in range(n):
    if i < j:
      can.append(min(dp[i][j],j-i))
print(max(can))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
for i in range(n//2,0,-1):
  d = dict()
  se = set()
  for j in range(n-i+1):
    c = hash(s[j:j+i])
    if c not in se:
      d[c] = j+i-1
      se.add(c)
    elif d[c] < j:
      print(i)
      exit()
print(0)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
for i in range(n//2,0,-1):
  d = dict()
  for j in range(n-i+1):
    c = hash(s[j:j+i])
    if c not in d:
      d[c] = j+i-1
    elif d[c] < j:
      print(i)
      exit()
print(0)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
high = n//2
low = 1
ans = 0

while low <= high:
    i = (high+low)//2
    for j in range(n-i*2+1):
        if s[j:i+j] in s[i+j:]:
            if ans < i:
                ans = i
                low = i+1
                break
    if ans < i:
        high = i-1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
S = input()

# dp[i][j] := iからとjから始めた時に、一致する最大の長さ
dp = list2d(N+1, N+1, 0)
# 後ろから埋めていく
for i in range(N-1, -1, -1):
    for j in range(N-1, -1, -1):
        if S[i] == S[j]:
            dp[i][j] = dp[i+1][j+1] + 1

mx = 0
for i in range(N+1):
    for j in range(N+1):
        # 最大値更新の際は、iとjがその値以上離れていることを確認する
        if dp[i][j] > mx and abs(i-j) >= dp[i][j]:
            mx = dp[i][j]
print(mx)

Submission status: Time Limit Exceeded

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

dp = [[0 for _ in range(N+5)] for _ in range(N+5)]

# dp[i][j]に文字列Sをi文字目からとj文字目からみたときに一致している部分の長さを格納
# 全て0で初期化
# i,jはそれぞれN-1から0まで動かせば良い(後ろから)
# i文字目とj文字目が一致していないならばdp[i][j]に0を格納
# i文字目とj文字目が一致していたらdp[i][j]にdp[i+1][j+1]+1を格納
for i in range(N-1, -1, -1):
    for j in range(N-1, -1, -1):
        if S[i] != S[j]:
            dp[i][j] = 0
        else:
            dp[i][j] = dp[i+1][j+1] + 1 # dp配列を長めに取ったのでj+1やj+1がN以上になってもそこには全て0が入っているので問題なし
#print(dp)

ans = 0
for i in range(N):
    for j in range(N):
        if i >= j: # i>=jの場合を排除してi<jのdp配列にのみ着目
            continue
        now = min(dp[i][j], j-i) # 文字がかぶっていた場合の考慮
        ans = max(ans, now)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
memo_ls = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
    for j in range(min(i+1,n-1), n):
        if s[i] == s[j]:
            memo_ls[i][j] = memo_ls[i-1][j-1] + 1
for i in range(n):
    for j in range(min(i+1,n-1), n):
        if memo_ls[i][j] > 0:
            if j - i < memo_ls[i][j]:
                memo_ls[i][j] = j - i
print(max([max(i) for i in memo_ls]))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
l = n//2
ans = 0

for i in range(1,l+1)[::-1]:
    for j in range(n-i*2+1):
        if s[j:i+j] in s[i+j:]:
            ans = i
            break
    else:
        continue
    break
print(ans)

Submission status: Time Limit Exceeded

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

import bisect

N = int(input())
s = input().split() 
s = list(s[0])

dp = [[0]*(N+1) for _ in range(N+1)]
ans=0
for i in reversed(range(N)):
    for j in reversed(range(N)):
        if s[i]==s[j]:
            dp[i][j]=min(abs(j-i),dp[i+1][j+1]+1)
            ans = max(ans,dp[i][j])
#print(dp)
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+1):
        if (s[i:j] in s[j:]):
            if ans < len(s[i:j]):
                ans = len(s[i:j])
        else:
            break
print(ans)

Submission status: Time Limit Exceeded

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

dp=[[0 for _ in range(N)] for _ in range(N)]
#dp[i][j]:i文字目とj文字目からの共通文字の最大長さ(i>j)

for i in range(N):
  if S[i]==S[N-1]:
    dp[i][N-1]=1
    dp[N-1][i]=1

for i in reversed(range(N-1)):
  for j in range(i):
    if S[i]==S[j]:
      dp[i][j]=dp[i+1][j+1]+1
      if j+dp[i][j]-1>=i:
        dp[i][j]=i-j

A=[]
for i in range(N):
  for j in range(i):
    A.append(dp[i][j])

print(max(A))

Submission status: Time Limit Exceeded

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

dp=[[0 for _ in range(N)] for _ in range(N)]
#dp[i][j]:i文字目とj文字目からの共通文字の最大長さ

for i in range(N):
  if S[i]==S[N-1]:
    dp[i][N-1]=1
    dp[N-1][i]=1

for i in reversed(range(N-1)):
  for j in reversed(range(N-1)):
    if S[i]==S[j]:
      dp[i][j]=dp[i+1][j+1]+1
      if min(i,j)+dp[i][j]-1>=max(i,j):
        dp[i][j]=max(i,j)-min(i,j)

A=[]
for i in range(N):
  for j in range(i):
    A.append(dp[i][j])

print(max(A))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
S = input()

def bisearch_max(mn, mx, func):
    """ 条件を満たす最大値を見つける二分探索 """

    ok = mn
    ng = mx
    while ok+1 < ng:
        mid = (ok+ng) // 2
        if func(mid):
            # 上を探しに行く
            ok = mid
        else:
            # 下を探しに行く
            ng = mid
    return ok

def calc(m):
    A = set()
    for i in range(N-m*2+1):
        a = S[i:i+m]
        # 既に探したaはもう1回探す必要ない
        if a not in A:
            b = S[i+m:]
            if b.find(a) != -1:
                return True
            A.add(a)
    return False

print(bisearch_max(0, N, calc))

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+1):
        if (s[i:j] in s[j:]) == True and ans < len(s[i:j]):
            ans = len(s[i:j])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
S = input()

def bisearch_max(mn, mx, func):
    """ 条件を満たす最大値を見つける二分探索 """

    ok = mn
    ng = mx
    while ok+1 < ng:
        mid = (ok+ng) // 2
        if func(mid):
            # 上を探しに行く
            ok = mid
        else:
            # 下を探しに行く
            ng = mid
    return ok

class RollingHash:

    MOD = 2 ** 64
    b = 10 ** 8 + 7

    def __init__(self, S):
        # 各文字を数値に変換しておく
        S = [ord(s)-97 for s in S]

        self.len = len(S)
        self.pow = [1] * (self.len+1)
        for i in range(self.len):
            self.pow[i+1] = self.pow[i] * self.b
            self.pow[i+1] %= self.MOD
        # ハッシュの生成
        self.hash = [0] * (self.len+1)
        for i in range(self.len):
            self.hash[i+1] = self.hash[i] * self.b + S[i]
            self.hash[i+1] %= self.MOD
    
    # 区間[i,j)のハッシュ値を取得
    def get(self, l, r):
        return (self.hash[r] - self.hash[l] * self.pow[r-l]) % self.MOD

def calc(m):
    A = set()
    for i in range(N-m*2+1):
        a_hash = rh.get(i, i+m)
        if a_hash not in A:
            for j in range(i+m, N-m+1):
                b_hash = rh.get(j, j+m)
                if a_hash == b_hash:
                    return True
            A.add(a_hash)
    return False

rh = RollingHash(S)
print(bisearch_max(0, N, calc))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
S = input()

def bisearch_max(mn, mx, func):
    """ 条件を満たす最大値を見つける二分探索 """

    ok = mn
    ng = mx
    while ok+1 < ng:
        mid = (ok+ng) // 2
        if func(mid):
            # 上を探しに行く
            ok = mid
        else:
            # 下を探しに行く
            ng = mid
    return ok

def calc(m):
    A = set()
    for i in range(N-m*2+1):
        a = S[i:i+m]
        # 既に探したaはもう1回探す必要ない
        if a not in A:
            b = S[i+m:]
            if b.find(a) != -1:
                return True
        A.add(a)
    return False

print(bisearch_max(0, N, calc))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
S = input()

def bisearch_max(mn, mx, func):
    """ 条件を満たす最大値を見つける二分探索 """

    ok = mn
    ng = mx
    while ok+1 < ng:
        mid = (ok+ng) // 2
        if func(mid):
            # 上を探しに行く
            ok = mid
        else:
            # 下を探しに行く
            ng = mid
    return ok

def calc(m):
    A = set()
    for i in range(N-m*2+1):
        a = S[i:i+m]
        b = S[i+m:]
        # 既に探したaはもう1回探す必要ない
        if a not in A:
            if b.find(a) != -1:
                return True
        A.add(a)
    return False

print(bisearch_max(0, N, calc))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
S = input()

def bisearch_max(mn, mx, func):
    """ 条件を満たす最大値を見つける二分探索 """

    ok = mn
    ng = mx
    while ok+1 < ng:
        mid = (ok+ng) // 2
        if func(mid):
            # 上を探しに行く
            ok = mid
        else:
            # 下を探しに行く
            ng = mid
    return ok

def calc(m):
    for i in range(N-m*2+1):
        a = S[i:i+m]
        b = S[i+m:]
        if b.find(a) != -1:
            return True
    return False

print(bisearch_max(0, N, calc))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
S = input()

def bisearch_max(mn, mx, func):
    """ 条件を満たす最大値を見つける二分探索 """

    ok = mn
    ng = mx
    while ok+1 < ng:
        mid = (ok+ng) // 2
        if func(mid):
            # 上を探しに行く
            ok = mid
        else:
            # 下を探しに行く
            ng = mid
    return ok

def calc(m):
    for i in range(N-m*2+1):
        a = S[i:i+m]
        b = S[i+m:]
        if b.count(a):
            return True
    return False

print(bisearch_max(0, N, calc))

Submission status: Time Limit Exceeded

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

    dp = [[0] * 5005 for i in range(5005)]

    for i in range(N, 0, -1):
        for j in range(N, 0, -1):
            if S[i-1] != S[j-1]:
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i+1][j+1] + 1

    result = 0
    for i in range(N):
        for j in range(N):
            if i >= j:
                continue
            now = min(dp[i][j], j-i)
            result = max(now, result)

    print(result)

Submission status: Time Limit Exceeded

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

dp = [[] for i in range(n)]
for i in range(n):
    r = dp[i]
    prev = s[i]
    r.append(prev)
    for j in range(i + 1, n):
        nxt = prev + s[j]
        r.append(nxt)
        prev = nxt

res = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        tt = res
        mx = min(j - i, n - j)
        if tt >= mx:
            continue
        while tt < mx:
            if dp[i][tt] != dp[j][tt]:
                break
            else:
                tt += 1
        res = max(res, tt)

print(res)