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:
# -*- 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):
    if N < 27:
        if Counter(S).most_common(1)[0][1] == 1:
            return 0

    ans = 0
    t = defaultdict(list)
    for i in range(N-1):
        t[S[i:i+1]].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 = 1
    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
    # for _ in range(1000):
    #     # S = ''.join(random.choices('abcdefghijklmnopqrstuwzxyz', k=N))
    #     S = ''.join(random.choices('abcde', k=N))
    #     # S = ''.join(random.choices('a', k=N))
    #     # print(S)
    #     print(slv(N, S))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
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
from heapq import heappop, heappush

n = ni()
s = ns()

lenstr = []
dic = defaultdict(list)

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

ans = 0

while lenstr:
    leni, stri = heappop(lenstr)
    leni *= -1
    if dic[stri][-1] - dic[stri][0] >= leni:
        ans = max(ans, leni)
        break

print(ans)

Submission status: Time Limit Exceeded

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

dic=defaultdict(list)

for i in range(n-1):
    for j in range(i+1,n+1):
        if dic[s[i:j]]==[]:
            dic[s[i:j]]+=[j]
    
        elif max(dic[s[i:j]])<=i:
            dic[s[i:j]]+=[j]

ans=0
for key,value in dic.items():
    if len(value) <2:
        continue
    if len(value) >=2:
        if len(key) > ans:
            ans=len(key)
print(ans)

Submission status: Time Limit Exceeded

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

max_count = 0
for i in range(n):
    for j in range(n):
        if i >= j:
            continue
        if s[i] == s[j]:
            count = max_count + 1
            while True:
                if i+count <= j and s[i:i+count] == s[j:j+count]:
                    #print(count, i, s[i:i+count])
                    count += 1
                else:
                    max_count = max(max_count, count-1)
                    break
print(max_count)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

ngram = [defaultdict(list) for i in range(N)]


for i in range(len(S)):
    # i文字
    for j in range(len(S) - i):
        # j文字目から
        ngram[i][S[j:i+j+1]].append(j)

answer = 0
for i in range(N-1, -1, -1):
    # print(i, ngram[i])
    for indexes in ngram[i].values():
        if len(indexes) > 1 and indexes[-1] - indexes[0] > i:
            answer = i + 1
    if answer != 0:
        break
print(answer)

Submission status: Time Limit Exceeded

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

M = N // 2

for i in range(M, 1, -1):
    for j in range(0, N - (2 * i) + 1):
        S1 = S[j:j+i]

        for k in range(j+i, N-i+1):
            if S1 == S[k:k+i]:
                print(i)
                sys.exit()
            # S2 = S[k:k+i]

print(0)

Submission status: Time Limit Exceeded

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


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

    dp = collections.defaultdict(set)
    for i,s in enumerate(S):
        for k,v in list(dp.items()):
            for vv in v:
                if vv + len(k) == i:
                    dp[k+s].add(vv)
        dp[s].add(i)
    
    dp_sorted = sorted(((k,v) for k,v in dp.items() if len(v) > 1),key=lambda x:len(x[0]),reverse=True)

    for k,v in dp_sorted:
        if max(v) - min(v) >= len(k):
            print(len(k))
            return

    print(0)

# 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()
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+max(answer-1, 1)
    if now+answer>=n+1:
        break
 
print(answer)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N = int(input())
    S = input()
    
    max_len = 0
    
    for i in range(1,N//2+1):
        # print([S[j:j+i] for j in range(N-i+1)])
        search_dict = {}
        for j in range(N-i+1):
            if S[j:j+i] in search_dict:
                if search_dict[S[j:j+i]] + i <= j:
                    max_len = i
                    break
            else:
                search_dict[S[j:j+i]] = j
                
    print(max_len)
    
solve()

Submission status: Time Limit Exceeded

Solution code:
import re
N = int(input())
S = input()
A = []
k = -1
for s in S:
    if s in A:
        k = 0
        break
    else:
        A.append(s)
if k==-1:
    ans=0
else:
    ans = 1
    for l in range(N):
        for r in range(l+1,N):
            if r-l<=ans or N-r<=ans:continue
            text = S[r:]
            if re.search(S[l:r], text):
                ans = r-l
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# ABC141e
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

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

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N = int(input())
    Ss = input()

    strAs = [set() for _ in range(N)]
    for L in range(N-1):
        maxLen = (N-L)//2
        for R in range(L, L+maxLen):
            ss = Ss[L:R+1]
            strAs[R].add(ss)
    strBs = [set() for _ in range(N)]
    for R in reversed(range(1, N)):
        maxLen = (R+1)//2
        for L in range(R-maxLen+1, R+1):
            ss = Ss[L:R+1]
            strBs[L].add(ss)

    ans = 0
    strCands = set()
    for iEn in range(N-1):
        for strA in strAs[iEn]:
            strCands.add(strA)
        for strB in strBs[iEn+1]:
            if strB in strCands:
                lenB = len(strB)
                if lenB > ans:
                    ans = lenB

    print(ans)

solve()

Submission status: Time Limit Exceeded

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

max_len = 0


for i in range(1,(n//2+1)):
    s_closed = set()
    fl = 0
    for j in range(n-i+1):
        if fl == 1:
            break
        ss = s[j:j+i]
        if ss in s_closed:
            j += i-1
            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
                fl = 1
                break

print(max_len)

Submission status: Time Limit Exceeded

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


def solve(N: int, S: str):
    
    ans = 0
    for i in range(N):
        for j in range(i+1, min(i+1+N//2, N)):
            st = S[i:j]
            # print(st)
            if(S.count(st) > 1):
                ans = max(ans, len(st))

    print(ans)
    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:
N = int(input())
S = input()


def isok(n):
    for i in range(N-2*n+1):
        now = S[i:i+n]
        if S[i+n:].find(now) != -1:
            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:
from collections import defaultdict
n = int(input())
s = input()
def test(n, s):
    table = defaultdict(list)
    best = 0
    for i in range(n):
        sub = ""
        for j in range(i, n):
            sub += s[j]
            if sub in table and table[sub][0] <= j-len(sub):
                best = max(len(sub), best)    
            table[sub].append(j)
    return best

print(test(n, s))

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()
    T = [-1] * N

    sToIndex = defaultdict(int)
    now = 1

    for i, s in enumerate(S):
        if not s in sToIndex:
            T[i] = now
            sToIndex[s] = now
            now += 1
        else:
            T[i] = sToIndex[s]

    cumT = [0] * (N + 1)
    for i in range(1, N + 1):
        cumT[i] = cumT[i - 1] + T[i - 1]

    cumTList = []
    for left in range(N):
        for right in range(left + 1, N + 1):
            cumTList.append((cumT[right] - cumT[left], left, right))

    matchList = defaultdict(list)
    for v, l, r in cumTList:
        matchList[v].append((l, r))

    ans = 0
    for v, match in matchList.items():
        for i in range(len(match)):
            for j in range(i + 1, len(match)):
                l1, r1 = match[i]
                l2, r2 = match[j]
                if l2 < r1:
                    continue
                if T[l1: r1] == T[l2: r2]:
                    ans = max(ans, r1 - l1)

    print(ans)

sol()

Submission status: Time Limit Exceeded

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

mod = 10 ** 9 + 7
hash = [ord(S[0])-97]
for s in S[1:] :
    hash.append((hash[-1] * 26 + ord(s) - 97) % mod)
hash = [0] + hash

M = 0
for i in range(N + 1) :
    for j in range(i + 1, N + 1) :
        for k in range(M+1, N - j + 1) :
            if i + k > j :
                break
            if (hash[j+k] - hash[j] * (26 ** k)) % mod == (hash[i+k] - hash[i] *  (26 ** k)) % mod :
                M += 1
            else :
                break
                
print(M)

Submission status: Time Limit Exceeded

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

max_count = 0
for i in range(n):
    for j in range(n):
        if i >= j:
            continue
        if s[i] == s[j]:
            count = max_count
            while True:
                if i+count <= j and s[i:i+count] == s[j:j+count]:
                    #print(count, i, s[i:i+count])
                    count += 1
                else:
                    max_count = max(max_count, count-1)
                    break
print(max_count)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
maxi=0
for i in range(n):
  for j in range(1+1,n):
    if s.count(s[i:j])>=2:
      maxi=max(maxi,j-i)
if maxi==1:
  print(0)
else:
  print(maxi)

Submission status: Time Limit Exceeded

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

# len 取り得る最大の長さは N / 2

for i in range(N//2, 0, -1):
  for j in range(0, N-2*i+1):
    left = S[j:j+i]
    for k in range(j+i, N-i+1):
      right = S[k:k+i]
      
      # print(i, j, k)
      # print("left : ", left)
      # print("right: ", right)
      
      if left == right:
        print(len(left))
        exit()
        
print(0)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
ans = 0
for i in range(1,n):
    max_seq = 0
    seq = 0
    for s1,s2 in zip(s,s[i:]):
        if s1==s2:
            seq += 1
        else:
            max_seq = max(max_seq,seq)
            seq=0
        if seq == i:
            break
    max_seq = max(max_seq,seq)
    ans = max(ans,max_seq)
print(ans)

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()
    T = [-1] * N

    sToIndex = defaultdict(int)
    now = 1

    for i, s in enumerate(S):
        if not s in sToIndex:
            T[i] = now
            sToIndex[s] = now
            now += 1
        else:
            T[i] = sToIndex[s]

    cumT = [0] * (N + 1)
    for i in range(1, N + 1):
        cumT[i] = cumT[i - 1] + T[i - 1]

    cumTList = []
    for left in range(N):
        for right in range(left + 1, N + 1):
            cumTList.append((cumT[right] - cumT[left], left, right))

    matchList = defaultdict(list)
    for v, l, r in cumTList:
        matchList[v].append((l, r))

    ans = 0
    for v, match in matchList.items():
        for i in range(len(match)):
            for j in range(i + 1, len(match)):
                l1, r1 = match[i]
                l2, r2 = match[j]
                if l2 < r1:
                    continue
                if S[l1: r1] == S[l2: r2]:
                    ans = max(ans, r1 - l1)

    print(ans)

sol()

Submission status: Time Limit Exceeded

Solution code:
def sol():
    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)
    return ans
print(sol())

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n = int(input())
s = input()
for i in range(n//2,0,-1):
  d = defaultdict(list)
  for j in range(n-i+1):
    d[s[j:j+i]].append((j,j+i-1))
  for j in d:
    e = d[j][0][1]
    if e < d[j][-1][0]:
      print(i)
      exit()
print(0)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
S=input()
a=0
ans=0
while a<=n-2:
    x=S[a]
    maxcnt=0
    for j in range(a+1,n):
        if S[j]==x:
            cnt=1
            while cnt<=n-j-1:
                if S[a+cnt]==S[j+cnt] and a+cnt<j:
                    cnt+=1
                else:
                    break
            ans=max(ans,cnt)
            maxcnt=max(maxcnt,cnt)
    a+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)


def solve(N: int, S: str):
    sa = []
    for i in range(N):
        sa.append([S[i:], i])
    sa.sort()
    #print(sa)
    ret = 0
    for i in range(N - 1):
        tmp = 0
        for k in range(i + 1, N):
            s, si = sa[i]
            t, ti = sa[k]
            mx = min(len(s), len(t), abs(si - ti))
            #print(s, t, si, ti, mx)
            j = 0
            while j < mx and s[j] == t[j]:
                j += 1
            if j < tmp:
                break
            tmp = j
        ret = max(ret, tmp)
    print(ret)
    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 re
N = int(input())
S = input()
for i in range(N//2,0,-1):
    for j in range(N-2*i+1):
        if re.search(S[j:j+i],S[j+i:]):
            print(i)
            exit()
print(0)

Submission status: Time Limit Exceeded

Solution code:
import sys
import time
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return sys.stdin.readline().rstrip()
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()

def main():
  start = time.time()
  n = I()
  s = S()
  ok = 0
  ng = n//2+2
  while ok+1 < ng:
    if time.time()-start > 1.9:
      print(2500)
      exit()
    flag = False
    mid = (ok+ng)//2
    for j in range(n-mid):
      if s[j+mid:].find(s[j:j+mid]) != -1:
        flag = True
        break
    if flag:
      ok = mid
    else:
      ng = mid
  print(ok)

if __name__ == '__main__':
  main()

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()

lenstr = []
dic = defaultdict(list)

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

ans = 0

for leni, stri in lenstr:
    if dic[stri][-1] - dic[stri][0] >= leni:
        ans = max(ans, leni)

print(ans)

Submission status: Time Limit Exceeded

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

import re

for leng in range(n-1,0,-1):
    for start in range(n):
        if start+leng > n:
            break
        parts=s[start:start+leng]
        if len(re.findall(parts, s)) > 1:
            print(leng)
            exit()
print(0)

Submission status: Time Limit Exceeded

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

max_length = 0

for i in range(1, n-1):
    tmp_len = 0
    for c1, c2 in zip(s[0:n-i:], s[i::]):
        if c1 == c2:
            tmp_len += 1
        else:
            tmp_len = 0

        max_length = max(max_length, tmp_len)
        if tmp_len >= i:
            break

print(max_length)

Submission status: Time Limit Exceeded

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

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

n = ni()
s = input()
d = {}
ln = len(s)
for i in range(ln):
    for j in range(i, min(ln, i+1+ln//2)):
        tx = s[i:j+1]
        if tx not in d.keys():
            d[tx] = [i]
        else:
            d[tx].append(i)
ans = 0
for k, v in d.items():
    if len(v) >= 2:
        l = len(k)
        if max(v) - min(v) >= l:
            if ans < l:
                ans = l
print(ans)

Submission status: Time Limit Exceeded

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

max_count = 0
for i in range(n):
    for j in range(n):
        if i >= j:
            continue
        if s[i] == s[j]:
            count = 1
            while True:
                if i+count <= j and s[i:i+count] == s[j:j+count]:
                    #print(count, i, s[i:i+count])
                    count += 1
                else:
                    max_count = max(max_count, count-1)
                    break
print(max_count)

Submission status: Time Limit Exceeded

Solution code:
import collections
def main():

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

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

Submission status: Time Limit Exceeded

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


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

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):
    for l2 in range(l1 + le, n - le + 1):
      if s[l1:l1+le] == s[l2:l2+le]:
        ans = le
        break
    else:
      continue
    break
  else:
    continue
  break
print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(N//2+1):
	for j in range(i+1, N//2+2):
		s = S[i:j]

		if s in S[j:]:
			ans = max(len(s), ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
ans = 0
for i in range(1, N):
    cnt = 0
    for j in range(N-i):
        if S[j] == S[i+j]:
            cnt += 1
        else:
            ans = max(ans, min(cnt, i))
            cnt = 0
    ans = max(ans, min(cnt, i))
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):
        a = S[i:i+m]
        for j in range(i+m, N):
            b = S[j:j+m]
            if a == b:
                return True
    return False

print(bisearch_max(0, N, calc))

Submission status: Time Limit Exceeded

Solution code:
def hersCode(n):
  ok = 0
  ng = n
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if nasu(mid):
      ok = mid
    else:
      ng = mid
  return ok

def nasu(n):
  for i in range(N - n * 2 + 1):
    for j in R[S[i]]:
      if i + n > j: continue
      if j + n > N: continue
      if honya(i, j, n):
        return True
  return False

def honya(x, y, n):
  for i in range(n):
    if S[x + i] != S[y + i]:
      return False
  return True

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

R = {}
for i in range(N):
  if S[i] not in R:
    R[S[i]] = [i]
  else:
    R[S[i]].append(i)

print(hersCode(N))

Submission status: Time Limit Exceeded

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

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

    p = [list() for i in range(26)]

    for i in range(N):
        p[ord(s[i]) - ord("a")].append(i)
    
    ans = 0
    for i in range(len(p)):
        for j in range(len(p[i])-1):
            for k in range(j+1, len(p[i])):
                ans = max(ans, 1)
                t = 1
                s1 = p[i][j]
                s2 = p[i][k]
                while True:
                    if s1 + t < s2 and s2 + t < N:
                        if s[s1+t] == s[s2+t]:
                            t += 1
                            # print(s[s1+t])
                            ans = max(ans, t)
                        else:
                            break
                    else:
                        break
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

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

saisho = [{} for _ in range(N // 2 + 1)]

for i in range(1, N // 2 + 1):  # 文字のながさ
    for j in range(N):  # とってくる文字の最初
        # よくない
        if j + i > len(S):
            continue
        bubunn = S[j:j+i]
        if bubunn not in saisho[i]:
            saisho[i][bubunn] = []

        saisho[i][bubunn].append(j)

# print(saisho)

for i in reversed(range(1, N // 2 + 1)):
    if len(saisho[i]) == 0:
        continue

    for bubunn in saisho[i]:
        left = saisho[i][bubunn][0]
        right = saisho[i][bubunn][-1]
        if left + i <= right:
            print(i)
            sys.exit(0)

print(0)

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()

lenstr = []
dic = defaultdict(list)

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

ans = 0

lenstr.sort(reverse=True)
for leni, stri in lenstr:
    if dic[stri][-1] - dic[stri][0] >= leni:
        ans = leni
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N = int(input())
S = input()
half_N = N//2
for i in range(half_N):
    now_len = half_N - i
    #print(now_len)
    dic = defaultdict(list)

    for j in range(N - now_len+1):
        dic[S[j:j+now_len]].append(j)

    for key, val in dic.items():
        #print(key)
        if len(val) > 1:
            if max(val)-min(val) >= now_len:
                print(now_len)
                exit()
print(0)

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 = ""
    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


    if (res_length > 0):
        for i in range(index - res_length + 1,
                       index + 1):
            res = res + str[i - 1]

    return res


if __name__ == "__main__":
    a = int(input())
    s = input()

    print(len(longestRepeatedSubstring(s)))

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(1, N):
    S1 = S[:i]
    S2 = S[i:]
    ok = 0
    ng = len(S2) + 1
    k = (ok + ng) // 2
    while ng - ok > 1:
        if S1.count(S2[:k]) > 0:
            ok = k
            k = (k + ng) // 2
        else:
            ng = k
            k = (k + ok) // 2
        if k == 0:
            break
    ans = max(ans, k)
print(ans)

Submission status: Time Limit Exceeded

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

max_len = 0


for i in range(1,(n//2+1)):
    s_closed = set()
    fl = 0
    for j in range(n-i+1):
        if fl == 1:
            break
        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
                fl = 1
                break

print(max_len)