Problem:


Score : 500 points

Problem Statement

Given is a string S of length N.

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

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

l_1 + len \leq l_2

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

If there is no such integer len, print 0.

Constraints

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

|S| = N

S consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

N
S

Output

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

Sample Input 1

5
ababa

Sample Output 1

2

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

Sample Input 2

2
xy

Sample Output 2

0

No non-empty string satisfies the conditions.

Sample Input 3

13
strangeorange

Sample Output 3

5



Sample input:
5
ababa


Sample output:
2

Submission status: Time Limit Exceeded

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

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

print(res_length)

Submission status: Time Limit Exceeded

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


def solve_(N: int, S: str):
    max_con = 1
    tmp = 1
    for i in range(N - 1):
        if S[i] == S[i + 1]:
            tmp += 1
        else:
            max_con = max(max_con, tmp)
            tmp = 1
    max_con = max(max_con, tmp)


    sa = []
    for i in range(N):
        sa.append([S[i:], i])
    sa.sort()
    ret = 0
    for i in range(N - 1):
        s, si = sa[i]
        t, ti = sa[i + 1]
        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
        ret = max(ret, j)
    ret = max(ret, max_con // 2)
    print(ret)
    return


def solve(N: int, S: str):
    sa = []
    for i in range(N):
        sa.append([S[i:], i])
    sa.sort()
    #print(sa)
    ret = 0
    #cnt = 0
    for i in range(N - 1):
        s, si = sa[i]
        if len(s) < ret:
            continue
        tmp = 0
        for k in range(i + 1, N):
            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
            #print(j, tmp)
            if j <= tmp:
                break
            tmp = j
            #cnt += 1
        ret = max(ret, tmp)
    #print(cnt)
    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:
N = int(input())
S = input()

def lcs(a, b):
    L = []
    for bk in b:
        bgn_idx = 0
        for i, cur_idx in enumerate(L):
            chr_idx = a.find(bk, bgn_idx) + 1
            if not chr_idx:
                break
            L[i] = min(cur_idx, chr_idx)
            bgn_idx = cur_idx
        else:
            chr_idx = a.find(bk, bgn_idx) + 1
            if chr_idx:
                L.append(chr_idx)
    return len(L)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
_max = 0
for i in range(n):
    for j in range(i+1, n):
        part = s[i:j]
        if part in s[j:]:
            _max = max(_max, j-i)
        else:
            break
print(_max)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline


def solve(S, N):
    max_len = 0
    for i in range(N):
        for j in range(i + 1, N):
            if S[i] == S[j]:
                length = 1
                for k in range(1, min(N - j, j - i)):
                    if S[i + k] == S[j + k]:
                        length += 1
                max_len = max(max_len, length)
    return max_len


if __name__ == '__main__':
    N = int(input())
    S = input().strip()

    answer = solve(S, N)
    print(answer)

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 S[j+i:].count(left) >= 1:
        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):
    l = s[:i]
    r = s[i:]
    if i < n/2:
        for j in range(len(l)):
            for k in range(j, len(l)+1):
                if k - j <= ans:
                    pass
                elif l[j:k] in r:
                    ans = k - j
    else:
        for j in range(len(r)):
            for k in range(j, len(r)+1):
                if k - j <= ans:
                    pass
                elif r[j:k] in l:
                    ans = k - j
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    S = str(input().strip())

    ans = 0
    for i in range(N):
        for j in range(ans, N-i):
            if len(S[i:i+j]) > len(S[i+j:]):
                break

            if S[i:i+j] in S[i+j:]:
                ans = j

    return ans


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

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

    dp = [[[] for _ in range(N + 1)] for _ in range(N + 1)]  # dp[l1][length] = [l2, l2, ...]

    for l1 in range(N):
        for l2 in range(l1 + 1, N):
            if S[l1] == S[l2]:
                dp[0][l1].append(l2)

    for length in range(1, N):
        for l1 in range(N):
            for l2 in dp[length - 1][l1]:
                if l2 + length >= N:
                    continue
                if l1 + length >= l2:
                    continue
                if S[l1 + length] == S[l2 + length]:
                    dp[length][l1].append(l2)

    ans = 0
    for length in range(N + 1):
        for l1 in range(N + 1):
            if dp[length][l1]:
                ans = max(ans, length + 1)

    print(ans)

sol()

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(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:
from itertools import groupby

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

t = S[1:]
c = 0
for i in range(1, N):
    # print(S, t, i)
    for k, g in groupby([a == b for a, b in zip(S, t)]):
        if k == False:
            continue
        x = len(tuple(g))
        c = max(c, min(i, x))
    t = t[1:]
# print(S, t)
print(c)

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):
  for j in range(i+1,N):
    m = 0
    x = i + dp[i-1][j-1] if i>1 else i
    y = j + dp[i-1][j-1] if i>1 else j
    while x<j and y<N and S[x]==S[y]:
      x += 1
      y += 1
      m += 1
#    print(pm,i,j)
    if m>ans:
      ans = m
    dp[i][j] = m
print(ans)

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 = []
for t in T:
    if t not in U:
        U.append(t)
    else:
        tlen = len(t)
        u = t
        for i in range(tlen-1):
            u+=t[i+1]
        if u not in T:
            MAX = max(MAX,tlen)
        
#print(T)
print(MAX)

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]))
        best = 1
        for i,j in pair:
            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:
n = int(input())
s = input()

temp = int(n/2)
cnt = temp
check_list = []

for j in range(cnt):
    for i in range(n-(temp-1)):
        t = s[i:i+temp]
        if len(s[:i]) < len(t) and len(s[i+temp:]) < len(t):
            continue
        if t in check_list:
            continue
        else:
            check_list.append(t)
        arr = list(s)
        arr[i:i+temp] = "A"
        arr = "".join(arr)
        if t in arr:
            print(len(t))
            exit()
    temp -= 1
    if temp == 0:
        print(0)
        exit()

Submission status: Time Limit Exceeded

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


def f(x):
    for i in range(N):
        if i + x <= N:
            s = S[i:i + x]
            # print(s)
            for j in range(i + x, N):
                if j + x <= N:
                    t = S[j:j + x]
                    if s == t:
                        return True
    return False


ok = 0
ng = N
# print(f(5))
while (ng-ok) > 1:
    mid = (ok+ng) //2
    if f(mid):
        ok = mid

    else:
        ng = mid
    #print(ok, ng)
print(ok)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

ab = "abcdefghijklmnopqrstuvwxyz"
xx = [ab.index(s) for s in ss]

#print(xx)
cnt = 0
max_cnt = 0
i = 0
while i < n:
    j = i + 1
    while j < n:
        if xx[i] == xx[j]:
            while j + cnt < n and i + cnt < j:
                if xx[i + cnt] == xx[j + cnt]:
                    cnt += 1
                else:
                    break
            max_cnt = max(max_cnt, cnt)
            #print(xx[i:(i + cnt)], xx[j:(j + cnt)], i, j, cnt)
            cnt = 0
            j = j + cnt + 1

        else:
            j += 1
            if j >= n - 1:  
                break
    #print(i, j, cnt)
    i += 1
print(max_cnt)

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(10000000)


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 = {}


def addTree(tr, b, n, ma):
    if n == N:
        return ma
    if S[n] not in tr:
        tr[S[n]] = Node(n)
        return addTree(tr[S[n]].children, b, n + 1, ma)
    else:
        if tr[S[n]].num >= b:
            ma = 0
        return addTree(tr[S[n]].children, b, n + 1, ma + 1)


for i in range(0, N):
    ma_max = max(ma_max, addTree(Tr, i, i, 0))

print(ma_max)

Submission status: Time Limit Exceeded

Solution code:
from sys import exit, stderr, stdin
input = stdin.readline
# setrecursionlimit(10**7)
import heapq
def debug(var, name="hoge"):
    print(name +":" + str(type(var)) + " = " + repr(var), file=stderr)
    return


def main():
    N = int(input())
    S = str(input()).rstrip()
    LS = len(S)
    alp = ['a', 'b', 'c', 'd', 'e', 'f', 'g',
            'h', 'i', 'j', 'k', 'l', 'm', 'n',
             'o', 'p', 'q', 'r', 's', 't', 'u',
              'v', 'w', 'x', 'y', 'z']
    s = set()
    ans = 0
    p = dict()
    for i in range(LS):
        for j in range(i+1,LS+1):
            subs = S[i:j]
            if subs in s:
                if p[subs][1] < i:
                    ans = max(ans,len(subs))

            else:
                s.add(subs)
                p[subs] = (i,j-1)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
length=int(len(s)/2)
answer=0
while(length>0):
    for i in range(len(s)-length):
        part=s[i:i+length]
        if (s.count(part)) >= 2:
            answer=length
            break
    if answer > 0:
        break
    length-=1
print(answer)

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):
    ans = 0
    for i in range(N-1):
        for j in range(i+1, 1):
            if S[i] == S[j]:
                break
        else:
            ans = 1
            break
    for i in range(N-2):
        for j in range(i+1, 2):
            if S[i] == S[j]:
                break
        else:
            ans = 2
            break
    t = defaultdict(list)
    for i in range(N-2):
        t[S[i:i+2]].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 = 0
    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('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 e():
    for l in range(n//2, 0, -1):
        for i in range(n-l+1):
            if n-(l+i)<l:
                break
            s=S[i:i+l]
            if len(S.split(s))>=3:
                return l
    return 0


print(e())

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(n-1):
    for j in range(i+1,n):
        p = 0
        for k in range(min(j-i,n-1-j+1)):
            if s[i+k] == s[j+k]:
                p += 1
                
            else:
                break
        ans = max(ans,p)

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 check_s in S[start_s+length_s:]:
            print(length_s)
            exit()
print(0)

Submission status: Time Limit Exceeded

Solution code:
def solve():
  import sys
  import math

  sys.setrecursionlimit(10**7)
  readline=sys.stdin.readline

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

  for i in range(n):
    for j in range((n-i)//2,ans,-1):
      if s[i:i+j] in s[i+j:]:
        ans = j
        break

  print(ans)


if __name__ == '__main__':
  solve()

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 

n=int(input())
s=input()
print(len(longestRepeatedSubstring(s)))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
_S = ''
flag = 0
ans = 0
for i in range(1, N // 2 + 1):  # i文字数取り出す
    for j in range(N + 1 - i):  # j文字目から
        _S = S.replace(S[j:j + i], "")
        if len(_S) < N - i:
            ans = i
            break
print(str(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
debug = True

debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 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 II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()

INF = 10 ** 18
MOD = 10 ** 9 + 7

def main():
    N = II()
    S = SI()

    mark = [-1 for i in range(N)]

    from collections import defaultdict
    posd = defaultdict(list)

    for i, c in enumerate(S):
        posd[c].append(i)

    for i in range(N):
        si = S[i]

        # headの文字の位置のリスト
        pos_list = posd[si]

        for pos in pos_list:
            if pos >= i:
                # 自分より前のところだけを探す
                continue

            # どこまであうかをやっていく
            for j in range(N):
                # 自分のところまで来てたらやめる
                if pos+j == i:
                    break
                # 突き抜けたらやめる
                if i+j == N:
                    break

                you = pos + j
                me = i + j

                # 違ったらやめる
                if S[you] != S[me]:
                    break

                # 同じなら、マークする
                mark[you] = max(mark[you], j)

    print(max(mark)+1)



main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
ans=n//2
while ans>0:
  for i in range(n-2*ans+1):
    a=s[i:i+ans]
    if a in s[i+ans:]:
      print(ans)
      exit()
  ans-=1
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):
  for j in range(i+1,N):
    m = 0
    x = i + dp[i-1][j-1] if i>1 else i
    y = j + dp[i-1][j-1] if i>1 else j
    while x<j and y<N and S[x]==S[y]:
      x += 1
      y += 1
      m += 1
#    print(pm,i,j)
    if m>ans:
      ans = m
    dp[i][j] = m
print(ans)

Submission status: Time Limit Exceeded

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

def search(w):
    dic = {}
    for i in range(N+1-w):
        s = S[i:i+w]
        if s not in dic.keys():
            dic[s] = [i]
        else:
            if dic[s][0]+w<=i:
                return True
            dic[s].append(i)
    return False

def main():
    ans = 0
    max_w = N//2
    for i in range(1, max_w+1):
        if search(i):
            ans = i
        else:
            break
    print(ans)

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][0] ==  x:
        return True
    else:
        return False

def search(a,n):
    se = dict()
    for i in range(0,len(a)-n+1):
        kkk = a[i:i+n]
        kkk = "".join(kkk)
        if kkk in se:
            for j in range(len(se[kkk])):
                if se[kkk][j] <= i-n:
                    return True
            else:
                se[kkk].append(i)
        else:
            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:
from collections import defaultdict
N = int(input())
S = input()
half_N = N//2
cand = [[] for _ in range(N-1)]
flag = True
for i in range(N):
    for j in range(1, N-i-1):
        if S[i] == S[i+j]:
            flag = False
            cand[i].append(i+j)
if flag:
    print(0)
    exit()

for length in range(1, N//2+1):
    flag = True
    new_cand = [[] for _ in range(N-1)]
    for i in range(N-length):
        tmp = []
        now_check = S[i+length]
        for c in cand[i]:
            if i + length >= c or c + length >= N:
                continue
            if S[c+length] == now_check:
                flag = False
                tmp.append(c)
        new_cand[i] = tmp
    cand = new_cand
    if flag:
        print(length)
        exit()
print(length+1)

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:
    x=S[a]
    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)
    a+=1
print(ans)

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
    after = S[0]
    for i in range(1,N):
        after += S[i]
        for j in range(ceil(len(after)/2),len(after)):
            if after.find(after[j:]) != j:
                ans = max(ans,len(after[j:]))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
ans = 0
p = 0
for i in range(1,n):
    word = s[p:i]
    w_l = len(word)
    for j in range(i,n-w_l+1):
        if word == s[j:j+w_l]:
            ans = w_l
            break
    else:
        p += 1
print(ans)

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]:
                temp = 0
                betw = k-i-1
                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 l in range(1, N//2+2):
    s, t = S[:l], S[l:]
    dp = [[0 for _ in range(N-l+1)] for _ in range(l+1)]
    for i in range(l):
        for j in range(N-l):
            if (s[i] == t[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])
    if (dp[l][N-l] > ans):
        ans = dp[l][N-l]
print(ans)

Submission status: Time Limit Exceeded

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

max_len = 0

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

print(max_len)

Submission status: Time Limit Exceeded

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
ts=time.time()
sys.setrecursionlimit(10**6)
#input=sys.stdin.readline
show_flg=False
#show_flg=True

ans=0
an=[]
n=I()
st=-1
s=list(input())
can=[]
for d in range(1,n):
    cnt=0
    for i in range(n-d):
        if s[i]==s[i+d] and st+cnt+1<=st+d:
            if st==-1:
                st=i
            #show('d,i,s[i],st,cnt,an',d,i,s[i],st,cnt,an)
            cnt+=1
            an+=s[i]
            ans=max(ans,cnt)
        else:
            #show('d,i,s[i],st,cnt,an',d,i,s[i],st,cnt,an,'els')
            cnt=0
            can+=[an]
            an=[]
            st=-1
    cnt=0
print(ans)
show(can)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
 
max_count = 0
for i in range(n):
    for j in range(i+1, n):
        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()
l = 0
r = 1
ans = 0
for l in range(-(-N//2)):
    for r in range(l+1, -(-N//2)+1):
        s = S[l:r]
        if S[r:].count(s) < 1:
            continue
        if len(s) > ans:
            ans = len(s)
print(ans)

Submission status: Time Limit Exceeded

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

result = 0

for a in range(1, N//2+1):
    for b in range(N-a):
        s1 = S[b:b+a]
        for c in range(b+1, N-a+1):
            s2 = S[c:c+a]
            if s1 == s2:
                result = a

print(result)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())
s = '^' + input().strip() + '$'

dp = (np.zeros((n + 2, n + 2)) - np.identity(n + 2) * 9999999).astype(int)
longest = 0
for i in range(1, n + 2):
    for j in range(i + 1, n + 2):
        if s[i] == s[j]:
            dp[i, j] = dp[i - 1, j - 1] + 1
        else:
            val = dp[i - 1, j - 1]
            if j - i < val:
                val = j - i
            if val > longest:
                longest = val

print(longest)

Submission status: Time Limit Exceeded

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

def longestRepeatedSubstring(str): 
    n = len(str) 
    LCSRe = [[0 for x in range(n + 1)] 
                            for y in range(n + 1)] 

    res = "" # To store result 
    res_length = 0 # To store length of result 

    # building table in bottom-up manner 
    index = 0
    for i in range(1, n + 1): 
            for j in range(i + 1, n + 1): 
                    
                    # (j-i) > LCSRe[i-1][j-1] to remove 
                    # overlapping 
                    if (str[i - 1] == str[j - 1] and
                            LCSRe[i - 1][j - 1] < (j - i)): 
                            LCSRe[i][j] = LCSRe[i - 1][j - 1] + 1

                            # updating maximum length of the 
                            # substring and updating the finishing 
                            # index of the suffix 
                            if (LCSRe[i][j] > res_length): 
                                    res_length = LCSRe[i][j] 
                                    index = max(i, index) 
                            
                    else: 
                            LCSRe[i][j] = 0

    # If we have non-empty result, then insert 
    # all characters from first character to 
    # last character of string 
    if (res_length > 0): 
            for i in range(index - res_length + 1, 
                                                                    index + 1): 
                    res = res + str[i - 1] 

    return res


print(len(longestRepeatedSubstring(s)))