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


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

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

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

@mt
def slv(N, S):
    t = defaultdict(list)
    for i, c in enumerate(S):
            t[c].append(i)
    def func(l):
        for j in range(N-l):
            for k in t[S[j]]:
                if k < j+l:
                    continue
                if k >= N-l+1:
                    continue
                for i in range(l):
                    if S[j+i] != S[k+i]:
                        break
                else:
                    return -l
        return 0

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


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


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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


def main():
    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 S2[:k] in S1:
                ok = k
                k = (k + ng) // 2
            else:
                ng = k
                k = (k + ok) // 2
        ans = max(ans, k)
        if ans > N - i - 1:
            break
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
ans = 0
p = 0
q = 1
while True:
    word = s[p:q]
    w_l = len(word)

    for j in range(q, n - w_l + 1):
        if word == s[j:j + w_l]:
            ans = w_l
            break
    else:
        p += 1
    q += 1
    if w_l >= len(s) - q:
        break
print(ans)

Submission status: Time Limit Exceeded

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

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

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

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

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

suffix = []

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

suffix.sort()

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

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

dp = np.array([[0] * (N + 1)] * (N + 1))
for i in range(N):
    dp[i][0] = 0
for j in range(N):
    dp[0][j] = 0

for i in range(1, N):
    for j in range(i + 1, N):
        if S[i] == S[j]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = dp[i][j - 1]
print(dp.max())

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

def ngram_func(words, n):
    return list(zip(*(words[i:] for i in range(n))))

answer = 0
for i in range(N-1, -1, -1):
    # i文字, N
    ngram = ngram_func(S, i)
    ng = defaultdict(lambda : -1)
    for j in range(len(ngram)):
        if ngram[j] not in ng:
            ng[ngram[j]] = j
        elif j - ng[ngram[j]] >= i:
            # print(i, j, ng[ngram[j]], ngram[j])
            answer = i
            break
    if answer != 0:
        break
print(answer)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(N):
    for j in reversed(range(i+1, N)):
        if len(S[i:j]) <= ans:
            break
        #print(S[i:j], S[j:])
        if S[i:j] in S[j:]:
            ans = max(ans, len(S[i:j]))
            break
print(ans)

Submission status: Time Limit Exceeded

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

max=0
for naga in range(1,n//2+1):
    for basho in range(n-naga):
        moji=s[basho:basho+naga]
        kanou=moji in s[basho+naga:]
        if(kanou):
            max=naga
            break

print(max)

Submission status: Time Limit Exceeded

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

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline


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

    ans_list = []

    for i in range(1,n):
        count = 0
        count_list = []
        flag = False
        for j,k in zip(s, s[i:]):
            if flag:
                if j == k:
                    count += 1
                else:
                    count_list.append(count)
                    flag = False
            else:
                if j == k:
                    count = 1
                    flag = True
        ans_list.append(min([i, max(count_list, default=0)]))
    print(max(ans_list))

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)

for n in range(len(SSS)):
    lss = len(SSS[n])
    for i in range(lss):
        for j in range(i,lss):
            if i==j or ans>SSS[n][j]-SSS[n][i] or ans>N-SSS[n][j]:
                continue
            id = 0
            while True:
                if SSS[n][i]+id>=N or SSS[n][j]+id>=N or SSS[n][i]+id>=SSS[n][j]:
                    break
                if S[SSS[n][i]+id]==S[SSS[n][j]+id]:
                    id += 1
                else:
                    break
            ans = max(ans,id)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
ans = True
for length in range(N//2, 0, -1):
    for l1 in range(N - length * 2 + 1):
        if S[l1+length:].find(S[l1:l1+length]) != -1:
            ans = False
            print(length)
            break
    else:   continue   
    break
if ans: print(0)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from bisect import bisect_right
    import sys
    input = sys.stdin.readline
    N = int(input())
    M = N // 2 + N % 2
    S = input()
    D = {c:[] for c in "abcdefghijklmnopqrstuvwxyz"}
    for i in range(N):
        D[S[i]].append(i)
    l = 0
    m = 0

    for l in range(N):
        #if m >= N//2: break
        c = S[l]
        d = D[c]
        j = bisect_right(d, l+m)
        if j == N:
            continue
        for r in d[j:]:
            if r + m > N:
                break
            k = 1
            while S[l+k] == S[r+k] and l+k < r and r+k < N:
                k += 1
            #if k > m: print((l, r, k), S[l:l+k], S[r:r+k])
            m = max(k, m)
    print(m)

def gen():
    import random
    N = 5*10**3
    print(N)
    a = ord('a')
    #print("".join(chr(a + random.randint(0, 3)) for i in range(N)))
    print("".join("a" if i % 2 == 1 else "b" for i in range(N)))
if 1 == 0:
    gen()
else:
    main()

Submission status: Time Limit Exceeded

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

for n in range(len(SSS)):
    lss = len(SSS[n])
    for i in range(lss):
        for j in range(lss):
            if i==j or ans>SSS[n][j]-SSS[n][i] or ans>N-SSS[n][j]:
                continue
            id = 0
            while True:
                if SSS[n][i]+id>=N or SSS[n][j]+id>=N or SSS[n][i]+id>=SSS[n][j]:
                    break
                if S[SSS[n][i]+id]==S[SSS[n][j]+id]:
                    id += 1
                else:
                    break
            ans = max(ans,id)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
dp = [[0]*N for i in range(N)]
pm = 0
ans = 0
for i in range(N-1,0,-1):
  for j in range(i-1,-1,-1):
    if S[i]==S[j]:
      if i<N-1:
        dp[i][j] = min(dp[i+1][j+1]+1, i-j)
      else:
        dp[i][j] = 1
    else:
      if i<N-1:
        dp[i][j] = min(dp[i+1][j+1], i-j)
      else:
        dp[i][j] = 0
    if dp[i][j]>ans:
      ans = dp[i][j]
print(ans)

Submission status: Time Limit Exceeded

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

  for w in range(n//2,0,-1):
    for i in range(n-w):
      if s[i:i+w] in s[i+w:]:
        print(w)
        quit()

  print(0)


if __name__ == '__main__':
  solve()

Submission status: Time Limit Exceeded

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

ans=0
for i in range(N):
	for j in range(i+1,N):
		s=S[i:j]
		if s in S[j:]:
			ans=max(ans,len(s))

print ans

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)

    ans = []

    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)

        ans.append(i - 1)

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


if __name__ == '__main__':
    p_e()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=input()
d={}
for i in range(N):
  for j in range(i,N+1):
    now=S[i:j]
    if now in d:
      d[now]+=1
    else:
      d.setdefault(now,1)
twice={k:v for k, v in d.items() if v>=2}
v1=sorted(twice.keys(), key=len)[::-1] 
for v in v1:
    f=S.find(v)+len(v)
    if v in S[f:]:
        break
print(len(v))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input().strip()
D = {}
for i in range(N):
    a = S[i]
    if a not in D:
        D[a] = []
    D[a].append(i)
dp = [0 for _ in range(N)]
if S[0]==S[1]:
    dp[1]=1
else:
    dp[1] = 0
for i in range(2,N):
    a = S[i]
    cntmax = 0
    for j in D[a]:
        cnt = 1
        while 1:
            if i-j>=cnt+1 and j-cnt>=0 and S[j-cnt:j+1]==S[i-cnt:i+1]:
#                 print("i,j,cnt={},{},{}".format(i,j,cnt))
                cntmax = max(cntmax,cnt+1)
            else:break
            cnt += 1
    dp[i] = max(dp[i-1],cntmax)
print(dp[N-1])

Submission status: Time Limit Exceeded

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

ans = 0
flag = False

for i in range(N):
    for j in range(i+1, N):
        if S[i:j] in S[j:]:
            flag = True
            if len(S[i:j]) > ans:
                ans = len(S[i:j])

print(ans)

Submission status: Time Limit Exceeded

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

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

print(ans)

Submission status: Time Limit Exceeded

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

m = n // 2
while 0 < m:
    for i in range(n): # s[i:i+m]
        rest = s[i+m:]
        if len(rest) < m:
            continue
        if s[i:i+m] in rest:
            print(m)
            sys.exit()
    m -= 1


print(0)

Submission status: Time Limit Exceeded

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


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)

def filter_dp(dp):
    return {k:v for k,v in dp.items() if len(v) > 1}

def solve2(N: int, S: str):
    dp = collections.defaultdict(set)

    for i,s in enumerate(S[:-1]):
        dp[S[i:i+2]].add(i)

    dp = filter_dp(dp)

    if len(dp) > 0:
        for i in range(2, N):
            dp2 = collections.defaultdict(set)
            for k,v in dp.items():
                for a, b in itertools.combinations(v,2):
                    a, b = sorted([a,b])
                    if b+i < N and a+i < b and S[a+i] == S[b+i]:
                        dp2[S[a:a+i+1]].add(a)
                        dp2[S[a:a+i+1]].add(b)
            if len(dp2):
                dp = dp2
            else:
                print(i)
                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
    solve2(N, S)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)

def main():
    n=int(input())
    s=input()
    pre=[set() for _ in range(26)]
    nx=[set() for _ in range(n)]
    oa=ord("a")
    for i in range(n-1,-1,-1):
        ci=ord(s[i])-oa
        nx[i]|=pre[ci]
        pre[ci].add(i)
    #print(pre)
    #print(nx)
    ans=0
    for i in range(n):
        for ii in nx[i]:
            for di in range(1,n):
                if (not ii+di in nx[i+di]) or (i+di==ii):
                    L=di
                    break
            ans=max(ans,L)
    print(ans)
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())

n = ni()
s = ns()

dic = {}
strs = set()

for st in range(n):
    stri = s[st]
    if not stri in strs:
        dic[stri] = [st, -1]
        strs.add(stri)
    else:
        dic[stri][1] = st

    for ed in range(st+1, min(st+n//2+2, n)):
        stri += s[ed]
        if not stri in strs:
            dic[stri] = [st, -1]
            strs.add(stri)
        else:
            dic[stri][1] = st

ans = 0
for key, val in dic.items():
    if val[1] - val[0] >= len(key):
        ans = max(ans, len(key))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
def resolve():
    n=int(input())
    s=input()
    for w in range(1,n): # 幅数
        flag=False
        for i in range(n-w+1):
            if s.count(s[i:i+w])>=2:
                flag=True
        if flag is False:
            break
    print(w-1)
resolve()

Submission status: Time Limit Exceeded

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = 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 lrs(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 
  
n = int(input())
s = input()
print(len(lrs(s)))

Submission status: Time Limit Exceeded

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


def main():
    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 S2[:k] in S1:
                ok = k
                k = (k + ng) // 2
            else:
                ng = k
                k = (k + ok) // 2
        ans = max(ans, k)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def lcs(s1, s2):
    dp = []
    for s2_k in s2:
        bgn_idx = 0
        for i, cur_idx in enumerate(dp):
            chr_idx = s1.find(s2_k, bgn_idx) + 1
            if not chr_idx:
                break
            dp[i] = min(cur_idx, chr_idx)
            bgn_idx = cur_idx
        else:
            chr_idx = s1.find(s2_k, bgn_idx) + 1
            if chr_idx:
                dp.append(chr_idx)
    return len(dp)

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

Submission status: Time Limit Exceeded

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

for i in reversed(range(int(N//2))):
    j=0
    for j in range(0,N-i-i):
        buf=S[j:j+i+1]
        for k in range(i+j+1,N-i):
            if buf==S[k:k+i+1]:
                print(i + 1)
                break
        else:
            continue
        break
    else:
        continue
    break
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
t=input()
s=[]
for i in range(n):
    s.append(ord(t[i])-96)
now=0
now2=1
plus=0
answer=0
swit=0
save=0
while now<n:
    save=0
    while now2<n:
        if swit==0:
            if s[now]==s[now2]:
                swit=1
                plus=1
            else:
                now2+=1
        else:
            if now2+plus<n:
                if s[now2+plus]==s[now] and save==0:
                    save=now2+plus
                if s[now+plus]==s[now2+plus] and now+plus<now2:
                    plus+=1
                    if plus>=answer:
                        answer=plus
                else:
                    if save!=0:
                        now2=save
                        save=0
                    else:
                        now2+=1
                    plus=0
                    swit=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:
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()
ln = len(s)
flag = False
for l in range(ln//2)[::-1]:
    d = {}
    for i in range(ln - l):
        c = s[i:i+l+1]
        if c not in d.keys():
            d[c] = i
        else:
            ll = len(c)
            if i >= d[c] + ll:
                print(ll)
                flag = True
                break
    if flag:
        break
if flag is False:
    print(0)

Submission status: Time Limit Exceeded

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

ans_max = N//2 + 1

ans = [0] * N

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

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

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


print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
import bisect
n = int(input())
s_s = list(input())
pos = {}
for i, s in zip(range(n), s_s):
  if s not in pos:
    pos[s] = []
  pos[s].append(i)

ans = 0
for i in range(n):
  start_char = s_s[i]
  cand_pos = pos[start_char]
  valid_cand_pos_index = bisect.bisect_right(cand_pos, i)
  for idx in range(valid_cand_pos_index, len(cand_pos)):
    j = cand_pos[idx]
    k = 1
    while True:
      if j + k < len(s_s) and s_s[i + k] == s_s[j + k] and (i + k) < j:
        k += 1
      else:
        break
      if ans < k:
        ans = k

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    S = input()
    #N = 2000
    #S = "a"*N
    import time
    star = time.time()
    
    from collections import defaultdict
    D = {}
     
    for i in range(N):
        s = S[i]
        if not s in D:
            D[s] = [1, i, i]
        else:
            D[s][-1] = i
        for j in range(i+1,min(i+2+N//2, N, max(2*i+2,(N+i)//2+2))):
            s = "".join([s,S[j]])
            if not s in D:
                D[s] = [j-i+1, i, i]
            else:
                D[s][-1] = i
    totyuu = time.time()
    #print(totyuu-star)
        
    ans = 0
    for i in D:
        L = D[i][0]
        tmp = 0
        if len(D[i]) >= 3:
            if D[i][1] + L <= D[i][-1]:
                tmp = L
        if ans < tmp:
            ans = tmp
    g = time.time()
    #print(g-star)
    print(ans)
    
main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
s = input()
if n >= 666:
    ans = 2
elif n >= 27:
    ans = 1
else:
    ans = 0

for i in range(1,n//2+1)[::-1]:
    if i == ans:
        print(ans)
        quit()
    d = deque([])
    for j in range(i,n-i+1):
        d.append(s[j:j+i])
    for j in range(n-2*i+1):
        tmp = s[j:j+i]
        ll = len(d)
        for k in range(ll):
            ddd = d.popleft()
            if tmp == ddd:
                print(i)
                quit()
            d.append(ddd)
        d.popleft()
print(0)

Submission status: Time Limit Exceeded

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

maxs = 0
for i, s1 in enumerate(S):
    if i + maxs > len(S):
        break
    matchs = S[i:i+maxs+1]
    for j in range(i+maxs+1, len(S)-maxs):
        # 以下でmatchしてたらここに戻りたい
        for k in range(j,len(S)-maxs):
            if i + maxs >= j:
                break
            checks = S[j:j+maxs+1]
            if matchs == checks:
                maxs = len(matchs)
                matchs = S[i:i+maxs+1]
print(maxs)

Submission status: Time Limit Exceeded

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

        else:
            break
                

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
l = [[] for _ in range(n)] #iよりも左に含まれる部分文字列
r = [[] for _ in range(n)] #i含む右に含まれる部分文字列
for i in range(1,n):
    for j in range(i):
        l[i].append(s[j:i])
    l[i].extend(l[i-1])
r[n-1].append(s[-1])
for i in range(n-2, -1, -1):
    for j in range(i, n):
        r[i].append(s[i:j+1])
    r[i].extend(r[i+1])
ans = 0
#print(l,r)
for i in range(1,n):
    for s1 in r[i]:
        for s2 in l[i]:
            if s1 == s2:
                ans = max(ans, len(s1))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N=int(input())
    S=input()
    b = False
    for l in range(N//2, 1, -1):
        for i in range(N):
            a = S[i:i+l]
            for j in range(i+l, N-l+1):
                if S[j:j+l].find(a) >= 0:
                    b = True
                    print(l)
                    break
            if b:
                break
        if b:
            break
    else:
        print(0)

if __name__ == '__main__':
    main()