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:
from collections import defaultdict, Counter
from itertools import combinations

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

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

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

if m == 0:
  m = 1 if max(Counter(S).values()) > 1 else 0

print(m)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
S = input()
k = n//2

for l in range(k, 0, -1):
    word = S[0:l]

    for i in range(n):
        if S[l+i:].find(word) >= 0:
            print(l)
            exit()

        if i + 2*l > n:
            break
        word = word[1:] + S[l+i]

print(0)

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    N = int(input())
    S = input().rstrip()
    ans = 0
    pool = S[0]
    for i in range(1,N):
        pool += S[i]
        len_after = i+1
        first = pool[:ceil((i+1)/2)]
        second = pool[ceil((i+1)/2):]
        for n in range(len_after//2):
            if first.find(second[n:]) != -1:
                ans = max(ans,len(second[n:]))

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
S = input()
m = n//2
l,r = 0,n-1
ans = 0
while l<=r:
    m = (l + r) // 2
#    print("m = ", m)
    for i in range(n-m) :
        # 切り取る
        sub = S[i :i + m]
#        print("sub=", sub)
#        print("i=", i)
        fl = False
        for j in range(i + m, n - m + 1) :
#            print("j=", j)
            sub2 = S[j :j + m]
            if sub == sub2 : #sub==sub2となり共通する部分がある場合
                fl = True
                break
        if fl:
            l = m+1
            ans = l-1
#            print(l-1,"にて共通部分有")
            break
    else:
        r = m-1
#        print(r+1,"にて共通部分無")
print(ans)

Submission status: Time Limit Exceeded

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

a = []
b = set()
b.add("")
c=[b.copy()]
for i in range(n - 1, -1, -1):
    for j, k in enumerate(a):
        a[j] = s[i] + k
    a.append(s[i])
    b |= set(a)
    c.append(b.copy())
c.reverse()

a = []
b = set()
b.add("")
d = [b.copy()]
for i in range(n):
    for j, k in enumerate(a):
        a[j] = k+s[i]
    a.append(s[i])
    b |= set(a)
    d.append(b.copy())
ans = 0

for i, j in zip(c, d):
    e = len(max(i & j, key=len))
    ans = max(e, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from bisect import bisect_right
    import sys
    input = sys.stdin.readline
    N = int(input())
    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):
        c = S[l]
        d = D[c]
        j = bisect_right(d, l+m)
        if j == N:
            continue
        for r in d[j:]:
            k = 1
            while S[l+k] == S[r+k] and l+k < r:
                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**2
    print(N)
    a = ord('a')
    print("".join(chr(a + random.randint(0, 25)) for i in range(N)))
#gen()
main()

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs , heapq as hq
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def search(a,n):
    se = dict()
    data = []
    for i in range(0,len(a)-n+1):
        kkk = a[i:i+n]
        kkk = "".join(kkk)
        if In(kkk,data):
            for j in range(len(se[kkk])):
                if se[kkk][j] <= i-n:
                    return True
            else:
                se[kkk].append(i)
        else:
            bs.insort(data,kkk)
            se[kkk] = [i]
    return False








n = onem()

s = list(input())
l = 0
r = n//2
for i in range(n):
    mid = -(-(l+r)//2)
    ans = search(s,mid)
    if l == mid:
        break
    if ans:
        l = mid
    else:
        r = mid-1
print(l)

Submission status: Time Limit Exceeded

Solution code:
#E問題


N = int(input())
S = list(str(input()))

T = []

for i in range(N):
    s = S[i]
    T.append(s)
    for j in range(N-i-1):
        t = S[i+j+1]
        s+=t
        T.append(s)

MAX = 0
U = []
T.sort(reverse=True)
for t in T:
    if t not in U:
        U.append(t)
    else:
        tlen = len(t)
        t1 = t[0]
        s = t.lstrip(t1)
        u = t+s
        if u not in U:
            MAX = max(tlen,MAX)
        else:
            U.append(t)
        
        
        
#print(T)
print(MAX)

Submission status: Time Limit Exceeded

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


class Node:
    def __init__(self, num_):
        self.num = num_
        self.children = {}  # dict

    def addChild(self, ch_, num_):
        self.children[ch_] = Node(num_)


ma_max = 0
Tr = {}
for i in range(0, N):
    tr = Tr
    ma = 0
    for j in range(i, N):
        if S[j] not in tr:
            tr[S[j]] = Node(j)
            tr = tr[S[j]].children
        else:
            if tr[S[j]].num >= i:
                ma = -1
            else:
                ma += 1
            tr = tr[S[j]].children
    ma_max = max(ma_max, ma)
    if N - i < ma_max:
        break

print(ma_max)

Submission status: Time Limit Exceeded

Solution code:
from string import ascii_lowercase
from collections import deque
N=int(input());S=input();q=deque([""]);m=0
while q:
    s=q.popleft()
    for c in ascii_lowercase:
        t=s+c
        if S.count(t)>1:q.append(t);m=max(m,len(t))
print(m)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    s = input()
    slist = list(s)
    sset = set(slist)
    l = []
    lap = l.append
    if len(sset) == n:
        print(0)
    else:
        for i in list(sset):
            lap([j for j,k in enumerate(slist) if k == i])
        pair = []
        pap = pair.append
        for i in l:
            for j in range(len(i)):
                for k in range(j+1,len(i)):
                    pap((i[j],i[k]))
        cpair = []
        cpap = cpair.append
        for i in range(len(pair)):
            for j in range(i,len(pair)):
                if pair[i][0]-pair[j][0] == pair[i][1]-pair[j][1]:
                    cpap(pair[i])
        cpair = list(set(cpair))
        best = 1
        for i,j in cpair:
            x = i
            y = j
            c = 0
            while True:
                if x >= n or y >= n or x >= j or not s[x] == s[y]:
                    break
                c += 1
                x += 1
                y += 1
            best = max([c,best])
        print(best)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
    _,S = open(0).read().split()
    s1 = S[:int(len(S)*3/4)+1]

    maxLen = 0
    lenS1 = len(s1)
    for i in range(lenS1):
        for j in range(i+1+maxLen,lenS1):
            # print(s1[i:j], S[j:], j,i)
            if s1[i:j] in S[j:] and j-i+1 > maxLen:
                maxLen = j-i

    print(maxLen)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline


def main():
    n=int(input())
    s=input()
    a=[]
    max=0
    for i in range(n//2,-1,-1):
        for l in range(n-i):
            t=str(s[l:l+i+1])
            a.append([t,l])
        if len(a)>=2:
            for k in range(len(a)-1):
                for kk in range(k+1,len(a)):
                    if a[k][0]==a[kk][0] and a[k][1] + i < a[kk][1]:
                        max=i+1
                        break
        a=[]
        if max>0:
            break

    print(max)



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

    for i in range(N//2, 0, -1):
        if N-i*2 == 0:
            tmp = '0'*i + S[i:]
            if tmp.find(S[:i]) != -1:
                print(i)
                exit()
        else:
            for index in range(N-i*2):
                # 仮の文字列の生成
                tmp = S[:index] + '0'*i + S[index+i:]
                if tmp.find(S[index:index+i]) != -1:
                    print(i)
                    exit()

    print('0')

Submission status: Time Limit Exceeded

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

ans = 0
for j in range(n):
    for i in range(j):
        temp = 0
        mar = 0
        while (j + mar < n) & (i + mar < j):
            if (s[j+mar] == s[i+mar]):
                mar += 1
                temp += 1
            else:
                break
        ans = max(ans, temp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

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

max_len = math.floor(n/2)
for s_len in range(max_len):
    s_len = max_len - s_len
    for s_idx in range(len(s)):
        target = s[s_idx:s_idx+s_len]
        if len(target) != s_len:
            continue
        if target in s[0:s_idx] or target in s[s_idx+s_len:]:
            print(s_len)
            exit(0)

print(0)

Submission status: Time Limit Exceeded

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

ans = 1
for i in range(n):
    for j in range(i+1,n+1):
        a = s[i:j]
        b = s[j:]
        if len(a) > len(b) or len(a) == 1 or len(a) <= ans:
            continue
        if b.count(a) > 0:
            ans = max(ans,len(a))
        # print(a,b,b.count(a))

if ans == 1:
    print(0)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:

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

ans = 0
for i in range(1, n):
    l = s[:i]
    r = s[i:]
    if i < n/2:
        for j in range(len(l)):
            for k in range(j+ans, len(l)+1):
                if l[j:k] in r:
                    ans = k - j
    else:
        for j in range(len(r)):
            for k in range(j+ans, len(r)+1):
                if r[j:k] in l:
                    ans = k - j
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
ans = 0
p = 0
q = 1
flag = True
while q < n:
    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
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N = int(input())
S = input()
ds = defaultdict(list)
for i in range(N):
    ds[S[i]].append(i)

ans = 0
for s in ds:
    d = defaultdict(lambda:[0,-1])
    if len(ds[s])==1:
        continue
    ans = max(ans,1)
    for i in ds[s]:
        t = s
        j = i+1
        while j-i<=N-j-1:
            t = t+S[j]
            if d[t][1] < i:
                d[t][0] += 1
                d[t][1] = j
                ans = max(ans,j-i)
            j += 1
print(ans)

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]
    if left in S[j+i:]:
        print(len(left))
        exit()
        
print(0)

Submission status: Time Limit Exceeded

Solution code:
# Python program for KMP Algorithm 
def KMPSearch(pat, txt): 
    M = len(pat) 
    N = len(txt) 

    # create lps[] that will hold the longest prefix suffix 
    # values for pattern 
    lps = [0]*M 
    j = 0 # index for pat[] 

    # Preprocess the pattern (calculate lps[] array) 
    computeLPSArray(pat, M, lps) 

    i = 0 # index for txt[] 
    while i < N: 
        if pat[j] == txt[i]: 
            i += 1
            j += 1

        if j == M: 
            return True
            j = lps[j-1] 

        # mismatch after j matches 
        elif i < N and pat[j] != txt[i]: 
            # Do not match lps[0..lps[j-1]] characters, 
            # they will match anyway 
            if j != 0: 
                j = lps[j-1] 
            else: 
                i += 1
    return False

def computeLPSArray(pat, M, lps): 
    len = 0 # length of the previous longest prefix suffix 

    lps[0] # lps[0] is always 0 
    i = 1

    # the loop calculates lps[i] for i = 1 to M-1 
    while i < M: 
        if pat[i]== pat[len]: 
            len += 1
            lps[i] = len
            i += 1
        else: 
            # This is tricky. Consider the example. 
            # AAACAAAA and i = 7. The idea is similar 
            # to search step. 
            if len != 0: 
                len = lps[len-1] 

                # Also, note that we do not increment i here 
            else: 
                lps[i] = 0
                i += 1
                
n = int(input())
s = input()

max_window_sz = n//2
ans = 0
prev_ans = ans
for i in range(1,max_window_sz+1):
    prev_ans = ans
    for start in range(n-i):
        s1 = s[start+i:]
        s2 = s[start:start+i]
#         print(s1,s2)
        if(KMPSearch(s2,s1)):
            ans = max(i,ans)
            break
    if ans == prev_ans:
        break
print(ans)

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

for i in range(1,n//2+1)[::-1]:
    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:
def do():
    N = int(input())
    S = str(input())
    answer = 0
    for i in range(len(S)-1):
        for k in range(i+1,len(S)):
            if S[i] == S[k] and k+answer <= len(S):
                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)
    print(answer)
    
if __name__ == '__main__':
    do()

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(1, N):
    tmp = 0
    for j in range(N - i):
        if S[j] == S[i + j]:
            if tmp < i:
                tmp += 1
            else:
                continue
            if tmp > ans:
                ans = tmp
        else:
            tmp = 0

print(ans)

Submission status: Time Limit Exceeded

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

n = len(s) 
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 (s[i - 1] == s[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

print(res_length)

Submission status: Time Limit Exceeded

Solution code:
#import sys
#input = sys.stdin.readline
def main():
    N = int( input())
    S = input()
    dp = [[0]*(N+1) for _ in range(N+1)]
    for i in range(N-1):

        for j in range(i+1, N):
            if S[i] == S[j]:
                dp[i+1][j+1] = min(dp[i][j] + 1, j-i)
    print( max( [ max(dp[i]) for i in range(N+1)]))
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def n_gram(target, n):
  return [ target[idx:idx + n] for idx in range(len(target) - n + 1)]

n=int(input())
str=input()
ans=0

for i in range(1,(n//2)+1):
    gramfied=n_gram(str,i)
    sets=[]
    sets_count=1
    for j in gramfied:
        if j in sets:
            if sets_count>=sets.index(j)+i:
                ans=i
                break
        sets.append(j)
        sets_count+=1
print(ans)

Submission status: Time Limit Exceeded

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

for length_s in range(N//2, 0, -1):
    for start_s in range(0, N-length_s):
        check_s = S[start_s:start_s+length_s]
        if length_s > N - start_s - length_s:
            break
        if check_s in S[start_s+length_s:]:
            print(length_s)
            exit()
print(0)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
    def input():
        return sys.stdin.readline()[:-1]
    N = int(input())
    S = input() + "_"
    #shakutori * 2
    ans = 0
    for s in range(N-1):
        for e in range(s+1,N):
            if S[s] == S[e]:
                k = 0
                while s+k < e and e+k < N and S[s+k] == S[e+k]:
                    k += 1
                    if e+k == N:
                        break
                ans = max(ans,k)
    print(ans)
if __name__ == '__main__':
    main()

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 + max_length, i + 1 + (N - i) // 2):
        if S[j + 1:].find(S[i:j + 1]) != -1:
            max_length = j - i + 1

print(max_length)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
f = False
if len(set(S)) == N:
    print(0)
else:
    for i in range(N//2, 1, -1):
        for j in range(N - i):
            if S[j:j+i] in S[j+i:]:
                f = True
                break
        if f:
            print(i)
            break

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

dic = {}
strs = set()

slice = [[""]*n for _ in range(n)]
for st in range(n):
    curstr = s[st]
    for ed in range(st+1, min(st+n//2+2, n)):
        curstr += s[ed]
        slice[st][ed] = curstr

for st in range(n):
    for ed in range(st+1, min(st+n//2+2, n)):
        stri = slice[st][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,collections as cl,bisect as bs , heapq as hq
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def search(a,n):
    se = dict()
    data = []
    for i in range(0,len(a)-n+1):
        kkk = a[i:i+n]
        kkk = "".join(kkk)
        if In(kkk,data):
            for j in range(len(se[kkk])):
                if se[kkk][j] <= i-n:
                    return True
            else:
                se[kkk].append(i)
        else:
            bs.insort(data,kkk)
            se[kkk] = [i]
    return False








n = onem()

s = list(input())
l = 0
r = n//2
while True:
    mid = -(-(l+r)//2)
    ans = search(s,mid)
    if l == mid:
        break
    if ans:
        l = mid
    else:
        r = mid-1
print(l)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
ans = []
count = 0
for i in range(n):
	for j in range(i+1,n):
		if s[i] == s[j]:
			i_dash = i
			j_dash = j
			while True:
				if i_dash == j or j_dash == n:
					break
				elif s[i_dash] == s[j_dash]:
					count+=1
				else:
					break
				i_dash += 1
				j_dash += 1
			ans.append(count)
			count = 0

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
dp = [False for _ in range(len(s))]
if n%2 == 0:
    x = n//2
else:
    x = (n-1)//2
ans = 0
for i in range(n-1):
    for j in range(i+1,n):
        if s[i] == s[j]:
            dp[i] = True
            ans = 1

for i in range(2,x+1):
    flag = False
    for j in range(n-i+1-i):
        if not dp[j]:
            continue
        for k in range(j+i-1,n-i+1):
            if s[j:j+i] == s[k:k+i]:
                ans = i
                flag = True
                break
        if flag:
            break
print(ans)

Submission status: Time Limit Exceeded

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


def LCSubStr(X, Y, m, n):

    # Create a table to store lengths of
    # longest common suffixes of substrings.
    # Note that LCSuff[i][j] contains the
    # length of longest common suffix of
    # X[0...i-1] and Y[0...j-1]. The first
    # row and first column entries have no
    # logical meaning, they are used only
    # for simplicity of the program.

    # LCSuff is the table with zero
    # value initially in each cell
    LCSuff = [[0 for k in range(n+1)] for l in range(m+1)]

    # To store the length of
    # longest common substring
    result = 0

    # Following steps to build
    # LCSuff[m+1][n+1] in bottom up fashion
    for i in range(m + 1):
        for j in range(n + 1):
            if (i == 0 or j == 0):
                LCSuff[i][j] = 0
            elif (X[i-1] == Y[j-1]):
                LCSuff[i][j] = LCSuff[i-1][j-1] + 1
                result = max(result, LCSuff[i][j])
            else:
                LCSuff[i][j] = 0
    return result


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


print(ans)

Submission status: Time Limit Exceeded

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

sa = [i for i in range(N+1)]
rank = [ord(c) for c in S] + [-1]

k = -1
key = lambda i: (rank[i], rank[i+k] if i+k <= N else -1)

def construct_sa():
    global k,rank
    k = 1
    tmp = [0] * (N+1)
    while k <= N:
        sa.sort(key=key)
        tmp[sa[0]] = 0
        for i in range(1,N+1):
            tmp[sa[i]] = tmp[sa[i-1]] + (key(sa[i-1]) < key(sa[i]))
        rank = [r for r in tmp]
        k *= 2

construct_sa()


def exist_twice(s):
    n = len(s)
    l,r = 0,N
    while r-l > 1:
        m = (l+r)//2
        if S[sa[m]:sa[m]+n] < s:
            l = m
        else:
            r = m
    if S[sa[r]:sa[r]+n] != s:
        return False
    minsa = maxsa = sa[r]
    while r <= N and S[sa[r]:sa[r]+n] == s:
        minsa = min(minsa, sa[r])
        maxsa = max(maxsa, sa[r])
        if maxsa - minsa >= n:
            return True
        r += 1
    return False

def is_ok(l):
    if l<=0: return True
    for i in range(N-l+1):
        if exist_twice(S[i:i+l]):
            return True
    return False

ok = 0
ng = N//2+1
while ng-ok > 1:
    m = (ng+ok)//2
    if is_ok(m):
        ok = m
    else:
        ng = m
print(ok)

Submission status: Time Limit Exceeded

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

ans = 0

while ans <= len(s)//2:
    for i in range(1, len(s)//2+1):
        if s[:i] in s[i:]:
            if s[:i+1] in s[i+1:]:
                continue
            else:
                ans = max(ans, len(s[:i]))
    s = s[1:]
    if len(s) == 1:
        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
OB = [-1]*N
for i in range(N):
    if D[S[i]]<=1:
        pass
    else:
        OB[i] = dic[S[i]]

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


print(ans)

Submission status: Time Limit Exceeded

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

S_dict = {}
for i, s in enumerate(list(S)):
    if s in S_dict:
        S_dict[s].append(i)
    else:
        S_dict[s] = [i]
#print(S_dict)

S_set = set()
for nums in S_dict.values():
    for i, a in enumerate(nums):
        for b in nums[i+1:]:
            S_set.add((a, b))
#print(S_set)
#print("---")

ans = 0
for a, b in sorted(S_set):
    i = 0
    if not (a, b) in S_set:
        continue
    while 1:
        #print(i, a+i, b+i)
        if (a+i, b+i) in S_set and a+i < b:
            S_set.remove((a+i, b+i))
            i += 1
        else:
            break
    ans = max(ans, i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from bisect import bisect_right
    import sys
    input = sys.stdin.readline
    N = int(input())
    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):
        c = S[l]
        d = D[c]
        j = bisect_right(d, l)
        if j == N:
            continue
        for r in d[j:]:
            k = 1
            while S[l+k] == S[r+k] and l+k < r:
                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**2
    print(N)
    a = ord('a')
    print("".join(chr(a + random.randint(0, 25)) for i in range(N)))
#gen()
main()

Submission status: Time Limit Exceeded

Solution code:
def lcsubstr(x, y):
    m = len(x)
    n = len(y)
    dp = [[0 for k in range(n+1)] for l in range(m+1)] 
      
    result = 0 

    for i in range(m + 1): 
        for j in range(n + 1): 
            if (i == 0 or j == 0): 
                dp[i][j] = 0
            elif (x[i-1] == y[j-1]): 
                dp[i][j] = dp[i-1][j-1] + 1
                result = max(result, dp[i][j]) 
            else: 
                dp[i][j] = 0
    return result 

n = int(input())
s = input()
l = 0
for i in range(1, n):
    s1, s2 = s[:i], s[i:]
    l = max(lcsubstr(s1, s2), l)
print(l)

Submission status: Time Limit Exceeded

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

for l in range(N//2, 0, -1):
    for i in range(N):
        if 2*l+i > N:
            break
        part = S[i:l+i]
        for j in range(l+i, N-l+1):
            cmp = S[j:j+l]
            if cmp == part:
                print(l)
                import sys
                sys.exit()
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
def f_e():
    n = int(input())
    s = input()
    a = 0
    for si in range(n):
        s1, s2 = s[:si], s[si:]
        dp = [[0]*(len(s2)+1) for _ in range(len(s1)+1)]
        for i in range(len(s1)):
            for j in range(len(s2)):
                if s1[i]==s2[j]:
                    dp[i+1][j+1] = dp[i][j]+1
                else:
                    dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
        a = dp[-1][-1] if dp[-1][-1]>a else a
    print(a)

if __name__ == "__main__":
    f_e()

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
S=input()
a=0
ans=0
while a<=n-2-ans:
    for j in range(a+1+ans,n-ans):
        if S[j]==S[a]:
            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)
    a+=1
print(ans)

Submission status: Time Limit Exceeded

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

def check(L):
  for i in range(N - (L * 2) + 1):
    if S.rindex(S[i:i+L]) >= i+L:
      return True
  return False

left = 0
right = N // 2 + 1
while right - left > 1:
  mid = left + (right - left) // 2
  if check(mid):
    left = mid
  else:
    right = mid
print(left)