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: Wrong Answer

Solution code:
import re

input()
s = input()
m = re.match(r'^.*?(.+).*?\1.*?$', s)
print(len(m.groups()[0]) if m else 0)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

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

ans = 0
for i in range(1,n//2+1):
    res = 0
    r = 0
    for a,b in zip(s,s[i:]):
        if a == b:
            res += 1
            if res > r: r = res
        else:
            res = 0
    if r > i: r = i
    if ans < r: ans = r

print(ans)

Submission status: Wrong Answer

Solution code:
def solve(n, s):
    MOD = 10 ** 9 + 7
    d = 26
    s = [ord(c) - 97 for c in s]

    for l in range(n // 2, 0, -1):
        t = 0
        exist = set()
        m = pow(d, l, MOD)
        for c in s[:l]:
            t = (t * d + c) % MOD
        exist.add(t)
        for i, c in enumerate(s[l:], start=l):
            t = (t * d - s[i - l] * m + c) % MOD
            if t in exist:
                return l
            exist.add(t)

    return 0


n = int(input())
s = input()
print(solve(n, s))

Submission status: Time Limit Exceeded

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

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

ans = 0
for i in range(n):
    t = s[i:]
    z = z_algorithm(t)
    for j in range(len(z)):
        if z[j] <= j:
            ans = max(ans, z[j])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input());s=input()
def Zalgorithm(a):
    n=len(a)
    left,right=-1,-1
    res=[0]*n
    ret=0
    for i in range(1,n):
        cnt=0 if right<i else min(right-i,res[i-left])
        while i+cnt<n and a[cnt]==a[cnt+i]:cnt+=1
        res[i]=cnt
        if i>=cnt:ret=max(ret,cnt) 
        if right<i+cnt:left,right=i,i+cnt
    #res[0]=n
    return ret
ans=0
now=''
for i in range(n-1,-1,-1):
    now=s[i]+now
    ans=max(ans,Zalgorithm(now))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input());s=input()
from collections import defaultdict
d=defaultdict(lambda:-1)
ans=0
ok=set()
for j in range(n):
    now=''
    for i in range(j,-1,-1):
        now=s[i]+now
        if now in ok:continue
        if d[now]!=-1:
            if d[now]<=i:
                ans=max(ans,j-i+1)
                ok.add(now)
        else:d[now]=j+1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.buffer.readline
inputs=sys.stdin.buffer.readlines
sys.setrecursionlimit(10**9)
n=int(input());s=input()
from collections import defaultdict
d=defaultdict(lambda:-1)
ans=0
ok=set()
for j in range(n+1):
    X=list(b' '+s[:j])
    X.reverse()
    for i in range(j):
        X.pop()
        x=tuple(X)
        if x in ok:continue
        if d[x]!=-1:
            if d[x]<=i:
                ans=max(ans,j-i)
                ok.add(x)
        else:
            d[x]=j
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input());s=input()
from collections import defaultdict
d=defaultdict(lambda:-1)
ans=0
ok=set()
for j in range(n+1):
    for i in range(j):
        x=s[i:j]
        if x in ok:continue
        if d[x]!=-1:
            if d[x]<=i:
                ans=max(ans,j-i)
                ok.add(x)
        else:
            d[x]=j
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
#長さnの文字列s
def gene_hash(i,j): #特定範囲のハッシュを返す s[i:j]
    return (hash1[j]-hash1[i]*power1[j-i]%mod1)%mod1

base1 = 1007
mod1 = 10**9+7

hash1 = [0]*(n+1)
power1 = [1]*(n+1)

for i,e in enumerate(s):
    hash1[i+1] = (hash1[i]*base1 + ord(e))%mod1
    power1[i+1] = (power1[i]*base1)%mod1
    
lef = 0
rig = n//2 + 1

while rig - lef > 1:
    mid = (rig+lef)//2
    Flag = False
    for i in range(n-2*mid+1):
        if Flag:
            break
        now = gene_hash(i,i+mid)
        for j in range(i+mid,n-mid+1):
            if now == gene_hash(j,j+mid):
                Flag = True
                break
    if Flag:
        lef = mid
    else:
        rig = mid
print(lef)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
left = 0
right = n // 2 + 1
while right - left > 1:
    mid = (right + left) // 2
    len = mid
    for i in range(n-2*len + 1):
        s1 = s[i:i+len]
        s2 = s[i+len:]
        if s1 in s2:
            left = mid
            break
    else:
        right = mid
print(left)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
left = 0
right = n // 2 + 1
while right - left > 1:
    mid = (right + left) // 2
    len = mid
    for i in range(n):
        if i + len > n - len:
            continue
        s1 = s[i:i+len]
        s2 = s[i+len:]
        if s1 in s2:
            left = mid
            break
    else:
        right = mid
print(left)

Submission status: Time Limit Exceeded

Solution code:
import sys

# 1-dimension Rolling Hash
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

mod = 10**9 + 7
base = 37

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

rh = RollingHash(S, base, mod)
ans = 0
for i in range(N):
     for w in range(1, N//2+1):
        if N <= i + w:
            continue
        original = rh.get(i, i+w)
        # print("org", original)
        for j in range(i+w+1, N):
            if N <= j + w:
                continue
            hash = rh.get(j, j+w)
            # print("hash", hash)
            if hash == original:
    	        ans = max(ans, w+1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:

from collections import defaultdict

def main():
    #bfならどう解く？
    #O(n2)で解ける
    N = int(input())
    S = input()
    
    length = 1
    ans = 0
    while length<= N//2:
        seen = defaultdict(int)
        for start in range(length):
            for idx in range(start, N-length+1, length):
                sub = S[idx:idx+length]
                if sub in seen:
                    prev_idx = seen[sub]
                    if prev_idx + length <= idx:
                        ans = length
                        break
                else:
                    seen[sub] = idx
        length += 1
    
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

from collections import defaultdict

def main():
    #bfならどう解く？
    #O(n2)で解ける
    N = int(input())
    S = input()
    
    length = 1
    ans = 0
    while length<= N//2:
        seen = defaultdict(set)
        for start in range(length):
            for idx in range(start, N-length+1, length):
                sub = S[idx:idx+length]
                if sub in seen:
                    for prev_idx in seen[sub]:
                        if prev_idx + length <= idx:
                            ans = length
                            break
                seen[sub].add(idx)
        length += 1
    
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline

N = int(readline())
S = readline().rstrip()

# dp[i][j] = i文字目からとj文字目からとで最長の長さ
# S[i] != S[j] ならdp[i][j] = 0
# S[i] == S[j] ならdp[i][j] = dp[i + 1][j + 1] + 1

dp = [[0] * (N + 1) for i in range(N + 1)]

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

Submission status: Time Limit Exceeded

Solution code:
class RollingHash():
  def __init__(self,s,base=37,mod=10**9+7):
    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
def isok(l):
  for i in range(n-l*2+1):
    t=s[i:i+l]
    for j in range(i+l,n-l+1):
      if t==s[j:j+l]:return 1
  return 0
def b_search():
  ng=n+1
  ok=0
  while abs(ng-ok)>1:
    mid=(ng+ok)//2
    if isok(mid):ok=mid
    else:ng=mid
  return ok
n=int(input())
s=input()
rh=RollingHash(s)
print(b_search())

Submission status: Time Limit Exceeded

Solution code:
def isok(l):
  for i in range(n-l*2+1):
    t=s[i:i+l]
    for j in range(i+l,n-l+1):
      if t==s[j:j+l]:return 1
  return 0
def b_search():
  ng=n+1
  ok=0
  while abs(ng-ok)>1:
    mid=(ng+ok)//2
    if isok(mid):ok=mid
    else:ng=mid
  return ok
n=int(input())
s=input()
print(b_search())

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 10 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
N = int(input())
S = input()
ans = 0
ws = defaultdict(list)
for l in range(1, N // 2 + 1):
    for i in range(0, N - l + 1):
        w = S[i:i+l]
        if len(ws[w]) > 0:
            if ws[w][-1] < i:
                ws[w].append(i)
        else:
            ws[w].append(i)
for k, v in ws.items():
    if len(v) <= 1:
        continue
    else:
        ans = max(ans, len(k))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 10 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
N = int(input())
S = input()
d = defaultdict(list)
for i in range(N):
    for j in range(i + 1, N):
        w = S[i:j+1]
        if len(d[w]) == 0:
            d[w].append((i, j))
        elif d[w][-1][-1] < i:
            d[w].append((i, j))

ans = 0
for k, v in d.items():
    if len(v) <= 1:
        continue
    ans = max(ans, len(k))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys


# \n
def input():
    return sys.stdin.readline().rstrip()


def main():
    N = int(input())
    S = list(input())

    ok = 0
    ng = N // 2
    ans = 0
    for i in range(N - 1):
        for j in range(i + ans + 1, N):
            if  N - j + 1 < ans:
                break
            for k in range(0, min(j - i, N - j)):
                if S[i + k] != S[j + k]:
                    ans = max(ans, k)
                    break
            else:
                ans = max(ans, k + 1)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys


# \n
def input():
    return sys.stdin.readline().rstrip()


def main():
    N = int(input())
    S = list(input())

    ok = 0
    ng = N // 2
    ans = 0
    for i in range(N - 1):
        for j in range(i + 1, N):
            if min(j - i, N - j) + 1 < ans:
                continue
            for k in range(0, min(j - i, N - j)):
                if S[i + k] != S[j + k]:
                    ans = max(ans, k)
                    break
            else:
                ans = max(ans, k + 1)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys


# \n
def input():
    return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    S=list(input())

    ok =0
    ng =N//2
    ans =0
    for i in range(N-1):
        for j in range(i+1,N):
            for k in range(0,min(j-i,N-j)):
                if S[i+k] != S[j+k]:
                    ans =max(ans,k)
                    break
            else:
                ans = max(ans,k+1)
    print(ans)







if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys


# \n
def input():
    return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    S=list(input())

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

    print(ans)







if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right
import sys
input = sys.stdin.readline
n = int(input())
s = tuple(map(lambda x: ord(x) - ord("a") + 1, input()))
base = 1007
mod = 2**61 - 1

length = n//2
b = [1] * (length + 1)
shash = [0] * (length+1)
for i in range(1, length + 1):
    b[i] = b[i-1] * base
    b[i] %= mod
    shash[i] = shash[i - 1] * base % mod + s[i - 1]
    shash[i] %= mod

for ans in reversed(range(1, length+1)):
    # calc hash
    hash_ = 0
    check = {}
    #y = set([])
    for left in range(n - ans + 1):
        if left == 0:
            hash_ = shash[ans]
            check[hash_] = left
            #y.add(hash_)
        else:
            hash_ = base * hash_ % mod - b[ans] * s[left - 1] % mod + s[left + ans - 1]
            hash_ %= mod
            if hash_ in check.keys():
                # print("tmp = ", tmp)
                if check[hash_] <= left - ans:
                    print(ans)
                    # a = check[hash_][tmp-1]
                    # at = "".join(map(lambda x: chr(x + ord("a")), s[a:a+ans]))
                    # for j in range(ans):
                        # if s[a+j] != s[left+j]:
                            # print("Fail")
                            # exit()
                    # print("Success")
                    sys.exit()
            else:
                check[hash_] = left
                #y.add(hash_)
        # print(hash_, s[left:left+ans])
print(0)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right
n = int(input())
s = list(map(lambda x: ord(x) - ord("a") + 1, input()))
base = 1007
mod = 2**61 - 1
b = [1] * (n//2 + 6)
for i in range(n//2 + 5):
    b[i+1] = b[i] * base
    b[i+1] %= mod

length = n//2

for ans in reversed(range(1, length+1)):
    # calc hash
    hash_ = 0
    check = {}
    y = set([])
    for left in range(n - ans + 1):
        if left == 0:
            for i in range(ans):
                hash_ += s[i] * b[ans - i - 1] % mod
                hash_ %= mod
            check[hash_] = [left]
            y.add(hash_)
        else:
            hash_ = base * hash_ % mod - b[ans] * s[left - 1] % mod + s[left + ans - 1]
            hash_ %= mod
            if hash_ in y:
                tmp = bisect_right(check[hash_], left-ans)
                # print("tmp = ", tmp)
                if tmp == 0:
                    check[hash_].append(left)
                else:
                    print(ans)
                    # a = check[hash_][tmp-1]
                    # at = "".join(map(lambda x: chr(x + ord("a")), s[a:a+ans]))
                    # for j in range(ans):
                        # if s[a+j] != s[left+j]:
                            # print("Fail")
                            # exit()
                    # print("Success")
                    exit()
            else:
                check[hash_] = [left]
                y.add(hash_)
        # print(hash_, s[left:left+ans])
print(0)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right
n = int(input())
s = list(map(lambda x: ord(x) - ord("a") + 1, input()))
base = 1007
mod = 2**61 - 1
b = [1] * (n//2 + 6)
for i in range(n//2 + 5):
    b[i+1] = b[i] * base
    b[i+1] %= mod

length = n//2

for ans in reversed(range(1, length+1)):
    # calc hash
    hash_ = 0
    check = {}
    for left in range(n - ans + 1):
        if left == 0:
            for i in range(ans):
                hash_ += s[i] * b[ans - i - 1] % mod
                hash_ %= mod
            check[hash_] = [left]
        else:
            hash_ = base * hash_ % mod - b[ans] * s[left - 1] % mod + s[left + ans - 1]
            hash_ %= mod
            if hash_ in check.keys():
                tmp = bisect_right(check[hash_], left-ans)
                # print("tmp = ", tmp)
                if tmp == 0:
                    check[hash_].append(left)
                else:
                    print(ans)
                    # a = check[hash_][tmp-1]
                    # at = "".join(map(lambda x: chr(x + ord("a")), s[a:a+ans]))
                    # for j in range(ans):
                        # if s[a+j] != s[left+j]:
                            # print("Fail")
                            # exit()
                    # print("Success")
                    exit()
            else:
                check[hash_] = [left]
        # print(hash_, s[left:left+ans])
print(0)

Submission status: Time Limit Exceeded

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

length = n//2

for ans in reversed(range(1, length+1)):
    for left in range(n - 2 * ans + 1):
        for right in range(left + ans, n - ans + 1):
            if s[left:left+ans] == s[right:right+ans]:
                print(ans)
                exit()

print(0)

Submission status: Time Limit Exceeded

Solution code:
import sys
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

def z_algorithm(s: list):
    n = len(s)
    if n == 0: return []
    z = [-1] * n
    z[0] = 0; j = 0
    for i in range(1, n):
        k = z[i] = 0 if j + z[j] <= i else min(j + z[j] - i, z[i - j])
        while i + k < n and s[k] == s[i + k]: k += 1
        z[i] = k
        if j + z[j] < i + z[i]: j = i
    z[0] = n
    return z

def z_algorithm2(s: str):
    n = len(s)
    s2 = list(map(ord, s))
    return z_algorithm(s2)

def Main():
    n = read_int()
    s = read_str()
    ans = 0
    for i in range(n):
        lcp = z_algorithm2(s[i:])
        for j, x in enumerate(lcp):
            ans = max(ans, min(j, x))
    print(ans)

if __name__ == '__main__':
    Main()

Submission status: Time Limit Exceeded

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

result = 0

def check(l):
    for start in range(N - 2*l + 1):
        if s[start:start+l] in s[start+l:]:
            return True
    else:
        return False

mn = 0
mx = N // 2 + 1

while mx - mn != 1:
    md = (mn + mx) // 2
    if check(md):
        mn = md
    else:
        mx = md

print(mn)

Submission status: Time Limit Exceeded

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

result = 0

for l in range((N+1)//2, -1, -1):
    for start in range(N - 2*l + 1):
        if s[start:start+l] in s[start+l:]:
            result = l
            break
    if result > 0:
        break

print(result)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit

@njit(cache=True)
def main(N, s, dpt, result):
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            if s[j-1] == s[i-1]:
                if j - dpt[i-1][j-1] > i:
                    dpt[i][j] = dpt[i-1][j-1] + 1
            if dpt[i][j] > result:
                result = dpt[i][j]

    return result

if __name__ == '__main__':
    N = int(input())
    s = input()

    dpt = np.zeros((N+1, N+1), dtype='int32')
    result = 0
    print(main(N, s, dpt, result))

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    s = input()

    dpt = [[0] * (N + 1) for i in range(N + 1)]
    result = 0
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            if s[j-1] == s[i-1]:
                if j - dpt[i-1][j-1] > i:
                    dpt[i][j] = dpt[i-1][j-1] + 1
            if dpt[i][j] > result:
                result = dpt[i][j]

    print(result)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit

@njit(cache=True)
def main(N, s, dpt):
    result = 0
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            if s[j-1] == s[i-1]:
                if j - dpt[i-1][j-1] > i:
                    dpt[i][j] = dpt[i-1][j-1] + 1
            if dpt[i][j] > result:
                result = dpt[i][j]

    return result

if __name__ == '__main__':
    N = int(input())
    s = np.array([ord(c) for c in input()], dtype='int32')

    dpt = np.array([[0] * (N + 1) for i in range(N + 1)])

    print(main(N, s, dpt))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit

@njit(cache=True)
def main(N, s, dpt):
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            if s[j-1] == s[i-1]:
                if j - dpt[i-1][j-1] > i:
                    dpt[i][j] = dpt[i-1][j-1] + 1

    result = 0
    for i in range(N + 1):
        result = max(result, max(dpt[i]))

    return result

if __name__ == '__main__':
    N = int(input())
    s = np.array([ord(c) for c in input()], dtype='int32')

    dpt = np.array([[0] * (N + 1) for i in range(N + 1)])

    print(main(N, s, dpt))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit

@njit
def main(N, s, dpt):
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            if s[j-1] == s[i-1]:
                if j - dpt[i-1][j-1] > i:
                    dpt[i][j] = dpt[i-1][j-1] + 1

    result = 0
    for i in range(N + 1):
        result = max(result, max(dpt[i]))

    return result

if __name__ == '__main__':
    N = int(input())
    s = np.array([c for c in input()], dtype='str')

    dpt = np.array([[0] * (N + 1) for i in range(N + 1)])

    print(main(N, s, dpt))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
s = [c for c in input()]

dpt = [[0] * (N + 1) for i in range(N + 1)]

for i in range(1, N+1):
    for j in range(i+1, N+1):
        if s[j-1] == s[i-1]:
            prev = dpt[i-1][j-1]
            if j - prev > i:
                dpt[i][j] = prev + 1

result = 0
for i in range(N + 1):
    result = max(result, max(dpt[i]))

print(result)

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())
    S = readline().strip()

    dp = [0] * (N + 1)
    ans = 0

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

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())
    S = readline().strip()

    dp = [[0] * (N + 1) for _ in range(N + 1)]
    for i in range(N - 1, -1, -1):
        for j in range(N - 1, -1, -1):
            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):
            if ans < min(dp[i][j], j - i):
                ans = min(dp[i][j], j - i)

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import copy
import random
import itertools
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

dic = dict()

def zalg(s):
    n = len(s)
    ret = [0] * n
    ret[0] = n
    i, j = 1, 0
    while i < n:
        while i + j < n and s[j] == s[i+j]:
            j += 1
        ret[i] = j

        if j == 0:
            i += 1
            continue

        k = 1
        while k < j and k + ret[k] < j:
            ret[i + k] = ret[k]
            k += 1

        i += k
        j -= k

    return ret

def solve(n=None, s1=None, s2=None):
    n = getN()
    s = getS()
    ans = 0
    for i in range(n):
        ps = s[i:]
        z = zalg(ps)
        for i, zz in enumerate(z):
            if i >= zz:
                ans = max(ans, zz)
    print(ans)

def main():
    n = getN()
    for _ in range(n):
        solve()
    return


if __name__ == "__main__":
    # main()
    solve()

Submission status: Time Limit Exceeded

Solution code:
def main():
  n=int(input())
  s=input()
  dp=[[0]*(n+1) for i in range(n+1)]
  for i in reversed(range(n)):
    for j in reversed(range(i+1,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(i+1,n):
      ans=max(ans,min(j-i,dp[i][j]))
  print(ans)
        

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
  n=int(input())
  s=np.array([ord(i) for i in input()])
  dp=np.zeros((n,n),dtype=int)
  for i in range(n-1):
    for j in range(i+1,n):
      if s[i]==s[j]:
        dp[i,j]=min(j-i, dp[i-1,j-1]+1)
  print(np.amax(dp))
        

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
  n=int(input())
  s=np.array([ord(i) for i in input()])
  dp=np.zeros((n,n),dtype=int)
  for i in range(n-1):
    for j in range(i+1,n):
      if s[i]==s[j]:
        dp[i][j]=min(j-i, dp[i-1][j-1]+1)
  print(np.amax(dp))
        

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
  n=int(input())
  s=np.array([ord(i) for i in input()])
  dp=np.zeros((n+1,n+1),dtype=int)
  ans=0
  for i in range(n-1,-1,-1):
    for j in range(n-1,i,-1):
      if s[i]==s[j]:
        dp[i][j]=dp[i+1][j+1]+1
        now=dp[i][j] if dp[i][j]<j-1 else j-1
        if ans<now:
          ans=now
        #ans=max(ans,min(dp[i][j],j-i))
  #for i in dp:
  #  print(i)
  print(ans)      
        

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
  n=int(input())
  s=np.array([ord(i) for i in input()])
  dp=np.zeros((n+1,n+1),dtype=int)
  ans=0
  for i in range(n-1,-1,-1):
    for j in range(n-1,i,-1):
      if s[i]==s[j]:
        dp[i][j]=dp[i+1][j+1]+1
        ans=max(ans,min(dp[i][j],j-i))
  #for i in dp:
  #  print(i)
  print(ans)      
        

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
  n=int(input())
  s=input()
  dp=np.array([[0]*(n+1) for i 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]=dp[i+1][j+1]+1
  #for i in dp:
  #  print(i)
  
  ans=0
  for i in range(n-1):
    for j in range(i+1,n):
      ans=max(ans,min(j-i,dp[i][j]))
  print(ans)      
        

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  n=int(input())
  s=input()
  dp=[[0]*(n+1) for i 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]=dp[i+1][j+1]+1
  #for i in dp:
  #  print(i)
  
  ans=0
  for i in range(n-1):
    for j in range(i+1,n):
      ans=max(ans,min(j-i,dp[i][j]))
  print(ans)      
        

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:

def main():
  n=int(input())
  s=input()
  ans=0
  for i in range(n):
    if ans>n-i:
      break
    Z=[0]*n
    j=i+1
    while j<n:
      k=0
      while i+k<j and j+k<n and s[i+k]==s[j+k]:
        k+=1
      Z[j]=k
      j+=1
    t=max(Z)
    if t>ans:
      ans=t
  print(ans)


if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:

def main():
  n=int(input())
  s=input()
  ans=0
  for i in range(n):
    Z=[0]*n
    j=i+1
    while j<n:
      k=0
      while i+k<j and j+k<n and s[i+k]==s[j+k]:
        k+=1
      Z[j]=k
      #if k>1:
      #  j+=k
      #else:
      j+=1
      #j+=max(k,1)
    t=max(Z)
    if ans<t:
      ans=t
  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):
  Z=[0]*n
  j=i+1
  while j<n:
    k=0
    while i+k<j and j+k<n and s[i+k]==s[j+k]:
      k+=1
      Z[j]=k
    j+=max(k,1)
  ans=max(ans,max(Z))
print(ans)

Submission status: Time Limit Exceeded

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

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