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:
import sys
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs= sys.stdin.buffer.readlines
#rstrip().decode('utf-8')

#import math
#import numpy as np
#import operator
#import bisect
#from heapq import heapify,heappop,heappush
#from math import gcd
#from fractions import gcd
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from itertools import accumulate
#from itertools import groupby
#from itertools import permutations
#from itertools import combinations
#from scipy.sparse import csr_matrix
#from scipy.sparse.csgraph import floyd_warshall
#from scipy.sparse.csgraph import csgraph_from_dense
#from scipy.sparse.csgraph import dijkstra
#sys.setrecursionlimit(10**7)

#map(int,input().split())

def main():
	n=int(input())
	s=input().rstrip().decode('utf-8')
	
	cnt=0
	ans=0
	l2=1
	for l1 in range(n-1):
		l2=l1+1
		while l2<n:
			if s[l1]!=s[l2]:
				l2+=1
			else:
				cnt=1
				x=l1+1
				y=l2+1
				while x<l2 and y<n:
					if s[x]==s[y]:
						cnt+=1
						x+=1
						y+=1
					else:
						break
				l2=y
				ans=max(ans,cnt)
	print(ans)


if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
S = input()[:-1]


def solve():
    dp = [[0]*(N+1) for _ in range(N+1)]
    for i, c in enumerate(S, 1):
        for j, k in enumerate(S, 1):
            if c == k:
                dp[i][j] = max(dp[i][j], dp[i-1][j-1]+1 if i +
                               dp[i-1][j-1] < j else 0)
    print(max([max(v) for v in dp]))


solve()

Submission status: Time Limit Exceeded

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

def z_algo(S):
    N = len(S)
    LCPs = [0]*N
    i = 1 ## iから何文字一致してるか調べる
    j = 0
    LCPs[0] = N
    while i < N:
        while i+j < N and S[j] == S[i+j]:
            j += 1
        if j == 0:
            i += 1
            continue
        LCPs[i] = j
        k = 1
        while k+i < N and k+LCPs[k] < j:
            LCPs[i+k] = LCPs[k]
            k += 1
        i += k
        j -= k
    return LCPs

def solve(N: int, S: str):
    answer = 0
    for i in range(N):
        LCP = z_algo(S[i:])
        for j in range(len(LCP)):
            # jの長さまでなら重ならない
            a = min(j,LCP[j])
            answer = max(answer,a)
    print(answer)
    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 is_len(x):
  for i in range(n-2*x+1):
    temp = s[i:i+x]
    if temp in s[i+x:]:
      return True
  return False

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

Submission status: Time Limit Exceeded

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

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

    d = dict()

    for length in range(N//2,0,-1):
        for j in range(0,N-length+1):
            if j == 0:
                s = S[:length]
            else:
                s = s[1:]+S[j+length-1]
            if d.get(s) != None:
                if d[s]+length <= j:
                    print(length)
                    return 
            else:
                d[s] = j

    print(0)
    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:
#!/usr/bin/env python3
import sys

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

    d = dict()

    for length in range(N//2,0,-1):
        for j in range(0,N-length+1):
            s = S[j:j+length]

            if d.get(s) != None:
                if d[s]+length <= j:
                    print(length)
                    return 
            else:
                d[s] = j

    print(0)
    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:
#!/usr/bin/env python3
import sys


def solve(N: int, S: str):
    for length in range(N,0,-1):
        for j in range(0,N-length+1):
            s = S[j:j+length]

            if s in S[:j] or s in S[j+length:]:
                print(length)
                return
    print(0)
    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()

checked = [[True for i in range(N)] for j in range(N)]
def ver(i, j, length):
    for f in range(length):
        if S[i+f] != S[j+f]: return False
    return True

def check(length):
    found = False
    for i in range(N):
        for j in range(i+length, N-length+1):
            if checked[i][j]:
                res = ver(i, j, length)
                if res:
                    found = True
                else:
                    checked[i][j] = False
    return found
            

for i in range(1, N):
    if not check(i):
        print(i - 1)
        break

Submission status: Time Limit Exceeded

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

def ver(i, j, length):
    for f in range(length):
        if S[i+f] != S[j+f]: return False
    return True

def check(length):
    for i in range(N):
        for j in range(i+length, N-length+1):
            if ver(i, j, length): return True
    return False

def binarySearch(lo, hi):
    if lo >= hi:
        return lo
    mid = lo + (hi - lo + 1) // 2
    if check(mid):
        return binarySearch(mid, hi)
    else:
        return binarySearch(lo, mid - 1)

print(binarySearch(0, N//2))

Submission status: Time Limit Exceeded

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

ans=0
for a in range(N-1):
    for b in range(a+1+ans,N-ans):
        cnt=0
        if S[a]==S[b]:
            #print(a,b)
            cnt+=1
            if a+ans<b and b+ans<N:
                if S[a+ans]==S[b+ans]:
                    
                    for c in range(1,min(b-a,N-b)):
                        #print(a+c,b+c)
                        if S[a+c]==S[b+c]:
                            cnt+=1
                            if ans<cnt:
                                ans=cnt
                        else:
                            break
                
print(ans)

Submission status: Time Limit Exceeded

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

ans=0
for a in range(N-1):
    for b in range(a+1,N-ans):
        cnt=0
        if S[a]==S[b]:
            #print(a,b)
            cnt+=1
            if a+ans<b and b+ans<N:
                if S[a+ans]==S[b+ans]:
                    
                    for c in range(1,min(b-a,N-b)):
                        #print(a+c,b+c)
                        if S[a+c]==S[b+c]:
                            cnt+=1
                            if ans<cnt:
                                ans=cnt
                        else:
                            break
                
print(ans)

Submission status: Time Limit Exceeded

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

ans=0
for a in range(N-1):
    for b in range(a+1,N):
        cnt=0
        if S[a]==S[b]:
            #print(a,b)
            cnt+=1
            for c in range(1,min(b-a,N-b)):
                #print(a+c,b+c)
                if S[a+c]==S[b+c]:
                    cnt+=1
                    if ans<cnt:
                        ans=cnt
                else:
                    break
                        
print(ans)

Submission status: Time Limit Exceeded

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

res = 0;
dp = [[0]*(N+1) for _ in range(N+1)]

for i in range(N-1, -1, -1):
  for j in range(N-1, i, -1):
    if S[i] == S[j]:
      dp[i][j] = max(dp[i][j], dp[i+1][j+1]+1);
    res = max(res, min(dp[i][j], j-i));
print(res)

Submission status: Time Limit Exceeded

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

dp = [[0 for j in range(n+1)] for i in range(n+1)]
dp[0][0] = 0

for i in range(n):
    for j in range(1,n):
        if s[i] == s[j] and i+dp[i][j]+1 <= j:
            dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j],dp[i][j]+1)
        else:
            dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])

print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
class SuffixArray(object):
    def __init__(self, s):
        self.__s = s
        self.__n = len(s)
        self.__suffix_array()
        self.__lcp_array()
        self.__sparse_table()

    def __suffix_array(self):
        s = self.__s
        n = self.__n
        sa = list(range(n))
        rank = [ord(s[i]) for i in range(n)]
        tmp = [0]*n
        k = 1
        cmp_key = lambda i: (rank[i], rank[i+k] if i+k < n else -1)
        while k <= n:
            sa.sort(key=cmp_key)
            tmp[sa[0]] = 0
            for i in range(1, n):
                tmp[sa[i]] = tmp[sa[i-1]] + (cmp_key(sa[i-1]) < cmp_key(sa[i]))
            rank = tmp[:]
            k<<=1
        self.__sa = sa
        self.__rank = rank

    def __lcp_array(self):
        s = self.__s
        n = self.__n
        sa = self.__sa
        rank = self.__rank
        lcp = [0]*n
        h = 0
        for i in range(n):
            j = sa[rank[i]-1]
            if h>0:
                h -= 1
            if rank[i]==0:
                continue
            while j+h<n and i+h<n and s[j+h]==s[i+h]:
                h += 1
            lcp[rank[i]] = h
        self.__lcp = lcp

    def __sparse_table(self):
        n = self.__n
        logn = max(0, (n-1).bit_length())
        table = [[0]*n for _ in range(logn)]
        table[0] = self.__lcp[:]
        # 直積（デカルト積）[a,b,c] [x,y,z] = (a,x),(a,y),(a,z),(b,),(c,)....
        from itertools import product
        for i, k in product(range(1, logn), range(n)):
            if k+(1<<(i-1)) >= n:
                table[i][k] = table[i-1][k]
            else:
                table[i][k] = min(table[i-1][k], table[i-1][k+(1<<(i-1))])
        self.__table = table

    def lcp(self, a, b):
        if a==b:
            return self.__n-a
        l, r = self.__rank[a], self.__rank[b]
        l = min(l, r)+1
        r = max(l, r)+1
        i = max(0, (r-l-1).bit_length()-1)
        table = self.__table
        return min(table[i][l], table[i][r-(1<<i)])

def main():
  N = int(input())
  S = input()
  sa = SuffixArray(S)
  ans = 0
  for i in range(N):
    for j in range(i+1, N):
      ans = max(min(j-i, sa.lcp(i,j)), ans)
  print(ans)
  
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
class RollingHash:
    def __init__(self, s, base, mod):
        self.base = base
        self.mod = mod

        self.hash = [0]
        self.power = [1]
        for c in s:
            self.hash.append((self.hash[-1] * base + ord(c)) % mod)
            self.power.append(self.power[-1] * base % mod)

    def get(self, left, right):
        h = self.hash[right] - self.hash[left] * self.power[right - left]
        return (h + self.mod) % self.mod


n = int(input())
s = input().rstrip()
rh = RollingHash(s, base=26, mod=2**50 + 1)


def check(diff):
    d = {}
    for i in range(n - diff + 1):
        h = rh.get(i, i + diff)
        if h in d.keys():
            if abs(d[h] - i) >= diff:
                return True
        else:
            d[h] = i
    return False


lo = 0
hi = n // 2 + 1
while lo + 1 < hi:
    mid = (lo + hi) // 2
    if check(mid):
        lo = mid
    else:
        hi = mid
print(lo)

Submission status: Time Limit Exceeded

Solution code:
class RollingHash:
    def __init__(self, s, base, mod):
        self.base = base
        self.mod = mod

        self.hash = [0]
        self.power = [1]
        for c in s:
            self.hash.append((self.hash[-1] * base + ord(c)) % mod)
            self.power.append(self.power[-1] * base % mod)

    def get(self, left, right):
        h = self.hash[right] - self.hash[left] * self.power[right - left]
        return (h + self.mod) % self.mod


n = int(input())
s = input().rstrip()
rh = RollingHash(s, base=10**4 + 7, mod=2**61 - 1)


def check(diff):
    d = {}
    for i in range(n - diff + 1):
        h = rh.get(i, i + diff)
        if h in d.keys():
            if abs(d[h] - i) >= diff:
                return True
        else:
            d[h] = i
    return False


lo = 0
hi = n // 2 + 1
while lo + 1 < hi:
    mid = (lo + hi) // 2
    if check(mid):
        lo = mid
    else:
        hi = mid
print(lo)

Submission status: Time Limit Exceeded

Solution code:
class RollingHashSingle:
    def __init__(self, s, base, mod):
        self.base = base
        self.mod = mod

        self.hash = [0]
        self.power = [1]
        for c in s:
            self.hash.append((self.hash[-1] * base + ord(c)) % mod)
            self.power.append(self.power[-1] * base % mod)

    def get(self, left, right):
        h = self.hash[right] - self.hash[left] * self.power[right - left]
        return (h + self.mod) % self.mod


class RollingHash:
    def __init__(self,
                 s,
                 base=(10**4 + 7, 10**4 + 9),
                 mod=(10**9 + 7, 10**9 + 9)):
        if isinstance(base, int):
            assert isinstance(mod, int)
            self.base = (base, )
            self.mod = (mod, )
        elif isinstance(base, tuple):
            assert isinstance(mod, tuple)
            assert len(base) == len(mod)
            self.base = base
            self.mod = mod
        else:
            raise ValueError()

        self._rh = [
            RollingHashSingle(s, base, mod)
            for base, mod in zip(self.base, self.mod)
        ]

    def get(self, left, right):
        return tuple(rh.get(left, right) for rh in self._rh)


n = int(input())
s = input().rstrip()
rh = RollingHash(s, base=10**4 + 7, mod=2**61 - 1)


def check(diff):
    d = {}
    for i in range(n - diff + 1):
        h = rh.get(i, i + diff)
        if h in d.keys():
            if abs(d[h] - i) >= diff:
                return True
        else:
            d[h] = i
    return False


lo = 0
hi = n // 2 + 1
while lo + 1 < hi:
    mid = (lo + hi) // 2
    if check(mid):
        lo = mid
    else:
        hi = mid
print(lo)

Submission status: Time Limit Exceeded

Solution code:
class RollingHashSingle:
    def __init__(self, s, base, mod):
        self.base = base
        self.mod = mod

        self.hash = [0]
        self.power = [1]
        for c in s:
            self.hash.append((self.hash[-1] * base + ord(c)) % mod)
            self.power.append(self.power[-1] * base % mod)

    def get(self, left, right):
        h = self.hash[right] - self.hash[left] * self.power[right - left]
        return (h + self.mod) % self.mod


class RollingHash:
    def __init__(self,
                 s,
                 base=(10**4 + 7, 10**4 + 9),
                 mod=(10**9 + 7, 10**9 + 9)):
        if isinstance(base, int):
            assert isinstance(mod, int)
            self.base = (base, )
            self.mod = (mod, )
        elif isinstance(base, tuple):
            assert isinstance(mod, tuple)
            assert len(base) == len(mod)
            self.base = base
            self.mod = mod
        else:
            raise ValueError()

        self._rh = [
            RollingHashSingle(s, base, mod)
            for base, mod in zip(self.base, self.mod)
        ]

    def get(self, left, right):
        return tuple(rh.get(left, right) for rh in self._rh)


n = int(input())
s = input().rstrip()
rh = RollingHash(s)


def check(diff):
    d = {}
    for i in range(n - diff + 1):
        h = rh.get(i, i + diff)
        if h in d.keys():
            if abs(d[h] - i) >= diff:
                return True
        else:
            d[h] = i
    return False


lo = 0
hi = n // 2 + 1
while lo + 1 < hi:
    mid = (lo + hi) // 2
    if check(mid):
        lo = mid
    else:
        hi = mid
print(lo)

Submission status: Time Limit Exceeded

Solution code:
def create_z_array(s):
    n = len(s)
    z_array = [0] * n
    left = 0
    right = 0
    for i in range(1, n):
        if i > right:
            left, right = i, i
            while right < n and s[right - left] == s[right]:
                right += 1
            z_array[i] = right - left
            right -= 1
        else:
            k = i - left
            if z_array[k] < right - i + 1:
                z_array[i] = z_array[k]
            else:
                left = i
                while right < n and s[right - left] == s[right]:
                    right += 1
                z_array[i] = right - left
                right -= 1
    return z_array


n = int(input())
s = input().rstrip()
res = 0
for i in range(n):
    z_array = create_z_array(s[i:])
    for j in range(1, len(z_array)):
        res = max(res, min(j, z_array[j]))
print(res)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    s = input()
    dp = [[0 for i in range(n+1)] for j in range(n+1)]
    
    for i in range(n-1,-1,-1):#後ろから
        for j in range(i-1,-1,-1):
            if s[i]!=s[j]:
              	dp[i][j] = 0#continueではない
        	    
            else:
              	dp[i][j] = dp[i+1][j+1] +1
              	"""
              	これでは結局ループしている
                cnt = 0
                for k in range(min(n-j,j-i)):
                    if s[i+k] ==s[j+k]:
                        cnt += 1
                    else:
                        break
                dp[i][j] = cnt
             	"""
    mx = 0
    #print(dp)
    for i in range(n):
      	for j in range(i):###
        	mx = max(mx,min(i-j,dp[i][j]))###
    print(mx)

if __name__ =='__main__':main()

Submission status: Time Limit Exceeded

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

memo1 = set()
memo2 = set()
ans = 0

for s in S:
    memo3 = set()
    memo3.add('')
    for sub in memo2:
        newsub = sub + s
        if newsub  in memo1:
            ans = max(ans,len(sub+s))
        else:
            memo1.add(newsub)
        
        memo3.add(newsub)
    
    memo2 = memo3

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# ローリングハッシュ
class RollingHash() :
    def __init__(self, S, base=26, mod=2**61-1) :
        hash = [0]
        pow = [1]
        for s in S :
            hash.append((hash[-1] * base + ord(s)) % mod)
            pow.append(pow[-1] * base % mod)

        self.hash = hash
        self.pow = pow
        self.mod = mod
        
    def get(self, l, r) :
        return (self.hash[r+1] - self.hash[l] * self.pow[r+1-l]) % self.mod
        
N = int(input())
S = input()

RH = RollingHash(S)

def solve() :
    for k in range(N // 2, 0, -1) :
        for i in range(N - 2 * k + 1) :
            for j in range(i + k, N - k + 1) :
                if RH.get(i, i+k-1) == RH.get(j, j+k-1) :
                    return k
    return 0
print(solve())

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = str(input())
ans = 0
cnt = 0
for i in range(n-1):
  start = i
  for j in range(i+1,n):
    if s[start] == s[j]:
      cnt += 1
      start += 1
      if start + cnt - 1 == j:
        ans = max(ans,cnt)
        cnt = 0
        start = i
    else:
      ans = max(ans,cnt)
      cnt = 0
      start = i
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

letters_dict = {}

for i in range(N):
    for j in range(i + 1, N):
        key = S[i:j + 1]
        if key not in letters_dict:
            letters_dict[key] = i
        else:
            ans = max(ans, min(len(key), i - letters_dict[key]))

print(ans)

Submission status: Time Limit Exceeded

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

for i in range(N):
    for j in range(i, N):
        cand = S[i:j]
        if S.find(cand, j) != -1:
            ans = max(ans, j-i)

print(ans)

Submission status: Time Limit Exceeded

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

for l in reversed(range(1,N//2+1)):
    for i in range(N-2*l+1):
        for j in range(i+l,N-l+1):
            if S[i:i+l] == S[j:j+l]:
                print(l)
                exit()

print(0)

Submission status: Time Limit Exceeded

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


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


def solve(N: int, S: str):
    ans = 0
    for i in range(N-1):
        ans = max(z_algo(S[i:])[(N-i+1)//2:] + [ans])
    print(ans)
    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:
def z_algolithm(S, x):
    length = len(S) - x
    A = [0]*length
    B = [0]
    i = 1; j = 0
    while i < length:
        while i+j < length and S[x+j] == S[x+i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        B.append(min(j, i))
        k = 1
        while k < length - i  and k + A[k] < j :
            A[i+k] = A[k]
            k += 1
        i += k
        j -= k
    ans = max(B)
    return ans

N = int(input())
S = input()
ans = max([z_algolithm(S, x) for x in range(N)])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def z_algolithm(S):
    length = len(S)
    A = [0]*length
    i = 1; j = 0
    A[0] = length
    while i < length:
        while i+j < length and S[j] == S[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while k < length - i  and k + A[k] < j :
            A[i+k] = A[k]
            k += 1
        i += k
        j -= k
    ans = 0
    for a in A:
        if a <= length//2:
            ans = max(ans, a)
    return ans

N = int(input())
S = input()
ans = max([z_algolithm(S[x:]) for x in range(N)])
print(ans)

Submission status: Time Limit Exceeded

Solution code:

def z_arr(s):
    """An advanced computation of Z-values of a string."""
    # From https://ivanyu.me/blog/2013/10/15/z-algorithm/

    Z = [0] * len(s)
    Z[0] = len(s)

    rt = 0
    lt = 0

    for k in range(1, len(s)):
        if k > rt:
            # If k is outside the current Z-box, do naive computation.
            n = 0
            while n + k < len(s) and s[n] == s[n+k]:
                n += 1
            Z[k] = n
            if n > 0:
                lt = k
                rt = k+n-1
        else:
            # If k is inside the current Z-box, consider two cases.

            p = k - lt  # Pair index.
            right_part_len = rt - k + 1

            if Z[p] < right_part_len:
                Z[k] = Z[p]
            else:
                i = rt + 1
                while i < len(s) and s[i] == s[i - k]:
                    i += 1
                Z[k] = i - k

                lt = k
                rt = i - 1
    return Z
n = int(input())
s = input()
m = 0
for i in range(n-1):
    z = z_arr(s[i:])
    t = z[-(len(s[i:])//2):]
    m = max(m, max(t))
print(m)

Submission status: Time Limit Exceeded

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

ans = 0

for cut in range(1, N):
    if ans >= N - cut:
        break
    x, y = S[:cut], S[cut:]

    for i in range(cut-ans):
        if x[i:] in y:
            ans = cut - i
            break

print(ans)

Submission status: Time Limit Exceeded

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

left = 0
right = 1
max_length = 0

while left < N:
    if right - left > N - right:
        break
    serch_str = S[left:right]
    left_str = S[right:]
    if serch_str in left_str:
        max_length = max(max_length, len(serch_str))
        right += 1
    else:
        left += 1
        right = left + 1

print(max_length)

Submission status: Time Limit Exceeded

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

left = 0
right = 1
max_length = 0

while left < N:
    serch_str = S[left:right]
    left_str = S[right:]
    if serch_str in left_str:
        max_length = max(max_length, len(serch_str))
        right += 1
    else:
        left += 1
        right = left + 1

print(max_length)

Submission status: Time Limit Exceeded

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

left = 0
right = 1
max_length = 0

while left < N:
    serch_str = S[left:right]
    left_str = S[right:]
    if serch_str in left_str:
        max_length = max(max_length, len(serch_str))
        right += 1
    else:
        left += 1
        right = left + 1

print(max_length)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
ans = 0
for i in range(1, N//2+1):
    for j in range(N-2*i+1):
        #j~j+i, k~k+i(k>=j+i)
        one = S[j:j+i]
        if one in S[j+i:]:
            ans = i
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
input()
s=input()
max_len = 0
len_s = len(s)
for i in range(len_s-1):
    if max_len > (len_s-i):
        break
    for j in range(len_s):
        if j-i < max_len:
           continue
        if j-i > len_s - j:
            break
        if s[i:j] not in s[j:]:
            break
        max_len = max(max_len, len(s[i:j]))

print(max_len)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def Z(s):
    """
    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
        elif z[i-L]<R-i: # 過去の結果が全て使える
            z[i]=z[i-L]
        else: # 過去の結果が一部使える
            L=i
            while(R<n and s[R-L]==s[R]): R+=1
            z[i]=R-L
    return z
def resolve():
    n=int(input())
    s=input()
    ans=0
    for i in range(n):
        z=Z(s[i:])
        k=len(z) # k=n-i
        for j in range(k):
            ans=max(ans,min(j,z[j]))
    print(ans)
resolve()

Submission status: Time Limit Exceeded

Solution code:
def z_argorithm(s):
    s_len=len(s)
    a=[0]*s_len
    c=0
    for i in range(1,s_len):
        if i+a[i-c] < c+a[c]:
            a[i]=a[i-c]
        else:
            j=max(0,c+a[c]-i)
            while i+j<s_len and s[j]==s[j+i]:
                j += 1
            a[i]=j
            c=i
    return a
def main():
    n=int(input())
    s=input()
    ans = 0
    for i in range(n-1):
        a = z_argorithm(s[i:])
        A=len(a)
        for i in range(A):
            ans=max(ans,min(i,a[i]))
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def z_argorithm(s):
    s_len=len(s)
    a=[0]*s_len
    i=1
    j=0
    while i<s_len:
        while i+j<s_len and s[j]==s[i+j]:
            j+= 1
        a[i]=j
        k=1
        if j==0:
            i += 1
            continue
        while i+k<s_len and k+a[k]<j:
            a[i+k]=a[k]
            k+=1

        i +=k
        j -=k
    return a
def main():
    n=int(input())
    s=input()
    ans = 0
    for i in range(n-1):
        a = z_argorithm(s[i:])
        for i in range(len(a)):
            if ans <min(i,a[i]):
                ans = min(i,a[i])
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def z_argorithm(s):
    s_len=len(s)
    a=[0]*s_len
    ans = 0
    i=1
    j=0
    while i<s_len:
        while i+j<s_len and s[j]==s[i+j]:
            j+= 1
        a[i]=j
        if ans < min(i,j):
            ans = min(i,j)
        k=1
        if j==0:
            i += 1
            continue
        while i+k<s_len and k+a[k]<j:
            a[i+k]=a[k]
            if ans < min(i+k,a[k]):
                ans = min(i+l,a[k])
            k+=1

        i +=k
        j -=k
    return ans
def main():
    n=int(input())
    s=input()
    ans = 0
    for i in range(n-1):
        a = z_argorithm(s[i:])
        if ans < a:
            ans = a
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def z_argorithm(s):
    s_len=len(s)
    a=[0]*s_len
    a_re=[0]*s_len
    a[0]=s_len
    i=1
    j=0
    while i<s_len:
        while i+j<s_len and s[j]==s[i+j]:
            j+= 1
        a[i]=j
        a_re[i]=min(i,j)
        k=1
        if j==0:
            i += 1
            continue
        while i+k<s_len and k+a[k]<j:
            a[i+k]=a[k]
            a_re[i+k]=min(a[k],i+k)
            k+=1

        i +=k
        j -=k
    return a_re
def main():
    n=int(input())
    s=input()
    ans = 0
    for i in range(n-1):
        a=z_argorithm(s[i:])
        max_a=max(a[1:])
        if max_a>ans:
            ans = max_a
    print(ans)

if __name__ == '__main__':
    main()