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

Submission status: Time Limit Exceeded

Solution code:
class RollingHash():
    def __init__(self, string):
        self.n = len(string)
        self.BASE = 1007
        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] * self.BASE + ord(char)) % 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
      

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)

Submission status: Time Limit Exceeded

Solution code:
# import numpy as np

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

# dp = np.zeros([n+1, n+1])
dp = [0] * (n+1)

for dif in range(1,n):
    count = 0
    t_max = 0
    for l1_r in range(0, n-dif):
        if(s[l1_r] == s[l1_r + dif]):
            count += 1
            t_max = max(count, t_max)
            if( count == dif):
                dp[dif] = count
                break
        else:
            count = 0
    dp[dif] = t_max

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

dp = np.zeros([n+1, n+1])

for l1_r in range(1,n):
    for l2_r in range(l1_r+1, n+1):
        if(s[l1_r-1] == s[l2_r-1]):
            temp = dp[l1_r-1][l2_r-1]
            if( (l2_r - l1_r) > temp):
                  temp += 1
        else:
            temp = 0
        dp[l1_r][l2_r] = temp


print(int(dp.max()))

Submission status: Time Limit Exceeded

Solution code:
def main():
    class rolling_hash():
        def __init__(self, sequence, char_list=None):
            self.sequence = sequence  # 文字列
            self.seq_size = len(self.sequence)  # 文字列の長さ
            self.mod = 2**61-1  # mod
            if char_list is None:  # 使われている文字のリスト
                self.char_list = "abcdefghijklmnopqrstuvwxyz"
            else:
                self.char_list = char_list
            self.base = len(self.char_list)+1  # 文字の種類数
            self.char_dict = {j: i+1 for i,
                              j in enumerate(self.char_list)}  # 文字と数値の対応表
            self.Hash_0start = [0]*(self.seq_size+1)  # 先頭からi-1文字目までのハッシュ値
            for i in range(self.seq_size):
                self.Hash_0start[i+1] = self.Hash_0start[i] + \
                    self.char_dict[self.sequence[i]] * \
                    pow(self.base, i, self.mod)

        def calc_hash(self, l, r):  # l文字目からr-1文字目までのハッシュ値
            return ((self.Hash_0start[r] - self.Hash_0start[l])
                    * pow(self.base, l*(self.mod-2), self.mod)) % self.mod

    n = int(input())
    s = input()
    h_s = rolling_hash(s)

    def value(num):
        h_dict = {}
        for i in range(len(s)-num+1):
            j = h_s.calc_hash(i, i+num)
            if j not in h_dict.keys():
                h_dict[j] = i
            else:
                if i-h_dict[j] >= num:
                    return True
        return False

    def b_search(a, b, value):
        while a+1 < b:
            med = (a+b)//2
            if value(med):
                a = med
            else:
                b = med-1
        if a == b:
            return a
        elif a+1 == b:
            if value(b):
                return b
            else:
                return a

    print(b_search(0, len(s), value))


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    S = input()
    m = 0
    for i in range(N-1):
        A = z_algo(S[i:])
        m = max(m, max(min(i,v) for i, v in enumerate(A)))
    return m

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

Submission status: Time Limit Exceeded

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

def getZArray(Ss):
    lenS = len(Ss)
    As = [lenS] * lenS
    i, j = 1, 0
    while i < lenS:
        while i+j < lenS and Ss[j] == Ss[i+j]:
            j += 1
        As[i] = j
        if j == 0:
            i += 1
        else:
            k = 1
            while i+k < lenS and k+As[k] < j:
                As[i+k] = As[k]
                k += 1
            i += k
            j -= k
    return As

ans = 0
for i in range(N):
    ZArray = getZArray(Ss[i:])
    for i, Z in enumerate(ZArray):
        L = min(Z, i)
        ans = max(ans, L)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
d=[[0]*n for i in range(n)]
maxd=0
for i in range(n-maxd-1):
  for j in range(i+1,n):
    if s[i]==s[j]:
      if i==0:
        d[i][j]=1
        continue
      elif i+d[i-1][j-1]<j:
        d[i][j]=d[i-1][j-1]+1
    maxd=max(maxd,d[i][j])
print(maxd)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(N):
    for j in range((N + i) // 2, i, -1):
        if S[i:j] in S[j:]:
            ans = max(ans, j - i)
            break

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 + 1, N):
        if (j - i) <= (N - j):
            l1 = S[i:j]
            l2 = S[j:]
            if l1 in l2:
                ans = max(ans, len(l1))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
d=[[0]*n for i in range(n)]
maxd=0
for i in range(n-1):
  for j in range(i+1,n):
    if s[i]==s[j]:
      if i==0:
        d[i][j]=1
        continue
      elif i+d[i-1][j-1]<j:
        d[i][j]=d[i-1][j-1]+1
    maxd=max(maxd,d[i][j])
print(maxd)

Submission status: Time Limit Exceeded

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


def lcs(s1, s2):
    I = len(s1)
    J = len(s2)
    dp = [[0] * (J + 1) for _ in range(I + 1)]

    for i in range(I):
        for j in range(J):
            if s1[i] == s2[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])

    return dp[I][J]


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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
ma=0
for i in range(int(n//2)+1):
    for L in range(1,int(n//2)+1):
        moji=s[i:i+L]
        num=s[i+L:].count(moji)
        if num>=1:
            ma=max(ma,len(moji))
print(ma)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import numpy as np
    n = int(input())
    alphabet = "abcdefghijklmnopqrstuvwxyz"
    d_alpha = {j: i for i, j in enumerate(alphabet)}
    s = input()
    s = np.array([d_alpha[i] for i in s], dtype=np.int8)
    m = 0
    for i in range(1, n):
        cnt_m = 0
        cnt = 0
        t = (s[:n-i] == s[i:])
        for j in t:
            if j:
                cnt += 1
            else:
                cnt_m = max(cnt, cnt_m)
                cnt = 0
        cnt_m = min(max(cnt, cnt_m), i)
        m = max(cnt_m, m)
    print(m)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import numpy as np
    n = int(input())
    alphabet = "abcdefghijklmnopqrstuvwxyz"
    d_alpha = {j: i for i, j in enumerate(alphabet)}
    s = input()
    s = np.array([d_alpha[i] for i in s], dtype=np.int8)
    m = 0
    for i in range(1, n):
        cnt_m = 0
        cnt = 0
        t = (s[:n-i] == s[i:])
        for j in t:
            if j:
                cnt = min(cnt+1, i)
            else:
                cnt_m = max(cnt, cnt_m)
                cnt = 0
        m = max(cnt, cnt_m, m)
    print(m)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import numpy as np
    n = int(input())
    alphabet = "abcdefghijklmnopqrstuvwxyz"
    d_alpha = {j: i for i, j in enumerate(alphabet)}
    s = input()
    s = np.array([d_alpha[i] for i in s], dtype=np.int8)
    m = 0
    for i in range(1, n):
        cnt_m = 0
        cnt = 0
        for j, k in zip(s[:n-i], s[i:]):
            if j == k:
                cnt = min(cnt+1, i)
            else:
                cnt_m = max(cnt, cnt_m)
                cnt = 0
        m = max(cnt, cnt_m, m)
    print(m)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    alphabet = "abcdefghijklmnopqrstuvwxyz"
    d_alpha = {j: i for i, j in enumerate(alphabet)}
    s = input()
    s = [d_alpha[i] for i in s]
    m = 0
    for i in range(1, n):
        cnt_m = 0
        cnt = 0
        for j in range(i, n):
            if s[j-i] == s[j]:
                cnt = min(cnt+1, i)
            else:
                cnt_m = max(cnt, cnt_m)
                cnt = 0
        m = max(cnt, cnt_m, m)
    print(m)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    s = input()
    m = 0
    for i in range(1, n):
        cnt_m = 0
        cnt = 0
        for j in range(i, n):
            if s[j-i] == s[j]:
                cnt = min(cnt+1, i)
            else:
                cnt_m = max(cnt, cnt_m)
                cnt = 0
        m = max(cnt, cnt_m, m)
    print(m)


main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
ans = 0
for i in range(1, N+1):
    x = 0
    for s1, s2 in zip(S, S[i:]):
        if s1 == s2 and i > x:
            x += 1
        else:
            x = 0
        ans = max(ans, x)
print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(N):
  j_start = ans + 1
  j_end = (N - i) // 2 + 1
  for j in range(j_start, j_end):
    base = S[i:i+j]
    if base in S[i+j:]:
      ans = max(ans, j)


print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(N):
  j_start = ans + 1
  j_end = N - i
  for j in range(j_start, j_end):
    base = S[i:i+j]
    if base in S[i+j:]:
      ans = max(ans, j)


print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
i = 0
j = 1
c = 1
while j <= N-c:
    c = 1
    for k in range(j, N):
        cnt = 0
        while k+cnt < N and i+cnt < j and S[i+cnt] == S[k+cnt]:
            cnt += 1
        c = max(c, cnt)
    if j-i > c:
        i += 1
        j = i+c
    else:
        j += 1
    ans = max(c, ans)
    
if N <= 26:
    L = []
    for i in range(N):
        L.append(S[i])
    L = set(L)
    if len(L) == N:
        ans = 0
    
print(ans)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  input = sys.stdin.readline

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

  ans = 0
  for i in range(N-1):
    for j in range(i+1,N):
      l = 0
      while(i+l < j and j+l < N and S[i+l] == S[j+l]):
        l += 1
      ans = max(l,ans)
  print(ans)

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(N-1):
  for j in range(i+1,N):
    l = 0
    while(i+l < j and j+l < N and S[i+l] == S[j+l]):
      l += 1
    ans = max(l,ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
N = int(input())
S = input()
ans = 0
table = collections.defaultdict(list)
for i in range(1, N//2 + 1):
    for j in range(N-i+1):
        table[S[j:j+i]].append(j)

ans = 0
for x in table:
    n = len(x)
    if n <= ans:
        continue
    if table[x][-1] - table[x][0] >= n:
        ans = max(ans, n)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
N = int(input())
S = input()
ans = 0
table = collections.defaultdict(list)
for i in range(1, N//2 + 1):
    for j in range(N-i+1):
        table[S[j:j+i]].append(j)
ans = 0
for x in table:
    n = len(x)
    if table[x][-1] - table[x][0] >= n:
        ans = max(ans, n)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
sign=0
ans=0
for i in range(n-1):
    for j in range(i+1,n):
        if s[j]==s[i+sign] and i+2*sign<j:
            sign+=1

        else:
            ans=max(sign,ans)
            sign=0
ans=max(sign,ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
res = 0
twices = list()
for i in range(N-1):
    for j in range(i + 1, N):
        t = ''
        si, sj = i, j
        length = 0
        while sj < N and S[si] == S[sj] and i+length<=j:
            t = t + S[si]
            si += 1
            sj += 1
            length += 1
        if i + length <= j:
            res = max(res, length)
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)]

for i in range(n)[::-1]:
    for j in range(n)[::-1]:
        dp[i][j]=dp[i+1][j+1]+1 if s[i]==s[j] else 0

res=0

for i in range(n):
    for j in range(n):
        if j<=i:continue
        else:
            res=max(res,min(j-i,dp[i][j]))

print(res)

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

class RollingHash(object):
    __base1=1007; __mod1=10**9+9
    __base2=1009; __mod2=10**9+7

    def __init__(self,s):
        self.__s=s; self.__n=len(s)
        b1=self.__base1; m1=self.__mod1
        b2=self.__base2; m2=self.__mod2
        H1,H2=[0]*(self.__n+1),[0]*(self.__n+1)
        P1,P2=[1]*(self.__n+1),[1]*(self.__n+1)
        for i in range(self.__n):
            H1[i+1]=(H1[i]*b1+ord(s[i]))%m1
            H2[i+1]=(H2[i]*b2+ord(s[i]))%m2
            P1[i+1]=P1[i]*b1%m1
            P2[i+1]=P2[i]*b2%m2
        self.__H1=H1; self.__H2=H2
        self.__P1=P1; self.__P2=P2

    def __getitem__(self,x):
        if(isinstance(x,int)): x=slice(x,x+1)
        assert(isinstance(x,slice) and ((x.step is None) or (x.step==1)))
        l=x.start; r=x.stop;
        assert(l<=r)
        return ((self.__H1[r]-self.__P1[r-l]*self.__H1[l]%self.__mod1)%self.__mod1,
                (self.__H2[r]-self.__P2[r-l]*self.__H2[l]%self.__mod2)%self.__mod2)

def bisection(l,r,f,left=True,discrete=True):
    eps=1 if discrete else 10**-12
    if((not left)^f(r)): return r if left else r+1
    elif(left^f(l)): return l-1 if left else l
    while(r-l>eps):
        h=(l+r)//2 if discrete else (l+r)/2
        if((not left)^f(h)): l=h
        else: r=h
    return (l+r)/2 if not discrete else l if left else r

def resolve():
    n=int(input())
    S=input()
    rh=RollingHash(S)

    from collections import defaultdict
    def check(k):
        D=defaultdict(lambda :-1)
        for i in range(n-k+1):
            hash=rh[i:i+k]
            if(D[hash]!=-1):
                if(i-D[hash]>=k): return True
            else:
                D[hash]=i
        return False

    for k in range(n,-1,-1):
        if(check(k)):
            print(k)
            return
resolve()

Submission status: Time Limit Exceeded

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

import collections
dp = collections.defaultdict(int)
for i in range(n-1, -1, -1):
    for j in range(i+1, n):
        if s[i] == s[j]:
            dp[i,j] = dp[i+1, j+1] + (j - i > dp[i+1, j+1])
try:
    print(max(dp.values()))
except:
    print(0)

Submission status: Time Limit Exceeded

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

dp = [[0]*(n+1) for i in range(n+1)]
#dp[n-1][n-1] = 1

for i in reversed(range(n)):
  for j in reversed(range(n)):
    if s[i] == s[j]:
      dp[i][j] = dp[i+1][j+1]+1

#print(dp)

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

Submission status: Time Limit Exceeded

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

ng = N//2 + 1
ok = 0

def isok(length):
    if length == 0:
        return True
    
    for i in range(N-length*2+1):
        for j in range(i+length,N-length+1):
            if S[i:i+length] == S[j:j+length]:
                return True
    return False

while abs(ok-ng) > 1:
    mid = (ok+ng) // 2
    if isok(mid):
        ok = mid
    else:
        ng = mid
        
print(ok)

Submission status: Time Limit Exceeded

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

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

#処理内容
def main():
	N = int(input())
	s = input()
	ans = 0
	for l in range(N):
		S = s[l:]
		#print(S)
		A = [0] * (N - l)
		A[0] = N - l

		i = 1
		j = 0
		while i < N - l:
			while i + j < N - l and S[j] == S[i + j]:
				j += 1
			if j == 0:
				i += 1
				continue
			A[i] = j
			k = 1
			while i + k < N - l and k + A[k] < j:
				A[i + k] = A[k]
				k += 1
			i += k
			j -= k
		#print(A)

		for x in range(N - l):
			if A[x] <= x:
				ans = max(ans, A[x])
	print(ans)

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
# 2019-11-18 17:34:23(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# import re
# import heapq
# import array
# from scipy.misc import comb # (default: exact=False)
# import numpy as np 



def main():
    n, s = sys.stdin.read().split()
    n = int(n)
    
    # a = [0 for _ in range(n)]
    # i = j = 0
    # while i < n:
    #     while i+j < n and s[j] == s[i+j]: 
    #         j += 1
    #     a[i] = j
    #     if j == 0:
    #         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

    # print(max(l for l in a if l <= n // 2))
    # print(a)
    
    ma = 0
    for k in range(n):
        sub = s[k:]
        a = [0 for _ in range(len(sub))]
        i, j = 1, 0
        while i < len(sub):
            while i+j < len(sub) and sub[j] == sub[i+j]:
                j += 1
                if j == len(sub) // 2:
                    break
            a[i] = j
            if j == 0:
                i += 1
                continue
            k = 1
            while i+k < len(sub) and k+a[k] < j:
                a[i+k] = a[k]
                k += 1
            i += k
            j -= k
        ma = max(ma, max(a))
    print(ma)

    # a = [0 for _ in range(n)]
    # a[0] = n 
    # c = 0
    # for i in range(1, n):
    #     if i+a[i-c] < c+a[c]:
    #         a[i] = a[i-c]
    #     else:
    #         j = max(0, c+a[c]-i)
    #         while i+j < n and s[s] == s[i+j]:
    #             j += 1
    #         a[i] = j
    
    # print(a)

    # zz = [[0 for _ in range(n)] for _ in range(n)]

    # ans = [0 for _ in range(n)]
    # for k in range(n):
    #     # z = zz[k]
    #     z = [0 for _ in range(n)]
    #     sub = s[k:]
    #     for i in range(1, len(sub)):
    #         count = 0
    #         for j in range(len(sub)-i):
    #             if sub[j] == sub[i+j]:
    #                 count += 1
    #                 if count == n // 2:
    #                     break
    #             else:
    #                 break
    #         z[i] = count
    #     ans[k] = max(z)
    #     # zz[k] = z
    # print(max(ans))






if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# 2019-11-18 17:34:23(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# import re
# import heapq
# import array
# from scipy.misc import comb # (default: exact=False)
# import numpy as np 



def main():
    n, s = sys.stdin.read().split()
    n = int(n)
    
    # a = [0 for _ in range(n)]
    # i = j = 0
    # while i < n:
    #     while i+j < n and s[j] == s[i+j]: 
    #         j += 1
    #     a[i] = j
    #     if j == 0:
    #         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

    # print(max(l for l in a if l <= n // 2))
    # print(a)
    

    # a = [0 for _ in range(n)]
    
    # i, j = 0, 0
    # while i < n:
    #     while i+j < n and s[j] == s[i+j]:
    #         j += 1
    #     a[i] = j
    #     if j == 0:
    #         i += 1
    #         continue
    #     k = 1
    #     while i+k < n and k+a[k] < j:
    #         a[i+k] = a[k]
    #         k += 1
    #     i += j
    #     j = 0
    # print(a)

    # a = [0 for _ in range(n)]
    # a[0] = n 
    # c = 0
    # for i in range(1, n):
    #     if i+a[i-c] < c+a[c]:
    #         a[i] = a[i-c]
    #     else:
    #         j = max(0, c+a[c]-i)
    #         while i+j < n and s[s] == s[i+j]:
    #             j += 1
    #         a[i] = j
    
    # print(a)

    # zz = [[0 for _ in range(n)] for _ in range(n)]
    ans = [0 for _ in range(n)]
    for k in range(n):
        # z = zz[k]
        z = [0 for _ in range(n)]
        sub = s[k:]
        for i in range(1, len(sub)):
            count = 0
            for j in range(len(sub)-i):
                if sub[j] == sub[i+j]:
                    count += 1
                    if count == n // 2:
                        break
                else:
                    break
            z[i] = count
        ans[k] = max(z)
        # zz[k] = z
    print(max(ans))






if __name__ == "__main__":
    main()

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
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:
import numpy as np
N = int(input())
s = str(input())
maxlen = N//2

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

ng = maxlen + 1
ok = 0
while np.abs(ok-ng) > 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()

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

for i in reversed(range(n)):
    for j in reversed(range(n)):
        if s[i] == s[j]:
            dp[i][j] = dp[i+1][j+1] + 1
            
ans = 0

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
S=input()
a=[0 for x in range(len(S))]

def zal(s):
  a[0]=len(s)
  i,j=1,0
  while i < a[0]:
    while i+j < a[0] and s[j]==s[i+j]:
      j+=1
    a[i]=j
    if j==0:
      i+=1
    else:
      k=1
      while i+k < a[0] and k+a[k] < j:
        a[i+k]=a[k]
        k+=1
      i+=k
      j-=k
  m=0
  for i in range(1,a[0]):
    if i >= a[i]:
      m=max(m,a[i])
  return m

m,i=0,0
while i < len(S)-1:
  m = max(m,zal(S[i:]))
  i += 1

print(m)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
ans=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(n):
    l=z_algo(s[i:])
    m=len(l)
    for j in range(m):
        ans=max(ans,min(j,l[j]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
dp=[[0]*n for i in range(n)]
ans=0
for i in range(1,n+1):
    for j in range(i):
        if s[j:i] in s[i:]:
            ans=max(ans,len(s[j:i]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
input=lambda :sys.stdin.readline().rstrip()
# inputs= sys.stdin.buffer.readlines
INF=float("inf")
MOD=10**9+7
#input = sys.stdin.buffer.readline
#sys.setrecursionlimit(2147483647)
#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
#map(int,input().split())

# Z-algorithm (O(N))
# https://deve68.hatenadiary.org/entry/20120201/1328109890
def Z(s):
    n=len(s)
    z=[0]*n
    z[0]=n
    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

# example
#print(Z("abaaabaabb")) # [10,0,1,1,4,0,1,2,0,0]


def main():
	n=int(input())
	s=input()
	ans=0
	for i in range(n-1):
		z=Z(s[i:])
		k=len(z)
		for j in range(k):
			ans=max(ans,min(j,z[j]))
	print(ans)
	
if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
input=lambda :sys.stdin.readline().rstrip()
# inputs= sys.stdin.buffer.readlines
INF=float("inf")
MOD=10**9+7

#input = sys.stdin.buffer.readline
#sys.setrecursionlimit(2147483647)

#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

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

def main():
	n=int(input())
	s=input()
	
	ans=0
	cnt=0
	
	
	for d in range(1,n):
		cnt=0
		for i in range(n-d):
			if s[i]==s[i+d]:
				cnt+=1
				ans = max(ans, min(cnt, d))
			else:
				cnt=0
	print(ans)
	
	
	
	
	

if __name__ == '__main__':
	main()