Problem:


Score : 500 points

Problem Statement

Given is a string S of length N.

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

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

l_1 + len \leq l_2

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

If there is no such integer len, print 0.

Constraints

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

|S| = N

S consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

N
S

Output

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

Sample Input 1

5
ababa

Sample Output 1

2

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

Sample Input 2

2
xy

Sample Output 2

0

No non-empty string satisfies the conditions.

Sample Input 3

13
strangeorange

Sample Output 3

5



Sample input:
5
ababa


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = list(input())
ba = ord("a")
for i in range(N):
  S[i] = ord(S[i]) - ba + 1
B = 27
mod = 10 ** 11 + 7
def contain(a, b):
  al = len(a)
  bl = len(b)
  #print(al, a)
  if al > bl: return False
  t = pow(B, al)
  ah = 0; bh = 0
  for i in range(al):
    ah = ah * B + a[i]
    ah %= mod
    bh = bh * B + b[i]
    bh %= mod
  for i in range(bl - al + 1):
    if ah == bh: return True
    if i + al < bl:
      #print(i, i + al)
      bh = bh * B + b[i + al] - b[i] * t
      bh %= mod
  return False
res = 0
for i in range(N):
  r = min(i + N // 2, N + 1)
  l = i + res + 1
  m = (l + r) // 2
  if l > r: continue
  while r - l > 3:
    m = (l + r) // 2
    if contain(S[i: m], S[m: ]):
      l = m
      res = max(res, m - i)
    else:
      r = m
  if m <= N:
    if contain(S[i: m + 1], S[m + 1: ]):
      res = max(res, m + 1 - i)
  if m + 1 <= N:
    if contain(S[i: m + 2], S[m + 2: ]):
      res = max(res, m + 2 - i)
  if m + 2 <= N:
    if contain(S[i: m + 3], S[m + 3: ]):
      res = max(res, m + 3 - i)
print(res)

Submission status: Time Limit Exceeded

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

d = [[0 for i in range(n)] for j in range(n)]

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

Submission status: Time Limit Exceeded

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

lenS = len(s)
#print(lenS)
ans = 0
tempAns = 0
for i in reversed(range(1,lenS//2+1)):
	for j in range(0,n-i+1):
		tempS = s[j:j+i]
		#print(tempS)
		for k in range(1,n-i-j+1):
			if (tempS == s[j+i+k-1:j+2*i+k-1]):
				ans = i
				break
			#print(s[j+i+k-1:j+2*i+k-1], i, j, k)
		if (ans > 0):
			break
	if (ans > 0):
		break
print(ans)

Submission status: Time Limit Exceeded

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

lenS = len(s)
#print(lenS)
ans = 0
tempAns = 0
for i in range(1,lenS//2+1):
	for j in range(0,n-i+1):
		tempS = s[j:j+i]
		#print(tempS)
		for k in range(1,n-i-j+1):
			if (tempS == s[j+i+k-1:j+2*i+k-1]):
				ans = i
				break
			#print(s[j+i+k-1:j+2*i+k-1], i, j, k)
		if (ans == i):
			break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
S=input()
dp=[[0]*(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]:
            continue
        else:
            dp[i][j] = dp[i+1][j+1] + 1

ans=0
for i in range(n):
    for j in range(n):
        if i>=j:
            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()
n_list = [0] * N
max_length = 0
for i in range(N):
    for j in range(max_length,N):
        if S[i:j] in S[j:N]:
            continue
        else:
            current_length = j-i-1
            if current_length > max_length:
                max_length = current_length
            break
print(max_length)

Submission status: Time Limit Exceeded

Solution code:
n,s=open(0)
n=int(n)
a=0
for i in range(n):
  t=0
  for v,w in zip(s,s[i:n]):
    t=-~t*(v==w)
    a=max(a,min(t,i))
print(a)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(input())
alfa = list('abcdefghijklmnopqrstuvwxyz')
a = []
ans = 0

for i in range(26):
    a = []
    for j in range(n):
        if s[j] == alfa[i]:
            a.append(j)
    for j in range(len(a)):
        for k in range(j,len(a)):
            num = 0
            count = 0
            if j != k:
                while (num <= n // 2 and a[k] + num < n and a[j] + num < a[k]):
                    if s[a[j]+num] == s[a[k]+num]:
                        count += 1
                        num += 1
                    else:
                        break
                if count > ans:
                    ans = count
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve(n, s, MOD):
    d = 26
    ttt = [ord(c) - 97 for c in s]

    ttx = []
    c = 1
    for t in ttt[::-1]:
        ttx.append(t * c % MOD)
        c = c * d % MOD
    ttx.reverse()
    ttc = [0]
    for t in ttx:
        ttc.append((ttc[-1] + t) % MOD)

    for l in range(n // 2, 0, -1):
        appeared = []
        comparing = set()
        l2 = l * 2
        p = 1

        for i in range(l, n + 1):
            t = (ttc[i] - ttc[i - l]) * p % MOD
            if i >= l2:
                comparing.add(appeared[i - l2])
                if t in comparing:
                    return l
            appeared.append(t)
            p = p * d % MOD

    return 0


n = int(input())
s = input()
print(min(solve(n, s, MOD) for MOD in (1000000000039,)))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S =  input()
max_length = 0
for i in range(N):
    j = i + 1
    while S[i:j] in S[j:N]:
        current_length = j-i
        if current_length > max_length:
            max_length = current_length
        j += 1
    '''
    #for j in range(i+1,N):
        if S[i:j] in S[j:N]:
            continue
        else:
            current_length = j-i-1
            if current_length > max_length:
                max_length = current_length
            break
    '''
print(max_length)

Submission status: Time Limit Exceeded

Solution code:
def solve(n, s, MOD):
    d = 26
    ttt = [ord(c) - 97 for c in s]

    ttx = []
    c = 1
    for t in ttt[::-1]:
        ttx.append(t * c % MOD)
        c = c * d % MOD
    ttx.reverse()
    ttc = [0]
    for t in ttx:
        ttc.append((ttc[-1] + t) % MOD)

    for l in range(n // 2, 0, -1):
        appeared = []
        comparing = set()
        l2 = l * 2
        p = 1

        for i in range(l, n + 1):
            t = (ttc[i] - ttc[i - l]) * p % MOD
            if i >= l2:
                comparing.add(appeared[i - l2])
            if t in comparing:
                return l
            appeared.append(t)
            p = p * d % MOD

    return 0


n = int(input())
s = input()
print(min(solve(n, s, MOD) for MOD in (999999999989, 1000000000039)))

Submission status: Time Limit Exceeded

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

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

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve(n, s, MOD):
    d = 26
    ttt = [ord(c) - 97 for c in s]

    ttx = []
    c = 1
    for t in ttt[::-1]:
        ttx.append(t * c % MOD)
        c = c * d % MOD
    ttx.reverse()
    ttc = [0]
    for t in ttx:
        ttc.append((ttc[-1] + t) % MOD)

    for l in range(n // 2, 0, -1):
        appeared = []
        comparing = set()
        l2 = l * 2
        p = 1

        for i in range(l, n + 1):
            t = (ttc[i] - ttc[i - l]) * p % MOD
            if i >= l2:
                comparing.add(appeared[i - l2])
            if t in comparing:
                return l
            appeared.append(t)
            p = p * d % MOD

    return 0


n = int(input())
s = input()
print(min(solve(n, s, MOD) for MOD in (999999999999999967, 999999999999999989)))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S =  input()
max_length = 0
for i in range(N):
    for j in range(i+1,N):
        if S[i:j] in S[j:N]:
            continue
        else:
            current_length = j-i-1
            if current_length > max_length:
                max_length = current_length
            break
print(max_length)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
DP = [[0]*5005 for _ in range(5005)]

for i in range(N):
    for j in range(N):
        if S[i] == S[j]:
            DP[N-i][N-j] = DP[N-i+1][N-j+1] + 1
ans = 0
for i in range(N):
    for j in range(N):
        if i >= j:
            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 = str(input())
dp = [[0 for i in range(N+1)] for i in range(N+1)]

for i in reversed(range(N)):
    for j in reversed(range(N)):
        if S[i] == S[j]:
            dp[i][j] = dp[i+1][j+1] + 1
ans = 0
for i in range(N):
    for j in range(N):
        if j > i:
            tmp = min(j-i,dp[i][j])
            ans = max(tmp,ans)
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

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

print(bisearch_max(0, N, calc))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())
S = list(input().strip())

dp = [0] * N
max_leng = 0

for i in range(0, N):
    leng = 0
    idx_i = i
    sta_j = -1

    j = i - 1
    while j > -1:
        if sta_j == idx_i:
            leng = 0
            idx_i = i
            j = sta_j-1
            sta_j = -1
            continue

        if S[idx_i] == S[j]:
            if leng == 0:
                sta_j = j
            leng += 1
            idx_i -= 1
            max_leng = max(leng, max_leng)
        else:
            j += leng
            leng = 0
            idx_i = i
        j -= 1
print(max_leng)

Submission status: Time Limit Exceeded

Solution code:
import collections
n=int(input())
s=input()
ans=0
d=collections.defaultdict(int)
for i in range(n):
  t=""
  for j in range(i,n):
    t+=s[j]
    if 0<d[t]<i and j-i+1>ans:
      ans=j-i+1
    elif d[t]==0 and i+2*(j-i+1)<=n:
      d[t]=j
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S =  input()
max_length = 0
for i in range(N):
    max_j = (N -i)//2
    for j in range(max_j):
        current_length = max_j-j
        if S[i:i+current_length] in S[i+current_length:N]:
            if current_length > max_length:
                max_length = current_length
            break
print(max_length)

Submission status: Time Limit Exceeded

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

    min_val = 0
    if N > 26:
        min_val = 1
    elif N >= (26 ** 2 + 1) * 2:
        min_val = 2

    for i in range(N//2, 0, -1):
        if i == min_val:
            print(i)
            exit()
        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:
import sys

stdin = sys.stdin

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

n = ni()
s = input()
dp = [[0] * 5005 for _ in range(5005)]
for i in range(n)[::-1]:
    for j in range(n)[::-1]:
        if s[i] != s[j]:
            dp[i][j] = 0
        else:
            dp[i][j] = dp[i+1][j+1] + 1
ans = 0
for i in range(n):
    for j in range(n):
        if i >= j: 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=list(input())

M=N//2
m=0

for _ in range(30):
    i=(M+m)//2
    #print(M,m,i)
    F=0
    for j in range(N-i):
        if M-m<=1:
            F=2
            break
        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]:
                F=1
    if F==1:
        m=i
    elif F==0:
        M=i
    else:
        F=2
        for j in range(N-M):
            for k in range(j+M,N-M+1):
                #print(M,S[j:j+M],S[k:k+M])
                if S[j:j+M]==S[k:k+M]:
                    F=3
        if F==3:
            print(M)
            exit()
        else:
            print(m)
            exit()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S =  input()
dp = [0] * N
min_selct = N//2
max_length = 0
for i in range(N):
    max_j = (N -i)//2
    for j in range(max_j):
        current_length = max_j-j
        if S[i:i+current_length] in S[i+current_length:N]:
            max_length = max(max_length,current_length)
            break
print(max_length)

Submission status: Time Limit Exceeded

Solution code:
def find_min_true(n, f):
    i, j = 0, n
    while i < j:
        h = (i+j) >> 1
        if not f(h):
            i = h + 1
        else:
            j = h
    return i

N=int(input())
S=input()
def search():
    def judge(slen):
        for l1 in range(0, N+1-2*slen):
            subst = S[l1:l1+slen]
            result = S.find(subst, l1+slen)
            #print("slen", slen, "l1", l1, "subst", subst, "result", result)
            if result != -1:
                return False
        return True
    return find_min_true(2501, judge)
ans = search()
if ans == -1:
    print(0)
else:
    print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S =  input()
dp = [0] * N
min_selct = N//2
max_length = 0
for i in range(N):
    max_j = (N -i)//2
    for j in range(max_j):
        current_length = max_j-j
        if S[i+current_length:N].find(S[i:i+current_length]) >= 0:
            max_length = max(max_length,current_length)
            break
print(max_length)

Submission status: Time Limit Exceeded

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


def solve(N: int, S: str):
    dp = [[0 for _ in range(N)] for _ in range(N)]

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

    res = 0
    for i in range(N-2,-1,-1):
        for j in range(N-2,i,-1):
            if S[i] == S[j]:
                dp[i][j] = dp[i+1][j+1] + 1
                l = dp[i][j]
                if j >= i+l:
                    res = max(res,l)

    print(res)



# Generated by 1.1.4 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:
n=int(input())
s=input()
ans=0
d=dict()
for i in range(n):
  t=""
  for j in range(i,n):
    t+=s[j]
    if d.get(t,0)==0:
      d[t]=j
    else:
      if d[t]<i:
        ans=max(ans,j-i+1)
print(ans)

Submission status: Time Limit Exceeded

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

for i in range(N):
  s_max = 0
  s_max2 = 0
  A = []
  for k in range(N - i):
    if S[k + i] == S[k]:
      A.append('1')
    else:
      A.append('0')
      
  for j in range(N -i):
    if A[j] == '1':
      s_max2 = s_max2 + 1
    else:
      if s_max < s_max2:
        s_max = s_max2
      s_max2 = 0
      
    if s_max < s_max2:
      s_max = s_max2
      
  if s_max > i:
    s_max = i
    
  if _max < s_max:
    _max = s_max
    
print(_max)

Submission status: Time Limit Exceeded

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


def solve(N: int, S: str):
    dp = [[0 for _ in range(N)] for _ in range(N)]

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

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

    res = 0
    for i in range(N):
        for j in range(i+1,N):
            l = dp[i][j]
            if j >= i+l:
                res = max(res,l)

    print(res)



# Generated by 1.1.4 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:
# -*- 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):
    dp = [[0] * (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
    
    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            ans = max(ans, min(j-i, dp[i][j]))

    return ans


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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = list(input())
ba = ord("a")
for i in range(N):
  S[i] = ord(S[i]) - ba + 1
B = 27
mod = 10 ** 11 + 7
def contain(a, b):
  al = len(a)
  bl = len(b)
  #print(al, a)
  if al > bl: return False
  t = pow(B, al)
  ah = 0; bh = 0
  for i in range(al):
    ah = ah * B + a[i]
    bh = bh * B + b[i]
  for i in range(bl - al + 1):
    if ah == bh: return True
    if i + al < bl:
      #print(i, i + al)
      bh = bh * B + b[i + al] - b[i] * t
  return False
res = 0
for i in range(N):
  r = min(i + N // 2, N + 1)
  l = i + 1
  m = (l + r) // 2
  while r - l > 3:
    r = min(i + N // 2, N + 1)
    l = i + 1
    m = (l + r) // 2
    if contain(S[i: m], S[m: ]):
      l = m
      res = max(res, m - i)
    else:
      r = m
  if m <= N:
    if contain(S[i: m + 1], S[m + 1: ]):
      res = max(res, m + 1 - i)
  if m + 1 <= N:
    if contain(S[i: m + 2], S[m + 2: ]):
      res = max(res, m + 2 - i)
  if m + 2 <= N:
    if contain(S[i: m + 3], S[m + 3: ]):
      res = max(res, m + 3 - i)
print(res)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
ans=0
d=dict()
for i in range(n):
  t=s[i]
  if d.get(t,0)==0:
    d[t]=i
  else:
    ans=max(ans,1)
  for j in range(i+1,n):
    t+=s[j]
    if d.get(t,0)==0:
      d[t]=j
    else:
      if d[t]<i:
        ans=max(ans,j-i+1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S =  input()
dp = [0] * N
min_selct = N//2
max_length = 0
for i in range(N):
    for j in range((N -i)//2): 
        if S[i+j+1:N].find(S[i:i+j+1]) >= 0:
            max_length = max(max_length,j+1)
print(max_length)

Submission status: Time Limit Exceeded

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


def solve(N: int, S: str):
    dp = [[0 for _ in range(N)] for _ in range(N)]

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

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

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

    res = 0
    for i in range(N):
        for j in range(i+1,N):
            l = dp[i][j]
            if j >= i+l:
                res = max(res,l)

    print(res)



# Generated by 1.1.4 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 lcp(S):
    N = len(S)
    prefix = [0] * N
    j = 0
    for i in range(1, N):
        if i + prefix[i - j] < j + prefix[j]:
            prefix[i] = prefix[i - j]
        else:
            k = max(0, j + prefix[j] - i)
            while i + k < N and S[k] == S[i + k]:
                k += 1
            prefix[i] = k
            j = i
    prefix[0] = N
    return prefix

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

ans = 0
for j in range(N):
    prefix = lcp(S[j:])
    for i, p in enumerate(prefix):
        if p <= i:
            ans = max(ans, p)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, Counter
from itertools import combinations
import re

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

d = defaultdict(list)
for i in range(N-4):
  d[S[i:i+5]].append(i)

m = 0
for x in d.values():
  if len(x) > 1:
    for i, j in combinations(x, 2):
      if j < i + 5:
        continue
      l = 5
      while i+l < j and j+l < N and S[i+l] == S[j+l]:
        l += 1
      m = max(m, l)

for k in range(4, 0, -1):
  if m > 0:
    break
  d = {}
  for i in range(N-k+1):
    x = S[i:i+k]
    if x in d and d[x] + k <= i:
      m = k
      break
    else:
      d[x] = i

print(m)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from itertools import combinations
 
 
def p_e():
    N = int(input())
    S = input()
 
    S_idx = defaultdict(list)
 
    for i in range(N):
        S_idx[S[i]].append(i)
 
    max_ans = 0
    for c in S_idx.keys():
        if len(S_idx[c]) <= 1:
            continue
 
        comb_list = list(combinations(S_idx[c], 2))
        i = 1
 
        f = True
        while f:
            i += 1
            f = False
            for comb in comb_list:
                a = comb[0]
                b = comb[1]
                if a + i - 1 >= N or b + i - 1 >= N:
                    comb_list.remove(comb)
                    continue
 
                if a + i - 1 >= b:
                    comb_list.remove(comb)
                    continue
 
                if S[a + i - 1] == S[b + i - 1]:
                    f = True
                else:
                    comb_list.remove(comb)
 
        if max_ans < i - 1:
            max_ans = i - 1
 
    print(max_ans)
 
 
if __name__ == '__main__':
    p_e()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S =  input()
dp = [0] * N
min_selct = N//2
max_length = 0
for i in range(N):
    for j in range(N -i): 
        if S[i+j+1:N].find(S[i:i+j+1]) >= 0:
            max_length = max(max_length,j+1)
print(max_length)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7
P = 97

def solve(N, S):
    A = [ord(c) - ord('a') + 2 for c in S]
    H = [0]
    pwr = 1
    for x in A:
        H.append(H[-1] + x * pwr)
        H[-1] %= MOD
        pwr = pwr * P % MOD

    def gethash(i, j):
        ha = H[j] - H[i]
        ha *= pow(pow(P, i, MOD), MOD-2, MOD)
        return ha % MOD

    def match(L):
        if L == 0: return True
        for i in xrange(N - L + 1):
            h1 = gethash(i, i+L)
            for j in xrange(i + L, N - L + 1):
                if h1 == gethash(j, j+L) and A[i:i+L] == A[j:j+L]:
                    return True

    #print map(doublematch, range(len(A)))
    lo, hi = 0, len(A) / 2
    while lo < hi:
        mi = (lo + hi + 1) / 2
        if match(mi):
            lo = mi
        else:
            hi = mi - 1
    return lo

print solve(int(raw_input()), raw_input())

Submission status: Time Limit Exceeded

Solution code:
def longestRepeatedSubstring(str): 
  
    n = len(str) 
    LCSRe = [[0 for x in range(n + 1)]  
                for y in range(n + 1)] 
  
    res = "" # To store result 
    res_length = 0 # To store length of result 
  
    # building table in bottom-up manner 
    index = 0
    for i in range(1, n + 1): 
        for j in range(i + 1, n + 1): 
              
            # (j-i) > LCSRe[i-1][j-1] to remove 
            # overlapping 
            if (str[i - 1] == str[j - 1] and
                LCSRe[i - 1][j - 1] < (j - i)): 
                LCSRe[i][j] = LCSRe[i - 1][j - 1] + 1
  
                # updating maximum length of the 
                # substring and updating the finishing 
                # index of the suffix 
                if (LCSRe[i][j] > res_length): 
                    res_length = LCSRe[i][j] 
                    index = max(i, index) 
                  
            else: 
                LCSRe[i][j] = 0
  
    # If we have non-empty result, then insert  
    # all characters from first character to  
    # last character of string 
    if (res_length > 0): 
        for i in range(index - res_length + 1, 
                                    index + 1): 
            res = res + str[i - 1] 
  
    return res 
  
# Driver Code 
if __name__ == "__main__": 
  n=int(input())
  str=input()
  print(len(longestRepeatedSubstring(str)))

Submission status: Time Limit Exceeded

Solution code:
def main():
    n=int(input())
    s=input()
    m=0
    for i in range(1,n):
        d,c=0,0
        for j in range(i,n):
            if s[j-i]==s[j]:c+=1
            else:
                d=max(c,d)
                c=0
        m=min(max(c,d,m),i)
    print(m)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = str(input())
list = [str(i) for i in S]
#print(list)

result = 0
maxval = 0

for length in range (1, N):
    counter = 0
    for i in range(N -length):
        if list[i] == list[i + length]:
            counter += 1
#            print('hit',counter)
        else:
#            print('hit2', counter)
            maxval = max (counter, maxval)
            counter = 0
    maxval = max (counter, maxval)
    maxval = min (maxval, length)
#    print ('---')


print (maxval)

Submission status: Time Limit Exceeded

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

m = 0
for i in range(int(n / 2) + 1):
    for j in range(i + 1, n + 1):
        if s[j:].find(s[i:j]) > -1:
            m = max(m, len(s[i:j]))
print(m)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
ans = 0
flag = False
for i in range(N // 2,-1,-1):
    for j in range(N-i*2+1):
#        a = S[j:i+j]
#        b = S[i+j:]
        if S[i+j:].find(S[j:i+j]) != -1:
#            print("find!")
            ans = i
            flag = True
            break
    if flag:
        break
print(ans)

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 i in range(m+1)]
for i in range(N):
    SSS[OB[i]].append(i)
SSS.sort()
for n in range(len(SSS)):
    lss = len(SSS[n])
    for i in range(lss):
        for j in range(i,lss):
            ni = SSS[n][i]
            nj = SSS[n][j]
            if i==j or ans>nj-ni or ans>N-nj:
                continue
            id = 0
            while True:
                if nj+id>=N or ni+id>=nj:
                    break
                if S[ni+id]==S[nj+id]:
                    id += 1
                else:
                    break
            ans = max(ans,id)
print(ans)

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):
    w = set()
    for j in range(n-2*i,-1,-1):
        #for k in range(j+i,n-i+1):
        #for k in range(n-i,j+i-1,-1):
        w.add(s[j+i:j+2*i])
        #print(w)
        if s[j:j+i] in w:
            print(i)
            exit(0)    
if f1:
    print(1)
else:
    print(0)