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

maxL = 0

for i in range(1, N-1):
    cnt = 0
    left = 0
    for j in range(0, N-i):
        if S[j]==S[j+i]:
            cnt+=1
            if maxL < cnt:
                maxL = cnt
            if cnt == i:
                break
        else:
            cnt = 0
            left = j + 1

print(maxL)

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 zalgo(S):
    N = len(S)
    prefix = [0]*N
    prefix[0] = N
    i=1;j=0
    while i < N:
        while i+j < N and S[j] == S[i+j]: j += 1
        prefix[i] = j
        if j==0:
            i += 1
            continue
        k=1
        while i+k < N and k+prefix[k] < j:
            prefix[i+k] = prefix[k]
            k += 1
        i += k
        j -= k
    return prefix

def main():
    """ main """
    N = int(input())
    S = input().rstrip()
    ans = 0
    for i in range(N):
        arr = zalgo(S[i:])
        for j in range(len(arr)):
            ans = max(ans, min(arr[j],j))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

dp = np.zeros((n+1, n+1), dtype=np.int64)
ans = 0

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

Submission status: Time Limit Exceeded

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

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

for i in range(n-1, -1, -1):
    for j in range(i, -1, -1):
        if s[i] == s[j]:
            a = dp[i+1][j+1]
            dp[i][j] = a + 1
        ans = max(ans, min(i-j, dp[i][j]))
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N=int(input())
S=input()
dic=defaultdict(lambda: [N,-1])
for i in range(N-1):
    for j in range(i, N):
        w = S[i:j+1]
        min_,max_ = dic[w]
        if j<min_:
            dic[w][0]=j
        elif j>max_:
            dic[w][1]=j
ans=0
for w,(min_,max_) in dic.items():
    if min_ <= max_-len(w):
        ans=max(ans,len(w))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

N = int(sys.stdin.readline())
S = sys.stdin.readline().strip()

ans = 0
for L in range(1, N):
	dp = [0]*N 
	for x in range(N - L):
		if S[x] == S[x+L]:
			if x==0: dp[x] += 1
			else: dp[x] = min(dp[x-1]+1, L)
			ans = max(ans, dp[x])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
m = 0
for i in range(N//2):
        for r in range(i+1,N-i):
                if S[i:r] in (S[r:N]):
                        m = max(m,len(S[i:r]))
                if len(S[i:r]) > len(S[r:N]):
                        break
print(m)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
m = 0
for i in range(N//2):
        for r in range(i+1,N):
                if S[i:r] in (S[r:N]):
                        m = max(m,len(S[i:r]))               
print(m)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
m = 0
for i in range(N-1):
    for r in range(i+1,N):
        if S[i:r] in (S[r:N]):
            m = max(m,len(S[i:r]))               
print(m)

Submission status: Time Limit Exceeded

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

def search(n):
    if n == 0:
        return False
    for i in range(N):
        for j in range(i+n, N):
            if j+n <= N:
                if S[i:i+n] == S[j:j+n]:
                    return True
    return False

l = 1
r = N//2+1

while l<r:
    mid = (l+r)//2
    if search(mid):
        l = mid+1
    else:
        r = mid

print(l-1)

Submission status: Time Limit Exceeded

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

max_cnt = 0
for i in range(1, n):
    cnt = 0
    for j in range(n - i):
        if ss[j] == ss[j + i]:
            cnt += 1
            max_cnt = max(cnt, max_cnt)
            if cnt == i:
                break
        else:
            cnt = 0

print(max_cnt)

Submission status: Time Limit Exceeded

Solution code:

N = int(input())
S = input()
ans = 0

for L in range(1,N): #比較する文字列同士の距離
    dp = [0] * (N+5)
    for x in range(N-L): #文字列の始点を全探索
        if S[x] == S[x+L]:
            if x == 0:
                dp[x] += 1
            else:
                dp[x] = min(dp[x-1]+1,L)
            ans = max(ans,dp[x])
        else:
            dp[x] = 0
            
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import cmp_to_key
import math
import bisect

n = int(input())
s = input()
k = 1
rank = [0] * (n+1)
tmp = [0] * (n+1)
sa = [''] * (n+1)
"""
def compare_sa(i,j):
	if rank[i] != rank[j]:
		return -1 if rank[i] < rank[j] else 1
	else:
		if i + k <= n:
			ri = rank[i+k]
		else:
			ri = -1
		if j + k <= n:
			rj = rank[j+k]
		else:
			rj = -1
		return -1 if ri < rj else 1


for i in range(n+1):
	sa[i] = i
	if i < n:
		rank[i] = ord(s[i])
	else:
		rank[i] = -1

while k <= n:

	sa = sorted(sa,key=cmp_to_key(compare_sa))

	tmp[sa[0]] = 0

	for i in range(1,n+1):
		if compare_sa(sa[i-1],sa[i]) == -1:
			tmp[sa[i]] = tmp[sa[i-1]] + 1
		else:
			tmp[sa[i]] = tmp[sa[i-1]]

	for i in range(n+1):
		rank[i] = tmp[i]

	k *= 2

#saはインデックス、sorted_listは実際の文字列
sorted_list = []
for i in range(n+1):
	sorted_list.append(s[sa[i]:])
print(sa)
print(sorted_list)

#文字列検索
T = ['ab','abra','abc','abracadabra','abracadabraaa','brabra','bra']
for t in T:
	start = bisect.bisect_left(sorted_list,t)
	end = bisect.bisect_left(sorted_list,t[:-1]+chr(ord(t[-1])+1))
	if start == end:
		print(t+'は存在しません')
	else:
		print(t+'は存在します')
"""

#lcp配列の作成
def getLCP(i,j):
	h = 0
	while i+h < n and j+h < n:
		if s[j+h] != s[i+h]:
			break
		h+=1
	return h

#lcp配列の最大値=最長の共通部分文字列のインデックス
#ans = sorted_list[ lcp.index(max(lcp)) ]
#ans = ans[:max(lcp)]
#print(ans)

ans = 0
for i in range(0,n):
	for j in range(i+1,n):
		lcp = min(getLCP(i,j),j-i)
		ans = max(ans,lcp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import cmp_to_key
import math
import bisect

n = int(input())
s = input()
k = 1
rank = [0] * (n+1)
tmp = [0] * (n+1)
sa = [''] * (n+1)

def compare_sa(i,j):
	if rank[i] != rank[j]:
		return -1 if rank[i] < rank[j] else 1
	else:
		if i + k <= n:
			ri = rank[i+k]
		else:
			ri = -1
		if j + k <= n:
			rj = rank[j+k]
		else:
			rj = -1
		return -1 if ri < rj else 1


for i in range(n+1):
	sa[i] = i
	if i < n:
		rank[i] = ord(s[i])
	else:
		rank[i] = -1

while k <= n:

	sa = sorted(sa,key=cmp_to_key(compare_sa))

	tmp[sa[0]] = 0

	for i in range(1,n+1):
		if compare_sa(sa[i-1],sa[i]) == -1:
			tmp[sa[i]] = tmp[sa[i-1]] + 1
		else:
			tmp[sa[i]] = tmp[sa[i-1]]

	for i in range(n+1):
		rank[i] = tmp[i]

	k *= 2
"""
#saはインデックス、sorted_listは実際の文字列
sorted_list = []
for i in range(n+1):
	sorted_list.append(s[sa[i]:])
print(sa)
print(sorted_list)

#文字列検索
T = ['ab','abra','abc','abracadabra','abracadabraaa','brabra','bra']
for t in T:
	start = bisect.bisect_left(sorted_list,t)
	end = bisect.bisect_left(sorted_list,t[:-1]+chr(ord(t[-1])+1))
	if start == end:
		print(t+'は存在しません')
	else:
		print(t+'は存在します')
"""

#lcp配列の作成
def getLCP(i,j):
	h = 0
	while i+h < n and j+h < n:
		if s[j+h] != s[i+h]:
			break
		h+=1
	return h

#lcp配列の最大値=最長の共通部分文字列のインデックス
#ans = sorted_list[ lcp.index(max(lcp)) ]
#ans = ans[:max(lcp)]
#print(ans)

ans = 0
for i in range(0,n):
	for j in range(i+1,n):
		lcp = min(getLCP(i,j),j-i)
		ans = max(ans,lcp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import cmp_to_key
import math
import bisect

n = int(input())
s = input()
k = 1
rank = [0] * (n+1)
tmp = [0] * (n+1)
sa = [''] * (n+1)

def compare_sa(i,j):
	if rank[i] != rank[j]:
		return -1 if rank[i] < rank[j] else 1
	else:
		if i + k <= n:
			ri = rank[i+k]
		else:
			ri = -1
		if j + k <= n:
			rj = rank[j+k]
		else:
			rj = -1
		return -1 if ri < rj else 1


for i in range(n+1):
	sa[i] = i
	if i < n:
		rank[i] = ord(s[i])
	else:
		rank[i] = -1

while k <= n:

	sa = sorted(sa,key=cmp_to_key(compare_sa))

	tmp[sa[0]] = 0

	for i in range(1,n+1):
		if compare_sa(sa[i-1],sa[i]) == -1:
			tmp[sa[i]] = tmp[sa[i-1]] + 1
		else:
			tmp[sa[i]] = tmp[sa[i-1]]

	for i in range(n+1):
		rank[i] = tmp[i]

	k *= 2

#saはインデックス、sorted_listは実際の文字列
sorted_list = []
for i in range(n+1):
	sorted_list.append(s[sa[i]:])
#print(sa)
#print(sorted_list)

#文字列検索
"""
T = ['ab','abra','abc','abracadabra','abracadabraaa','brabra','bra']
for t in T:
	start = bisect.bisect_left(sorted_list,t)
	end = bisect.bisect_left(sorted_list,t[:-1]+chr(ord(t[-1])+1))
	if start == end:
		print(t+'は存在しません')
	else:
		print(t+'は存在します')
"""

#lcp配列の作成
def getLCP(i,j):
	h = 0
	while i+h < n and j+h < n:
		if s[j+h] != s[i+h]:
			break
		h+=1
	return h

#lcp配列の最大値=最長の共通部分文字列のインデックス
#ans = sorted_list[ lcp.index(max(lcp)) ]
#ans = ans[:max(lcp)]
#print(ans)

ans = 0
for i in range(0,n):
	for j in range(i+1,n):
		lcp = min(getLCP(i,j),j-i)
		ans = max(ans,lcp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    import sys
    input=sys.stdin.readline
    N = int(input().rstrip())
    S = input().rstrip()

    def z_algo(s):
        """
        param s:str
        return list of int with length len(s)
        """
        # initialization
        n=len(s)
        z=[0]*n
        z[0]=n
        # construct
        L,R=0,0
        for i in range(1,n):
            if i>R: # 過去の結果が全く使えない
                L=R=i
                while(R<n and s[R-L]==s[R]): R+=1
                z[i]=R-L
                R-=1 # 0-indexedでiと比較するため
            elif z[i-L]<R-i+1:
                z[i]=z[i-L]
            else:
                L=i
                R+=1 # Rまでは確定しているので、R+1から確認
                while(R<n and s[R-L]==s[R]): R+=1
                z[i]=R-L
                R-=1
        return z

    ans = 0
    #for i in range(N-1):
    #    z = z_algo(S[i:])
    #    z = z[(len(z)+1)//2:]
    #    max_z = max(z)
    #    ans = max(ans, max_z)
    for i in range(N-1):
        z = z_algo(S[i:])
        for j in range(len(z)):
            ans=max(ans,min(j,z[j]))
    print(ans)

resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
N = int(input().rstrip())
S = input().rstrip()

def z_algo(s):
    """
    param s:str
    return list of int with length len(s)
    """
    # initialization
    n=len(s)
    z=[0]*n
    z[0]=n
    # construct
    L,R=0,0
    for i in range(1,n):
        if i>R: # 過去の結果が全く使えない
            L=R=i
            while(R<n and s[R-L]==s[R]): R+=1
            z[i]=R-L
            R-=1 # 0-indexedでiと比較するため
        elif z[i-L]<R-i+1:
            z[i]=z[i-L]
        else:
            L=i
            R+=1 # Rまでは確定しているので、R+1から確認
            while(R<n and s[R-L]==s[R]): R+=1
            z[i]=R-L
            R-=1
    return z

ans = 0
for i in range(N-1):
    z = z_algo(S[i:])
    z = z[(len(z)+1)//2:]
    max_z = max(z)
    ans = max(ans, max_z)
print(ans)

Submission status: Time Limit Exceeded

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

def z_algo(s):
    """
    param s:str
    return list of int with length len(s)
    """
    # initialization
    n=len(s)
    z=[0]*n
    z[0]=n
    # construct
    L,R=0,0
    for i in range(1,n):
        if i>R: # 過去の結果が全く使えない
            L=R=i
            while(R<n and s[R-L]==s[R]): R+=1
            z[i]=R-L
            R-=1 # 0-indexedでiと比較するため
        elif z[i-L]<R-i+1:
            z[i]=z[i-L]
        else:
            L=i
            R+=1 # Rまでは確定しているので、R+1から確認
            while(R<n and s[R-L]==s[R]): R+=1
            z[i]=R-L
            R-=1
    return z

ans = 0
for i in range(N-1):
    z = z_algo(S[i:])
    z = z[(len(z)+1)//2:]
    max_z = max(z)
    ans = max(ans, max_z)
print(ans)

Submission status: Time Limit Exceeded

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

def z_algo(s):
    """
    param s:str
    return list of int with length len(s)
    """
    # initialization
    n=len(s)
    z=[0]*n
    z[0]=n
    # construct
    L,R=0,0
    for i in range(1,n):
        if i>R: # 過去の結果が全く使えない
            L=R=i
            while(R<n and s[R-L]==s[R]): R+=1
            z[i]=R-L
            R-=1 # 0-indexedでiと比較するため
        elif z[i-L]<R-i+1:
            z[i]=z[i-L]
        else:
            L=i
            R+=1 # Rまでは確定しているので、R+1から確認
            while(R<n and s[R-L]==s[R]): R+=1
            z[i]=R-L
            R-=1
    return z

ans = 0
for i in range(N):
    z = z_algo(S[i:])
    z = z[(len(z)+1)//2:]
    if z:
        max_z = max(z)
        ans = max(ans, max_z)
print(ans)

Submission status: Time Limit Exceeded

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

def z_algo(S):
    N = len(S)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A

ans = 0
for i in range(N):
    z = z_algo(S[i:])
    z = z[(len(z)+1)//2:]
    if z:
        max_z = max(z)
        ans = max(ans, max_z)
print(ans)

Submission status: Time Limit Exceeded

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

def z_algorithm(str):
    len_str = len(str)
    p = [0] * len_str
    j = 0
    for i in range(1, len_str):
        if i + p[i-j] < j + p[j]:
            p[i] = p[i-j]
        else:
            k = max(0, j+p[j]-i)
            while i + k < len_str and str[k] == str[i+k] and k < i:
                k += 1
            p[i] = k
            j = i
    p[0] = 0
    return max(p)

ans = 0
for i in range(n-1):
    ans = max(ans, z_algorithm(s[i:]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from array import array

N = int(input())
S = array('B', map(ord, list(input())))

s2 = len(S)-1

len_max = 0


def len_common_substring(s1, s2):
    l = 1
    #    _s1 = s1 + 1
    #    _s2 = s2 + 1
    #    while(_s2 < len(S) and _s1 < s2):
    for _s1, _s2 in zip(range(s1+1, s2), range(s2+1, len(S))):
        if S[_s1] != S[_s2]:
            return l
        l += 1
#        _s1 += 1
#        _s2 += 1
        #print(_s1, _s2)
    return l


def len_longest_common_substring_starts_with_s2():
    s1 = s2-1
    longest = 0
    while(s1>=0):
        if S[s1] == S[s2]:
            longest = max(longest, len_common_substring(s1, s2))
        s1 -= 1
    return longest

while(s2>=0):
    l = len_longest_common_substring_starts_with_s2()
    len_max = max(len_max, l)
    s2 -= 1
    

print(len_max)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import re


def resolve():
    n = int(input())
    s = input()
    for i in range(n // 2, 0, -1):
        c = Counter([s[x: x + i] for x in range(n - i + 1)])
        for j in c.most_common():
            if j[1] < 2:
                break
            if re.match(r"^.*" + j[0] + r".*" + j[0] + r".*$", s):
                print(i)
                return
    print(0)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from array import array

N = int(input())
S = array('B', map(ord, list(input())))

s2 = len(S)-1

len_max = 0


def len_common_substring(s1, s2):
    l = 1
    _s1 = s1 + 1
    _s2 = s2 + 1
    while(_s2 < len(S) and _s1 < s2):
        if S[_s1] != S[_s2]:
            return l
        l += 1
        _s1 += 1
        _s2 += 1
        #print(_s1, _s2)
    return l


def len_longest_common_substring_starts_with_s2():
    s1 = s2-1
    longest = 0
    while(s1>=0):
        if S[s1] == S[s2]:
            longest = max(longest, len_common_substring(s1, s2))
        s1 -= 1
    return longest

while(s2>=0):
    l = len_longest_common_substring_starts_with_s2()
    len_max = max(len_max, l)
    s2 -= 1
    

print(len_max)

Submission status: Time Limit Exceeded

Solution code:
from array import array

N = int(input())
S = array('B', map(ord, list(input())))

s2 = len(S)-1

len_max = 0


def len_common_substring(s1, s2):
    l = 1
    _s1 = s1 + 1
    _s2 = s2 + 1
    while(_s2 < len(S) and _s1 < s2):
        if S[_s1] == S[_s2]:
            l += 1
        else:
            return l
        _s1 += 1
        _s2 += 1
        #print(_s1, _s2)
    return l


def len_longest_common_substring_starts_with_s2():
    s1 = s2-1
    longest = 0
    while(s1>=0):
        if S[s1] == S[s2]:
            longest = max(longest, len_common_substring(s1, s2))
        s1 -= 1
    return longest

while(s2>=0):
    l = len_longest_common_substring_starts_with_s2()
    len_max = max(len_max, l)
    s2 -= 1
    

print(len_max)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


def resolve():
    n = int(input())
    s = input()
    for i in range(n // 2, 0, -1):
        c = Counter([s[x:x + i] for x in range(n - i + 1)])
        for j in [x for x in c if c.get(x) > 1]:
            if j in s[s.find(j) + i:]:
                print(i)
                return
    print(0)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

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

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

print(ans)

Submission status: Time Limit Exceeded

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from array import array

N = int(input())
S = array('B', map(ord, list(input())))

s2 = len(S)-1

len_max = 0


def len_common_substring(s1, s2):
    l = 0
    _s1 = s1
    _s2 = s2
    while(_s2 < len(S) and _s1 < s2):
        if S[_s1] == S[_s2]:
            l += 1
        else:
            return l
        _s1 += 1
        _s2 += 1
        #print(_s1, _s2)
    return l


def len_longest_common_substring_starts_with_s2():
    s1 = s2-1
    longest = 0
    while(s1>=0):
        if S[s1] == S[s2]:
            longest = max(longest, len_common_substring(s1, s2))
        s1 -= 1
    return longest

while(s2>=0):
    l = len_longest_common_substring_starts_with_s2()
    len_max = max(len_max, l)
    s2 -= 1
    

print(len_max)

Submission status: Time Limit Exceeded

Solution code:
from array import array

N = int(input())
S = array('u', list(input()))

s2 = len(S)-1

len_max = 0


def len_common_substring(s1, s2):
    l = 0
    _s1 = s1
    _s2 = s2
    while(_s2 < len(S) and _s1 < s2):
        if S[_s1] == S[_s2]:
            l += 1
        else:
            return l
        _s1 += 1
        _s2 += 1
        #print(_s1, _s2)
    return l


def len_longest_common_substring_starts_with_s2():
    s1 = s2-1
    longest = 0
    while(s1>=0):
        if S[s1] == S[s2]:
            longest = max(longest, len_common_substring(s1, s2))
        s1 -= 1
    return longest

while(s2>=0):
    l = len_longest_common_substring_starts_with_s2()
    len_max = max(len_max, l)
    s2 -= 1
    

print(len_max)

Submission status: Time Limit Exceeded

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

ans = 0
dp = [0] * N
for i in range(N - 1):
    dp2 = dp[:]
    for j in range(i + 1, N):
        if S[i] == S[j] and j - i > dp2[j-1]:
            dp[j] = dp2[j-1] + 1
            ans = max(ans, dp[j])
        else:
            dp[j] = 0

print(ans)

Submission status: Time Limit Exceeded

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

def check(l):
    for i in range(N - 2 * l + 1):
        if S.find(S[i : i + l], i + l) > 0:
            return True

ok = 0
ng = N // 2 + 1

while ng - ok > 1:
    m = (ok + ng) // 2
    if check(m):
        ok = m
    else:
        ng = m

print(ok)

Submission status: Time Limit Exceeded

Solution code:
from random import shuffle
N = int(input())
S = input()

def check(l):
    r = list(range(N - 2 * l + 1))
    shuffle(r)
    for i in r:
        if S[i : i + l] in S[i + l :]:
            return True

ok = 0
ng = N // 2 + 1

while ng - ok > 1:
    m = (ok + ng) // 2
    if check(m):
        ok = m
    else:
        ng = m

print(ok)

Submission status: Time Limit Exceeded

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

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

ans = 0
for i in range(N):
    for j in range(i + 1, N):
        pre = dp[i-1][j-1]
        if S[i] == S[j] and j - i > pre:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = dp[i-1][j]
        ans = max(ans, dp[i][j])
print(ans)

Submission status: Time Limit Exceeded

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

ok = 0
ng = N // 2 + 1

while ng - ok > 1:
    m = (ok + ng) // 2
    if any([S[i : i + m] in S[i + m :] for i in range(N - 2 * m + 1)]):
        ok = m
    else:
        ng = m

print(ok)

Submission status: Time Limit Exceeded

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

ok = 0
ng = N // 2 + 1

while ng - ok > 1:
    m = (ok + ng) // 2
    if any(S[i : i + m] in S[i + m :] for i in range(N - 2 * m + 1)):
        ok = m
    else:
        ng = m

print(ok)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

def check(l):
    for i in range(N - 2 * l + 1):
        if S[i : i + l] in S[i + l :]:
            return True

ok = 0
ng = N // 2 + 1

while ng - ok > 1:
    m = (ok + ng) // 2
    if check(m):
        ok = m
    else:
        ng = m

print(ok)

Submission status: Time Limit Exceeded

Solution code:
# 速いやつの文字列inを使った省メモリver
N = int(input())
S = input()

def check(l):
    for i in range(N - 2 * l + 1):
        if S[i : i + l] in S[i + l :]:
            return True

ok = 0
ng = N // 2 + 1

while ng - ok > 1:
    m = (ok + ng) // 2
    if check(m):
        ok = m
    else:
        ng = m

print(ok)

Submission status: Time Limit Exceeded

Solution code:
from itertools import count
 
N = int(input())
S = input()
 
abc = 'abcdefghijklmnopqrstuvwxyz'
 
T = ['']
 
flag = True
for i in count():
    T2 = T[:]
    T = []
    for t in T2:
        for c in abc:
            if S.count(t + c) > 1:
                T.append(t + c)
                flag = False
    if flag:
        print(i)
        break
    flag = True

Submission status: Time Limit Exceeded

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

def z_algorithm_no_overlap(S_):
    N_ = len(S_)
    Z_ = [0] * N_
    L_ = R_ = 0
    for i in range(1, N_):
        if i > R_:
            L_ = R_ = i
            while R_ < N_ and S_[R_-L_] == S_[R_]:
                R_ += 1
            Z_[i] = R_ - L_
            R_ -= 1
        else:
            k = i - L_
            if Z_[k] < R_ - i + 1:
                Z_[i] = Z_[k]
            else:
                L_ = i
                while R_ < N_ and S_[R_-L_] == S_[R_]:
                    R_ += 1
                Z_[i] = R_ - L_
                R_ -= 1
    for i, z in enumerate(Z_):
        if z > i:
            Z_[i] = i
    return Z_
        
print(max(max(z_algorithm_no_overlap(S[i:])) for i in range(N-1)))

Submission status: Time Limit Exceeded

Solution code:
def calc_length(s: str, l1: int, l2: int, n: int) -> int:
  max_len = min([l2 - l1, n - l2])
  for i in range(1, max_len):
    if s[l1 + i] != s[l2 + i]:
      return i
  return max_len

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

longest = 0
for l1 in range(n - 2, -1, -1):
  for l2 in range(l1 + longest + 1, n):
    if s[l1] == s[l2]:
      length = calc_length(s, l1, l2, n)
      if length > longest:
        longest = length

print(longest)

Submission status: Time Limit Exceeded

Solution code:
def calc_length(s: str, l1: int, l2: int, n: int) -> int:
  max_len = min([l2 - l1, n - l2])
  for i in range(1, max_len):
    if s[l1 + i] != s[l2 + i]:
      return i
  return max_len

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

longest = 0
for l1 in range(n - 1):
  for l2 in range(l1 + 1, n):
    if s[l1] == s[l2]:
      length = calc_length(s, l1, l2, n)
      if length > longest:
        longest = length

print(longest)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
ans = 0
for i in range(0, n-1):
	for j in range(i+1, n):
		to_find = s[i:j]
		if s[j:].find(to_find) == -1:
			break
		else:
			ans_pos = j - i 
			if ans_pos > ans:
				ans = ans_pos
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
ans = 0
for i in range(0, n-1):
	for j in range(i, n):
		to_find = s[i:j]
		if s[j:].find(to_find) != -1:
			ans_pos = j - i 
			if ans_pos > ans:
				ans = ans_pos
		
print(ans)

Submission status: Time Limit Exceeded

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

vlen = 0
for l1 in range(N):
    for l2 in range(l1+1, N):
        i = 0
        while l1 + i < l2 and l2 + i < N:
            if S[l1 + i] != S[l2 + i]:
                break
            i += 1
        vlen = max(i, vlen)
print(vlen)

Submission status: Time Limit Exceeded

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

    def z_algorithm(string):
        n = len(string)
        ret = [0] * n
        i, j = 1, 0
        while i < n:
            while i + j < n and string[j] == string[i + j]:
                j += 1
            ret[i] = j
            if j == 0:
                i += 1
                continue
            k = 1
            while i + k < n and k + ret[k] < j:
                ret[i + k] = ret[k]
                k += 1
            i += k
            j -= k
        return ret

    ans = 0
    for i in range(N):
        t = S[i:N]
        lcp = z_algorithm(t)  # Longest Common Prefix
        for j in range(len(t)):
            ans = max(ans, min(lcp[j], j))
    return ans

print(e_who_says_a_pun())

Submission status: Time Limit Exceeded

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

    base = 37
    def rolling_hash(s, mod):
        l = len(s)
        h = [0]*(l + 1)
        v = 0
        for i in range(l):
            h[i+1] = v = (v * base + ord(s[i])) % mod
        pw = [1]*(l + 1)
        v = 1
        for i in range(l):
            pw[i+1] = v = v * base % mod
        return h, pw

    mod1 = 10**9 + 9; mod2 = 10**9 + 7
    h1, pw1 = rolling_hash(S, mod1)
    h2, pw2 = rolling_hash(S, mod2)

    def chk(l, h, pw, mod):
        p = pw[l]
        for i in range(min(l, N-2*l+1)):
            D[i] = (h[l+i] - h[i]*p) % mod
        s = set()
        for i in range(l, N-l+1):
            s.add(D[i-l])
            D[i] = v = (h[l+i] - h[i]*p) % mod
            if v in s:
                return 1
        return 0

    H = [set() for i in range(N//2+2)]
    D = [0]*N
    E = [0]*N
    k = N//2
    for l in range(1, N//2+1):
        if not chk(l, h1, pw1, mod1):
            k = l-1
            break
    ans = 0
    for l in range(k, 0, -1):
        if chk(l, h2, pw2, mod2):
            ans = l
            break
    print(ans)
solve()

Submission status: Time Limit Exceeded

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

for vlen in range(N // 2, -1, -1):
    for l1 in range(N - vlen * 2 + 1):
        for l2 in range(l1 + vlen, N):
            if S[l1:l1 + vlen] == S[l2:l2 + vlen]:
                print(vlen)
                exit()
print(0)

Submission status: Time Limit Exceeded

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

for vlen in range(N // 2, -1, -1):
    for l1 in range(N - vlen + 1):
        for l2 in range(l1 + vlen, N):
            if S[l1:l1 + vlen] == S[l2:l2 + vlen]:
                print(vlen)
                exit()
print(0)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ab = str(input())

ans = [0]
lenab = len(ab)

for h in range(lenab):
    abc = ab[h:]
    lenabc = len(abc)
    i = 1; j = 0
    while i < lenabc:
        while i+j < lenabc and abc[j] == abc[i+j] and j < i:
            j += 1
        if j == 0:
            i += 1
        else:
            ans.append(j)
            i += 1
            j=0

print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
from heapq import *
sys.setrecursionlimit(200000)
input = sys.stdin.readline

N, = map(int, input().split())
# L = [int(v) for v in input().split()]
# L = [int(input()) for _ in range(Q)]
S = input().strip()

t = N // 2 + 1
l = 2
r = t
sl = len(S)
ff = False
for _ in range(20):
    m = (l + r) // 2
    f = False
    for i in range(sl - m):
        for j in range(i + m, sl):
            if S[i:i+m] == S[j:j+m]:
                f = True
                break
        if f:
            break
    if f:
        ff = True
        l = m
    else:
        r = m

if ff:
    print((l + r) // 2)
else:
    print(0)

Submission status: Time Limit Exceeded

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

ans = 0
left, right = 0, 1

while right < N:
    s = S[left:right]
    if s in S[right:]:
        right += 1
        ans = max(ans, len(s))
    else:
        left = right - 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
s = input()
dp = [[0]*(n+1) for y in range(n+1)]
ans = 0

for i in range(n):
    a = n-1-i
    for j in range(n):
        b = n-1-j
        if s[a] == s[b]:
            dp[a][b] = dp[a+1][b+1] + 1
for i in range(n):
    for j in range(n):
        now = min(dp[i][j], j-i)
        ans = max(ans, now)
print(ans)