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:
def main():
    N = int(input())
    S = input()
    dp = [[0] * (N + 1) for _ in range(N + 1)]
    r = 0
    for i in reversed(range(N)):
        s = S[i]
        for j in reversed(range(i, N)):
            if s == S[j]:
                dp[i][j] = dp[i + 1][j + 1] + 1
            r = max(r, min(dp[i][j], j - i))
    print(r)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	N = II()
	SS = IS()
	ans = 0
	for l in range(N-1):
		i = 1
		j = 0
		S = copy.copy(SS[l:])
		A = [0]*len(S)
		while (i < len(S)):
			while (i+j < len(S) and S[j] == S[i+j] and j < i):
				j+=1
			A[i] = j
			if (j == 0):
				i+=1
				continue
			i += 1
			j = 0
		ans = max(max(A),ans)
	print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
#https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
class RollingHash():
    def __init__(self, s, base, mod):
        self.mod = mod
        self.pw = pw = [1]*(len(s)+1)
 
        l = len(s)
        self.h = h = [0]*(l+1)
 
        v = 0
        for i in range(l):
            h[i+1] = v = (v * base + ord(s[i])) % mod
        v = 1
        for i in range(l):
            pw[i+1] = v = v * base % mod
    def get(self, l, r):
        return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod
N=int(input())
S=input()
R1=RollingHash(S,37,10**9+7)
R2=RollingHash(S,29,10**9+9)
R3=RollingHash(S,36,10**10+19)
ans=0
for ln in range(1,N//2+1):
    D=dict()
    for l in range(N-ln+1):
        tmp=(R1.get(l,l+ln),R2.get(l,l+ln),R3.get(l,l+ln))
        if tmp in D:
            if D[tmp]+ln<=l:
                ans=max(ln,ans)
        else:
            D[tmp]=l
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
class RollingHash():
    def __init__(self, s, base, mod):
        self.mod = mod
        self.pw = pw = [1]*(len(s)+1)
 
        l = len(s)
        self.h = h = [0]*(l+1)
 
        v = 0
        for i in range(l):
            h[i+1] = v = (v * base + ord(s[i])) % mod
        v = 1
        for i in range(l):
            pw[i+1] = v = v * base % mod
    def get(self, l, r):
        return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod
N=int(input())
S=input()
R1=RollingHash(S,37,10**9+7)
R2=RollingHash(S,29,10**9+9)
ans=0
for ln in range(1,N//2+1):
    D=dict()
    for l in range(N-ln+1):
        tmp=(R1.get(l,l+ln),R2.get(l,l+ln))
        if not(tmp in D):
            D[tmp]=[l,l]
        D[tmp][1]=max(D[tmp][1],l)
        D[tmp][0]=min(D[tmp][0],l)
    #print(ln,D)
    for k in D:
        if D[k][1]-D[k][0]>=ln:
            ans=max(ans,ln)
print(ans)

Submission status: Time Limit Exceeded

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

s=[[0]*N for i in range(N)]
k=0
while(k<N-1):
  i=k+1
  while(i<N):
    j=0
    while(i+j<N and k+j < i):
      if S[i+j]==S[j+k]:
        j+=1
      else:
        break
    s[k][i]=j
    i+=1
  k+=1
ans=0
for i in range(N):
  ans=max(ans,max(s[i]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    n = int(input())
    s = input()
    for i in range(n//2, 0, -1):
      for j in range(n-i):
        if s[j:j+i] in s[j+i:]:
          print(i)
          return
    print(0)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import re


def resolve():
    n = int(input())
    s = input()
    for i in range(n//2, 0, -1):
      for j in range(n-i):
        if re.search(s[j:j+i]+r".*"+s[j:j+i],s)!=None:
          print(i)
          return
    print(0)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

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


def z_algorithm(s):
    n = len(s)
    lcpls = [0] * n  # Longest common prefix length
    lcpls[0] = n

    l = r = 1
    while l < n:
        while (r < n) and (s[r - l] == s[r]):
            r += 1

        if l == r:
            l += 1
            r += 1
            continue

        lcpls[l] = r - l

        k = 1
        while (l + k < r) and (lcpls[k] < r - l - k):
            lcpls[l + k] = lcpls[k]
            k += 1
        l += k

    return lcpls


ans = 0
for i in range(N):
    X = S[i:]
    Z = z_algorithm(X)

    for j, z in enumerate(Z):
        if j >= z:
            ans = max(ans, z)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

al = {'a':1, 'b':2, 'c':3, 'd':4, 'e':5, 'f':6, 'g':7, 'h':8, 'i':9, 'j':10, 'k':11, 'l':12, \
  'm':13, 'n':14, 'o':15, 'p':16, 'q':17, 'r':18, 's':19, 't':20, 'u':21, 'v':22, 'w':23, 'x':24, 'y':25, 'z':26}

def foo(l,s):
    b = 10**9+7
    r = 2**60
    t = 1
    h = 0
    for i in range(l-1,-1,-1):
        h = (h+t*al[s[i]])%r
        t = (t*b)%r
    g = {h:0}
    for i in range(1,n-l+1):
        h = (h*b-al[s[i-1]]*t+al[s[i+l-1]])%r
        if h in g:
            if g[h]+l <= i:
                return True
        else:
            g[h] = i
    return False


n = inn()
s = ins()
for i in range(n//2,0,-1):
    if foo(i,s):
        print(i)
        exit()
print(0)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
ans = 0
l, r = 0, 1

while l<N:
    s1 = S[l]
    v = 0
    while r<N:
        s2 = S[r]
        if s1!=s2:
            r+=1
            continue
        v = 1
        for i in range(1, r-l):
            if r+i>=N or l+i>=r:break
            if S[l+i]!=S[r+i]:continue
            v+=1
        ans = max(ans, v)
        r+=1
    l+=1
    r=l+1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7
#from collections import defaultdict

def ddprint(x):
  if DBG:
    print(x)

n = inn()
s = ins()
for m in range(n//2,0,-1):
    h = {}
    for i in range(n-m+1):
        t = s[i:i+m]
        if t not in h:
            h[t] = [i,i]
        else:
            h[t] = [min(h[t][0],i), max(h[t][1],i)]
            if h[t][1]-h[t][0]>=m:
                print(m)
                exit()
print(0)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7
#from collections import defaultdict

def ddprint(x):
  if DBG:
    print(x)

n = inn()
s = ins()
for m in range(n//2,0,-1):
    h = {}
    for i in range(n-m+1):
        t = s[i:i+m]
        if t not in h:
            h[t] = [i]
        else:
            h[t].append(i)
    for t in h:
        if len(h[t])>=2 and max(h[t])-min(h[t])>=m:
            print(m)
            exit()
print(0)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7
from collections import defaultdict

def ddprint(x):
  if DBG:
    print(x)

n = inn()
s = ins()
for m in range(n//2,0,-1):
    h = {}
    for i in range(n-m+1):
        t = s[i:i+m]
        if t not in h:
            h[t] = [(i,i+m)]
        else:
            for j,k in h[t]:
                if i+m<=j or k<=i:
                    print(m)
                    exit()
            h[t].append((i,i+m))
print(0)

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+1, n):
        # print("check i,j:({}, {})".format(i,j))
        check_i = i
        check_j = j
        while True:
            if check_j >= n:
                break

            elif s[check_i] == s[check_j] and (j - i) > (check_i - i) and check_j < n:
                # print("OK next i:j, ({}, {})".format(check_i,check_j))

                length = check_i - i + 1
                if length > max_length:
                    max_length = length

                check_i += 1
                check_j += 1

            else:
                break

print(max_length)

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    S = str(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-1):
        z = z_algo(S[i:])
        ans = max(ans,max(z[-((N-i)//2):]))
        
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
N = int(input())
S = input().strip()
G = {chr(i):[] for i in range(97,123)}
for i in range(N):
    G[S[i]].append(i)
cmax = 0
for a in G:
    for x in combinations(G[a],2):
        i,j = x[0],x[1]
        if i>j:
            i,j = j,i
        cnt = 0
        for k in range(j-i):
            if j+k<N and S[i+k] == S[j+k]:
                cnt += 1
            else:break
        cmax = max(cmax,cnt)
        
print(cmax)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
ans = 0
for n in range(N):
    X = S[:n]
    Y = S[n:]
    dp = [[0 for i in range(len(X)+1)] for j in range(len(Y)+1)] #0で初期化

    for i in range(len(Y)):
        for j in range(len(X)):
            if X[j] == Y[i]:
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
    ans = max(ans, dp[-1][-1])
print(ans)

Submission status: Time Limit Exceeded

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

strs = []
for n in range(N):
    if S[n] not in strs:
        strs.append(S[n])
ans = 0
for x in strs:
    for n in range(N-1):
        if S[n] == x:
            for m in range(n+1, N):
                l = 0
                if S[m] == x:
                    l = 0
                    while l < m-n:
                        if S[n:n+l+1] != S[m:m+l+1]:
                            break
                        l += 1
                ans = max(ans, l)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

p = 2 ** 61 - 1
p2 = 10 ** 8 + 7
q = 10 ** 2

def rollingHash(N, M, A, ans):
	mul = 1
	for i in range(M):
		mul = (mul * q) % p

	Droll = defaultdict(lambda:-1)
	val = 0
	for i in range(M):
		val = val * q + A[i]
		val %= p

	Droll[val] = 0
	for i in range(N - M):
		val = (val * q - A[i] * mul + A[i + M]) % p
		if Droll[val] != -1 and i + 1 - Droll[val] >= M:
			return M

		Droll[val] = i + 1
	return ans

#処理内容
def main():
	N = int(input())
	S = list(input())
	for i in range(N):
		S[i] = ord(S[i]) - 97

	ans = 0
	for i in range(1, N):
		ans = rollingHash(N, i, S, ans)

	print(ans)



if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

p = 10 ** 9 + 7
p2 = 2 ** 61 - 1
q = 10 ** 2

def rollingHash(N, M, A, ans):
	mul1 = 1
	mul2 = 1
	for i in range(M):
		mul1 = (mul1 * q) % p
		mul2 = (mul2 * q) % p2

	Droll1 = defaultdict(lambda:-1)
	Droll2 = defaultdict(lambda:-1)
	val1 = 0
	val2 = 0
	for i in range(M):
		val1 = val1 * q + A[i]
		val1 %= p
		val2 = val2 * q + A[i]
		val2 %= p2

	Droll1[val1] = 0
	Droll2[val2] = 0
	for i in range(N - M):
		val1 = (val1 * q - A[i] * mul1 + A[i + M]) % p
		val2 = (val2 * q - A[i] * mul2 + A[i + M]) % p2

		if Droll1[val1] != -1 and Droll1[val1] == Droll2[val2] and i + 1 - Droll1[val1] >= M:
			return M

		Droll1[val1] = i + 1
		Droll2[val2] = i + 1

	return ans

#処理内容
def main():
	N = int(input())
	S = list(input())
	for i in range(N):
		S[i] = ord(S[i]) - 97

	ans = 0
	for i in range(1, int(N // 2) + 1):
		ans = rollingHash(N, i, S, ans)

	print(ans)



if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

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


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

    max = 0

    for p in range(len(S)):
        S = S[1:]

        # Z algorithm
        A = [0] * len(S)
        i = 1
        j = 0
    
        while ( i < len(S)):
            while (i+j < len(S) and S[j] == S[i+j]):
                j += 1
            A[i] = j
            if (j <= i and j > max):
                max = j
    
            if j == 0:
                i += 1
                continue
            k = 1
            while (i+k < len(A) and k+A[k] < j):
                A[i+k] = A[k]
                k += 1
            i += k
            j -= k

    print(max)

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

n = int(input())
s = input()
ans = 0
for i in range(n):
  A = z_algo(s[i:])
  for j in range(1, n-i):
    m = min(j, A[j])
    ans = max(m, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def z_algo(S):
    '''
    Input: a string S
    Output: an array Z[0..|S| - 1]
            Z[i] = l: the length of the longest prefix of S[i..|S| - 1] which is also a prefix of S,
            i.e.,
                S[j] = S[i + j] for all 0 <= j < l (l != 0),
                S[0] != S[i] (l == 0)
    Time complexity: O(|S|) time
    '''
    N = len(S)
    Z = [-1] * N
    Z[0] = N
    L = 0; R = 0 # algorithm invariant: S[L..R] is always set to be the longest common prefix of S[L..|S| - 1]
    for i in range(1, N):
        if i > R: # naive calculation
            j = 0
            while i + j < N and S[j] == S[i + j]: j += 1
            Z[i] = j
            if j > 0: L = i; R = i + j - 1
        else: # i in [L, R]
            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
    return Z

N = int(input())
S = input()
ans = 0
for i in range(N-1):
    Z = z_algo(S[i:])
    for j, z in enumerate(Z):
        ans = max(ans, min(z, j))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def z_algo(S):
    '''
    Input: a string S
    Output: an array Z[0..|S| - 1]
            Z[i] = l: the length of the longest prefix of S[i..|S| - 1] which is also a prefix of S,
            i.e.,
                S[j] = S[i + j] for all 0 <= j < l (l != 0),
                S[0] != S[i] (l == 0)
    Time complexity: O(|S|) time
    '''
    N = len(S)
    Z = [-1] * N
    Z[0] = N
    L = 0; R = 0 # algorithm invariant: S[L..R] is always set to be the longest common prefix of S[L..|S| - 1]
    for i in range(1, N):
        if i > R: # naive calculation
            j = 0
            while i + j < N and S[j] == S[i + j]: j += 1
            Z[i] = j
            if j > 0: L = i; R = i + j - 1
        else: # i in [L, R]
            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
    return Z

N = int(input())
S = input()
ans = 0
for i in range(N-1):
    Z = z_algo(S[i:])
    for j, z in enumerate(Z[1:], 1):
        ans = max(ans, min(z, j))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input().strip()
k = 0
D = {chr(i):[] for i in range(97,123)}
D[S[0]].append(0)
for i in range(1,N):
    a = S[i]
    if len(D[a])>0:
        if k==0:
            k += 1
        else:
            for j in D[a]:
                if j-k>=0 and S[j-k:j]==S[i-k:i] and i-j>=k+1:
                    k += 1
                    break
    D[a].append(i)
print(k)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input().strip()
cnt = 0
for k in range(N//2,0,-1):
    A = []
    for i in range(N-k+1):
        A.append((S[i:i+k],i))
    A = sorted(A,key=lambda x:x[0])
    cur = 0
    for i in range(1,N-k+1):
        if A[i][0]!=A[i-1][0]:
            cur = i
        else:
            if A[i][1]-A[cur][1]>=k:
                cnt = k
                break
            else:
                continue
    if A[N-k][1]-A[cur][1]>=k:
        cnt = k
    if cnt>0:break
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys

n = int(input())
string = input()

# 辞書作成
alphabets = {chr(i):[] for i in range(97,123)}

for i, c in enumerate(string):
    alphabets[c].append(i)


Nmax = min(n-len(set(string)), n//2)+1

for nmax in reversed(range(Nmax)):

    for i1 in range(n-nmax):
        a = string[i1]

        for i2 in alphabets[a]:
            if i1==i2 or i2 < i1+nmax:
                continue
            
            if string[i1:i1+nmax]==string[i2:i2+nmax]:
                print(nmax)
                sys.exit()
    

print(0)

Submission status: Time Limit Exceeded

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

# 辞書作成
alphabets = {chr(i):[] for i in range(97,123)}

for i, c in enumerate(string):
    alphabets[c].append(i)


Nmax = min(n-len(set(string)), n//2)+1

for nmax in reversed(range(Nmax)):

    for i1 in range(n-nmax):
        a = string[i1]

        for i2 in alphabets[a]:
            if i1==i2 or i2 < i1+nmax:
                continue
            
            if string[i1:i1+nmax]==string[i2:i2+nmax]:
                print(nmax)
                quit()
    

print(0)

Submission status: Time Limit Exceeded

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




# 辞書作成
alphabets = {chr(i):[] for i in range(97,123)}

for i, c in enumerate(s):
    alphabets[c].append(i)

# 
Smax = 0
for i, c in enumerate(s):

    for j in alphabets[c]:


        if i==j:
            continue


        k = 0
        while i+k<j and j+k<n:
            
            if s[i+k]==s[j+k]:
                k += 1
            else:
                Smax = max(k, Smax)
                break
        else:
            Smax = max(k, Smax)

print(Smax)

Submission status: Time Limit Exceeded

Solution code:
import time
import random
N = int(input())
s = str(input())
maxlen = N//2
start = time.time()
def solve(tgt):
    for i in range(N-tgt*2+1):
        if s[i:i+tgt] in s[i+tgt:]:
            return True
    return False

ng = maxlen + 1
ok = 0
if N>650:
    ok = 2
first = 1
while ng-ok > 1:
    end = time.time()
    if end-start > 1.8:
        r = random.random.randint(ok,ng-1)
        print(r)
        exit()
    tgt = (ok+ng)//2
    if first == 1:
        tgt == tgt*7//8
        first = 0
    if solve(tgt):
        ok = tgt
    else:
        ng = tgt
print(ok)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
s = str(input())
maxlen = N//2

def solve(tgt):
    for i in range(N-tgt*2+1):
        if s[i:i+tgt] in s[i+tgt:]:
            return True
    return False

ng = maxlen + 1
ok = 0
if N>650:
    ok = 2
first = 1
while ng-ok > 1:
    tgt = (ok+ng)//2
    if first == 1:
        tgt == tgt*7//8
        first = 0
    if solve(tgt):
        ok = tgt
    else:
        ng = tgt
print(ok)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
s = str(input())
maxlen = N//2

def solve(tgt):
    for i in range(N-tgt*2+1):
        if s[i:i+tgt] in s[i+tgt:]:
            return True
    return False

ng = maxlen + 1
ok = 0
first = 1
while ng-ok > 1:
    tgt = (ok+ng)//2
    if first == 1:
        tgt == 4
        first = 0
    if solve(tgt):
        ok = tgt
    else:
        ng = tgt
print(ok)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
s = str(input())
maxlen = N//2

def solve(tgt):
    for i in range(N-tgt*2+1):
        if s[i:i+tgt] in s[i+tgt:]:
            return True
    return False

ng = maxlen + 1
ok = 0
first = 1
while ng-ok > 1:
    tgt = (ok+ng)//2
    if first == 1:
        tgt == (ok+ng)//32
        first = 0
    if solve(tgt):
        ok = tgt
    else:
        ng = tgt
print(ok)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
s = str(input())
maxlen = N//2
appear = [[0]*(N+1) for _ in range(26)]
for i in range(N):
    appear[ord(s[i])-97][i]=1
for i in range(26):
    appear[i] = list(np.cumsum(appear[i]))

def solve(tgt):
    for i in range(N-tgt*2+1):
        for j in range(26):
            if appear[j][N]-appear[j][i+tgt] < appear[j][i+tgt]-appear[j][i]:
                continue
        if s[i:i+tgt] in s[i+tgt:]:
            return True

    return False

ng = maxlen + 1
ok = 0
while ng-ok > 1:
    tgt = (ok+ng)//2
    if solve(tgt):
        ok = tgt
    else:
        ng = tgt
print(ok)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
s = str(input())
maxlen = N//2

def solve(tgt):
    dic = {}
    for i in range(N-tgt*2+1):
        if s[i:i+tgt] in dic.keys():
            continue
        if s[i:i+tgt] in s[i+tgt:]:
            return True
    dic[s[i:i+tgt]] = 1
    return False

ng = maxlen + 1
ok = 0
while ng-ok > 1:
    tgt = (ok+ng)//2
    if solve(tgt):
        ok = tgt
    else:
        ng = tgt
print(ok)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
def Z_algo(S):
    n = len(S)
    LCP = [0]*n
    i = 1
    j = 0
    c = 0#最も末尾側までLCPを求めたインデックス
    for i in range(1, n):
        #i番目からのLCPが以前計算したcからのLCPに含まれている場合
        if i+LCP[i-c] < c+LCP[c]:
            LCP[i] = LCP[i-c]
        else:
            j = max(0, c+LCP[c]-i)
            while i+j < n and S[j] == S[i+j]: j+=1
            LCP[i] = j
            c = i
    for i in range(1,n):
        if i <= LCP[i]:
            LCP[i] = i
    return LCP
ans = 0
for i in range(N):
    T = S[i:]
    R = Z_algo(T)
    R.pop(0)
    R.append(0)
    ans = max(max(R),ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
l = N//2+1
f = 0
while f == 0:
    l -= 1
    if l == 0:
        f = 1
    for i in range(N-2*l+1):
        P = S[i:i+l]
        for j in range(l+i,N-l+1):
            Q = S[j:j+l]
            if P == Q:
                f = 1
print(l)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
i=0
ans=0
while i<len(s):
  for j in range(i+1,len(s)):
    k=0
    while i+k<j and j+k<len(s):
      if s[i+k]==s[j+k]:
        k+=1
      else:
        break
    if ans<k:
      ans=k
  i+=1
print(ans)

Submission status: Time Limit Exceeded

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

dp = [[0] * n for _ in range(n)]
for i in range(n-1, -1, -1):
    for j in range(n-1, -1, -1):
        if s[i] == s[j]:
            if j+1 <= n-1 and i+1 <= n-1:
                dp[i][j] = dp[i+1][j+1] + 1
            else:
                dp[i][j] = 1
                
for i in range(n):
    for j in range(n):
        dp[i][j] = min(abs(i-j), dp[i][j])

ans = 0
for i in range(n):
    ans = max(ans, max(dp[i]))
print(ans)

Submission status: Time Limit Exceeded

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

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

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

answer = 0
for i in range(N):
  for j in range(N):
    if T[i][j] and j - i >= T[i][j]:
      answer = max(answer, T[i][j])
print(answer)

Submission status: Time Limit Exceeded

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

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

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

answer = 0
for i in range(N):
  for j in range(N):
    if T[i][j] and j - i >= T[i][j]:
      answer = max(answer, T[i][j])
print(answer)

Submission status: Time Limit Exceeded

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


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


for i in range(1, N - 1):
    cnt = max(z_algo(S[i:])[1:])
    if cnt > answer:
        answer = cnt

print(answer)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

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

for i, j in combinations(range(N), 2):
    limit = j
    if S[i:i + answer] != S[j:j + answer]:
        continue
    cnt = answer
    i += answer
    j += answer
    if j > N - 1:
        break
    while S[i] == S[j]:
        cnt += 1
        i += 1
        j += 1
        if j > N - 1 or i == limit:
            break
    if answer < cnt:
        answer = cnt

print(answer)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

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

for i, j in combinations(range(N), 2):
    limit = j
    if j - i == 1:
        if answer > N - j:
            break
    cnt = 0
    while S[i] == S[j]:
        cnt += 1
        i += 1
        j += 1
        if j > N - 1 or i == limit:
            break
    if answer < cnt:
        answer = cnt

print(answer)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
def solve():
	for j in range(n-1, 0, -1):
		for i in range(n):
			if i+j+j >n:
				break
			if s[i:i+j] in s[i+j:]:
				print(j)
				return
	print(0)

solve()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
def solve():
	for j in range(n-1, 0, -1):
		for i in range(n):
			if i+j>=n:
				break
			if s[i:i+j] in s[i+j:]:
				print(j)
				return
	print(0)

solve()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
def solve():
	for j in range(n-1, 0, -1):
		for i in range(n):
			if s[i:i+j] in s[i+j:]:
				print(j)
				return
	print(0)

solve()

Submission status: Time Limit Exceeded

Solution code:
class RollingHash():
    def __init__(self, string):
        self.n = len(string)
        self.BASE = 1234
        self.MOD = (1 << 61) - 1
        self.hash = [0] * (self.n + 1)
        self.pow = [1] * (self.n + 1)
        
        for i, char in enumerate(string):
            self.hash[i+1] = (self.hash[i] + ord(char)) * self.BASE % self.MOD
            self.pow[i+1] = (self.pow[i] * self.BASE) % self.MOD
            
    def get_hash(self, l, r):
        res = (self.hash[r] - self.hash[l] * self.pow[r-l]) % self.MOD
        return res
      
    def get_lcp(self, l1, r1, l2, r2):
        ng = min(r1 - l1, r2 - l2) + 1
        ok = 0
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            if self.get_hash(l1, l1 + mid) == self.get_hash(l2, l2 + mid):
                ok = mid
            else:
                ng = mid
        return ok
        
n = int(input())
s = input()

rh = RollingHash(s)

ans = 0
for l1 in range(n):
    for l2 in range(l1+1, n):
        if l2 - l1 < ans or n - l2 < ans:
            continue
        tmp = rh.get_lcp(l1, l2, l2, n)
        ans = max(tmp, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class RollingHash():
    def __init__(self, string):
        self.n = len(string)
        self.BASE = 1234
        self.MOD = (1 << 61) - 1
        self.hash = [0] * (self.n + 1)
        self.pow = [1] * (self.n + 1)
        
        for i, char in enumerate(string):
            self.hash[i+1] = (self.hash[i] + ord(char)) * self.BASE % self.MOD
            self.pow[i+1] = (self.pow[i] * self.BASE) % self.MOD
            
    def get_hash(self, l, r):
        res = (self.hash[r] - self.hash[l] * self.pow[r-l] % self.MOD) % self.MOD
        return res

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

rh = RollingHash(s)

ans = 0
for length in range(n + 1):
    set_ = set()
    for l in range(n):
        # [l, l + length), [l + length, l + 2*length)
        if l + 2*length > n:
            break
        set_.add(rh.get_hash(l, l + length))
        tmp = rh.get_hash(l + length, l + 2*length)
        if tmp in set_:
            ans = length
            break

print(ans)