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

Solution code:

import sys
def input():
	return sys.stdin.readline().strip()

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

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

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

Submission status: Accepted

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

# アルファベット→int
h = {}
for i in range(26):
    h[chr(ord('a') + i)] = i

base1 = 1009
base2 = 1007
mod1 = 1000000007
mod2 = 1000000009

pow1 = [1]*(n+1)
pow2 = [1]*(n+1)
hash1 = [0]*(n+1)
hash2 = [0]*(n+1)
for i in range(n):
    hash1[i+1] = (hash1[i]+h[s[i]]) * base1 % mod1
    hash2[i+1] = (hash2[i]+h[s[i]]) * base2 % mod2
    pow1[i+1] = pow1[i] * base1 % mod1
    pow2[i+1] = pow2[i] * base2 % mod2


# [l, r)
def get(l, r):
    t1 = ((hash1[r] - hash1[l] * pow1[r-l]) % mod1 + mod1) % mod1
    t2 = ((hash2[r] - hash2[l] * pow2[r-l]) % mod2 + mod2) % mod2
    return (t1, t2)

from collections import deque, defaultdict


def check(k):
    # 長さk二分探索
    if k > n:
        return False
    que1 = deque()

    d = defaultdict(int)
    # 最初のk通りを入れる
    for i in range(k):
        if i+k<=n:
            a = get(i, i+k)
            que1.append(a)
        else:
            break
    for i in range(k, n-k+1):
        a = que1.popleft()
        d[a] += 1
        b = get(i, i+k)
        if d[b] > 0:
            return True
        que1.append(b)
    
    return False

left = 0
right = n

while right - left > 1:
    mid = (right+left)//2
    if check(mid):
        left = mid
    else:
        right = mid

print(left)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
dp = [[0]*N for _ in range(N)]
ans = 0
for i in range(N):
    for j in range(i+1,N):
        if(S[i]==S[j]):
            if(i==0):
                dp[i][j] = 1
            else:
                last = dp[i-1][j-1]
                if(j-last == i):
                    continue
                dp[i][j] = last+1

                ans = max(dp[i][j],ans)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
tmp = input()
my_str = input()

start = 0
end = 1
max_len = 0

while (end < len(my_str)):
    if my_str[start:end] in my_str[end:]:
        if end - start > max_len:
            max_len = end - start
        end += 1
    else:
        start += 1

print(max_len)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

def Z_algo(S):
    n=len(S)
    A=[0]*n
    A[0]=n
    i=1
    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
    return A

N = I()
S = str(input())

T = ''.join(list(reversed(S)))

dp = [0]*N
for i in range(1,N):
    a = Z_algo(T[N-i-1:])
    b = []
    for j in range(len(a)):
        b.append(min(a[j],j))
    dp[i] = max(dp[i-1], max(b))

print(dp[N-1])

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
N = int(readline())
S = tuple(map(ord, readline().strip()))

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

for j in range(N-1, -1, -1):
    for i in range(j-1, -1, -1):
        k = dp[i+1][j+1]
        if S[i] != S[j]:
            continue
        if i+k == j:
            dp[i][j] = k
        else:
            dp[i][j] = k+1
print(max(max(d) for d in dp))

Submission status: Accepted

Solution code:
def check(S, l):
    idx = {}
    for i in range(len(S)-l+1):
        x = S[i:i+l]
        if x not in idx:
            idx[x] = i
        else:
            if idx[x]+l <= i:
                return True
    return False


def main():
    N = int(input())
    S = input()
    lo = 0
    hi = N//2
    while lo < hi:
        mid = -(-(lo+hi)//2)
        if check(S, mid):
            lo = mid
        else:
            hi = mid - 1
    print(lo)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

def input():
    return sys.stdin.readline()[:-1]

from collections import defaultdict

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

def is_pos(n,S,N):
    dd = defaultdict(int)
    flag =True
    for i in range(N-n+1):
        s = dd[S[i:i+n]]
        if s!=0:
            if i+1-s>=n:
                flag=False
                break
        else:
            dd[S[i:i+n]]=i+1
    return flag


def bisect(i,j,S,N):
    while j-i>1:
        if is_pos((i+j)//2,S,N):
            j = (i+j)//2
        else:
            i = (i+j)//2
    return i

print(bisect(0,N//2 + 1, S, N))

Submission status: Accepted

Solution code:
def Z_algorithm(S):
    l=len(S)
    A=[0]*l
    A[0]=l
    i=1; j=0
    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

def main():
    n=int(input())
    S=input()
    ans=0
    for i in range(1,n):
        s=S[:i]
        t=S[i:]
        l=len(t)
        T=t+'-'+s
        Z=Z_algorithm(T)
        #print(i,l,T,Z,ans)
        ans=max(ans,max(Z[l:]))
    print(ans)
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    s = input()
    if s == "Sunny":
        print("Cloudy")
    elif s == "Cloudy":
        print("Rainy")
    else:
        print("Sunny")
    return

#B
def B():
    s = S()
    for i in range(len(s)):
        if i%2:
            if s[i] not in ["L","U","D"]:
                print("No")
                return
        else:
            if s[i] not in ["R","U","D"]:
                print("No")
                return
    print("Yes")
    return

#C
def C():
    n,k,q = LI()
    a = IR(q)
    f = [k-q]*(n)
    for i in range(q):
        ai = a[i]-1
        f[ai] += 1
    for i in f:
        if i <= 0:
            print("No")
        else:
            print("Yes")
    return

#D
def D():
    n,m = LI()
    a = LI()
    q = []
    for i in range(n):
        heappush(q,-a[i])
    for i in range(m):
        x = heappop(q)
        x *= -1
        x >>= 1
        heappush(q,-x)
    print(-sum(q))
    return

#E
def E():
    n = I()
    s = S()
    l = 0
    r = n
    M = 10**64+1
    b = 26
    alp = list("abcdefghijklmnopqrstuvwxyz")
    f = {}
    for i in alp:
        f[i] = ord(i)-ord("a")
    pb = [pow(b,i,M) for i in range(n+1)]
    while r-l > 1:
        m = (l+r)>>1
        d = defaultdict(lambda : float("inf"))
        hash = 0
        for i in s[:m]:
            hash *= b
            hash += f[i]
            hash %= M
        d[hash] = 0
        t = pb[m]
        for i in range(n-m):
            si = s[i]
            hash *= b
            hash -= t*f[si]
            hash += f[s[i+m]]
            hash %= M
            if d[hash]+m <= i+1:
                l = m
                break
            if i+1 < d[hash]:
                d[hash] = i+1
        else:
            r = m
    print(l)
    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    E()

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**9)
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()


def f(ss):
	n = len(ss) 
	LCSRe = [[0 for x in range(n + 1)] 
				for y in range(n + 1)] 
	res = ""
	res_length = 0

	index = 0
	for i in range(1, n + 1): 
		for j in range(i + 1, n + 1): 
			if (ss[i - 1] == ss[j - 1] and
				LCSRe[i - 1][j - 1] < (j - i)): 
				LCSRe[i][j] = LCSRe[i - 1][j - 1] + 1
				if (LCSRe[i][j] > res_length): 
					res_length = LCSRe[i][j] 
					index = max(i, index)
			else: 
				LCSRe[i][j] = 0
	if (res_length > 0): 
		for i in range(index - res_length + 1, index + 1): 
			res = res + ss[i - 1] 

	return res_length

n = ni()
s = ns()
print(f(s))

Submission status: Accepted

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):
    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
#    print(r)
    if r > i: r = i
    if ans < r: ans = r

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy3


def solve(n, s):
    dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
    res_len = 0
    idx = 0
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            if s[i - 1] == s[j - 1] and dp[i - 1][j - 1] < j - i:
                dp[i][j] = dp[i - 1][j - 1] + 1
                if dp[i][j] > res_len:
                    res_len = dp[i][j]
                    idx = max(i, idx)
            else:
                dp[i][j] = 0
    return res_len


def main():
    n = int(input())
    s = input()
    res_len = solve(n, s)
    print(res_len)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

n = int(input())
s = input()
D = [[0] * n for i in range(n)]

for i in range(n):
    D[0][i] = int(s[0]==s[i])
    D[i][0] = int(s[0]==s[i])
D[0][0] = 0

for i in range(1,n):
    for j in range(i+1,n):
        mae = D[i-1][j-1]
        if s[i] == s[j]:
            if j-i <= mae:
                D[i][j] = mae
            else:
                D[i][j] = mae + 1

#print(D)

print(max([max(D[i]) for i in range(n)]))

Submission status: Accepted

Solution code:
n=int(input())
s=input()
a=0
i=0
j=1
while j<n:
	if s[i:j] in s[j:]:
		a=max(a,len(s[i:j]))
		j+=1
	else:
		i+=1
	if i==j:
		i+=1
		j+=2
print(a)

Submission status: Accepted

Solution code:
def LRS(str): 
  
    n = len(str) 
    LCSRe = [[0 for x in range(n + 1)]  
                for y in range(n + 1)] 
  
    res = ""
    res_length = 0
  
    index = 0
    for i in range(1, n + 1): 
        for j in range(i + 1, n + 1): 
              
            if (str[i - 1] == str[j - 1] and
                LCSRe[i - 1][j - 1] < (j - i)): 
                LCSRe[i][j] = LCSRe[i - 1][j - 1] + 1
  
                if (LCSRe[i][j] > res_length): 
                    res_length = LCSRe[i][j] 
                    index = max(i, index) 
                  
            else: 
                LCSRe[i][j] = 0
  
    if (res_length > 0): 
        for i in range(index - res_length + 1, 
                                    index + 1): 
            res = res + str[i - 1] 
  
    return res 
  
n = int(input())
s = input()

print(len(LRS(s)))

Submission status: Runtime Error

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

def z_algorythm(s):
    n = len(s)
    LCP = [0]*n
    c = 0
    for i in range(1, n):
        if i + LCP[i-c] < c + LCP[c]:
            LCP[i] = LCP[i-c]
        else:
            j = max(0, c+LCP[c]-i)
            while i+j < n and s[j] == s[i+j]:
                j += 1
                LCP[i] = j
                c = i
    LCP[0] = n
    return LCP

ans = 0
for i in range(n):
    LCP = z_algorythm(s[i:])
    for j, len in enumerate(LCP):
        tmp = min(len, j)
        ans = max(ans, tmp)
print(ans)

Submission status: Runtime Error

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

def z_algorythm(s):
    n = len(s)
    LCP = [0]*n
    i = 1
    j = 0
    c = 0
    for i in range(1, n):
        if i + LCP[i-c] < c + LCP[c]:
            LCP[i] = LCP[i-c]
        else:
            j = max(0, c+LCP[c]-i)
            while i+j < n and s[j] == s[i+j]:
                j += 1
                LCP[i] = j
                c = i
    LCP[0] = n
    return LCP

ans = 0
for i in range(n):
    LCP = z_algorythm(s[i:])
    for j, len in enumerate(LCP):
        tmp = min(len, j)
        ans = max(ans, tmp)
print(ans)

Submission status: Runtime Error

Solution code:
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
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: Runtime Error

Solution code:
def isok(index):
  for i in range(n-index*2+1):
    for j in range(i+index+1,n-index+1):
      if s[i:i+index]==s[j:j+index]: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: Runtime Error

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-i else j-i
        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: Runtime Error

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

if __name__=='__main__':
  main()

Submission status: Runtime Error

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,-1,-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: Runtime Error

Solution code:
def z_algorithm(s):
	"""Z-algorithm O(|S|)
    """
    l = len(s)
    z = [0] * l
    z[0] = l
    i, j = 1, 0
    while i < l:
        while i + j < l and S[j] == S[i+j]:
            j += 1
        z[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while k + z[k] < j:
            z[i+k] = z[k]
            k += 1
        i += k
        j -= k
 
    return z

Submission status: Runtime Error

Solution code:
N = cin()[0]
S = input()

def alpha2num(alpha):
    num = 0
    for index, item in enumerate(list(alpha)):
        num += pow(26, len(alpha) - index - 1) * (ord(item) - ord('a') + 1)
    return num

def rol_hash(l):

    b, h = 10 ** 6 + 7, 10 ** 9 + 7
    base = pow(b, l, h)
    hash_s = 0
    dic = {}
    for i in range(l):  hash_s = (hash_s * b + alpha2num(S[i])) % h
    dic[hash_s] = l - 1
    for i in range(N - l + 1):
        if i + l < N:
            hash_s = (hash_s * b - base * alpha2num(S[i]) + alpha2num(S[i + l])) % h
            if hash_s in dic:
                if dic[hash_s] < i:  return 1
            else:  dic[hash_s] = i + l - 1
    return 0

def is_ok(mid):
    return rol_hash(mid)

def binary_search(left, right):
    while (abs(right - left) > 1):
        mid = (left + right) // 2
        if is_ok(mid):  right = mid
        else:  left = mid
    return right

left = N + 1
right = -1
ret = binary_search(left, right)
if ret == right:  print(0)
else:  print(ret)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from collections import deque

class RollingHash():
    def __init__(self, s, base1=1007, base2=2009, mod1=10**9+7, mod2=10**9+9):
        self.mod1 = mod1
        self.mod2 = mod2
        self.s = s
        n = len(s)
        self.hash1 = [0]*(n+1)
        self.pow1 = [1]*(n+1)
        self.hash2 = [0]*(n+1)
        self.pow2 = [1]*(n+1)
        for i in range(n):
            self.hash1[i+1] = (self.hash1[i]*base1 + ord(s[i])) % self.mod1
            self.pow1[i+1] = (self.pow1[i]*base1) % self.mod1
            self.hash2[i+1] = (self.hash2[i]*base2 + ord(s[i])) % self.mod2
            self.pow2[i+1] = (self.pow2[i]*base2) % self.mod2

    def get(self, l, r):
        h1 = (self.hash1[r] - self.hash1[l] * self.pow1[r-l]) % self.mod
        h2 = (self.hash2[r] - self.hash2[l] * self.pow2[r-l]) % self.mod2
        return (h1,h2)


n = int(input())
s = input()
rh = RollingHash(s, base1=1007, base2=1007, mod1=10**9+7, mod2=10**9+7)

for len_ in range(n//2,0,-1):
    ql = [(-1,-1)]*(len_-1)
    wait_q = deque(ql)
    hset = set()
    # print(len_)
    for i in range(n-len_+1):
        # print(s[i:i+len_])
        hs = rh.get(i,i+len_)
        if hs in hset:
            print(len_)
            exit()
        else:
            wait_q.append(hs)
            hset.add(wait_q.popleft())
        # print(wait_q)
        # print(hset)

else:
    print(0)

Submission status: Runtime Error

Solution code:
from collections import deque

class RollingHash():
    def __init__(self, s, base1=19683,base2=6561,mod1=2^61-1,mod2=2^61-1):
        self.mod1 = mod1
        self.mod2 = mod2
        self.s = s
        n = len(s)
        self.hash1 = [0]*(n+1)
        self.pow1 = [1]*(n+1)
        self.hash2 = [0]*(n+1)
        self.pow2 = [1]*(n+1)
        for i in range(n):
            self.hash1[i+1] = (self.hash1[i]*base1 + ord(s[i])) % self.mod1
            self.pow1[i+1] = (self.pow1[i]*base1) % self.mod1
            self.hash2[i+1] = (self.hash2[i]*base2 + ord(s[i])) % self.mod2
            self.pow2[i+1] = (self.pow2[i]*base2) % self.mod2

    def get(self, l, r):
        h1 = (self.hash1[r] - self.hash1[l] * self.pow1[r-l]) % self.mod2
        h2 = (self.hash2[r] - self.hash2[l] * self.pow2[r-l]) % self.mod2
        return (h1,h2)


n = int(input())
s = input()
rh = RollingHash(base1=1007,base2=2009,mod1=10**9+7,mod2=10**9+9)

for len_ in range(n//2,0,-1):
    ql = [(-1,-1)]*(len_-1)
    wait_q = deque(ql)
    hset = set()
    print(len_)
    for i in range(n-len_+1):
        print(s[i:i+len_])
        hs = rh.get(i,i+len_)
        if hs in hset:
            print(len_)
            exit()
        else:
            wait_q.append(hs)
            hset.add(wait_q.popleft())
        print(wait_q)
        print(hset)

else:
    print(0)

Submission status: Runtime Error

Solution code:
import numpy as np
from numba import njit
@njit
def solve(n,s):
    dp=np.zeros((n+1,n+1),dtype=int)
    for i in range(n):
        for j in range(i+1,n):
            if s[i]==s[j]:
                if dp[i][j]<j-i:
                    dp[i+1][j+1]=dp[i][j]+1
    print(np.amax(dp))
n=int(input())
s=input()
solve(n,s)

Submission status: Runtime Error

Solution code:
import numpy as np
from numba import njit
@njit
def solve():
    n=int(input())
    s=input()
    dp=np.zeros((n+1,n+1),dtype=int)
    for i in range(n):
        for j in range(i+1,n):
            if s[i]==s[j]:
                if dp[i][j]<j-i:
                    dp[i+1][j+1]=dp[i][j]+1
    print(np.amax(dp))
solve()

Submission status: Runtime Error

Solution code:
class RollingHash:

    def __init__(self, string, root, mod):
        self.root = root
        self.mod = mod
        self.hs = [0] * (len(string) + 1)
        self.pw = [1] * (len(string) + 1)
        for i in range(len(string)):
            self.hs[i + 1] = (self.hs[i] * self.root + ord(string[i])) % self.mod
            self.pw[i + 1] = self.pw[i] * self.root % self.mod

    def get_hash(self, l, r):
        "get the hash of s[l:r] (0 <= l <= r <= len(s))"
        return (self.hs[r] - self.hs[l] * self.pw[r - l]) % self.mod

    def __getitem__(self, index):
        if isinstance(index, slice):
            return self.get_hash(index.start, index.stop)
        else:
            return 0


RHMOD = (1 << 61) - 1
POSITIVIZER = RHMOD << 20
class RollingHashMOD61:
    """
    MOD == 2 ** 61 - 1
    参考: https://qiita.com/keymoon/items/11fac5627672a6d6a9f6
    """


    def __init__(self, string, root):
        self.root = root
        self.hs = [0] * (len(string) + 1)
        self.pw = [1] * (len(string) + 1)
        for i in range(len(string)):
            tmp = self.hs[i] * self.root + ord(string[i])
            self.hs[i + 1] = (tmp >> 61) + (tmp & RHMOD)
            tmp = self.pw[i] * self.root
            self.pw[i + 1] = (tmp >> 61) + (tmp & RHMOD)

    def get_hash(self, l, r):
        "get the hash of s[l:r] (0 <= l <= r <= len(s))"
        ret = (self.hs[r] - self.hs[l] * self.pw[r - l] + POSITIVIZER)
        ret = (ret >> 61) + (ret & RHMOD)
        if ret >= RHMOD:
            ret -= RHMOD
        assert 0 <= ret < RHMOD
        return ret

    def __getitem__(self, index):
        if isinstance(index, slice):
            return self.get_hash(index.start, index.stop)
        else:
            return 0
        
if __name__ == "__main__":
    N = int(input())
    S = input()

    MOD = 2 ** 61 - 1
    root = 10000

    rh = RollingHashMOD61(S, root)

    ok = 0
    ng = N
    while ng - ok > 1:
        mid = (ok + ng) // 2
        hashes = dict()
        flg = False
        for i in range(N - mid + 1):
            hashofsub = rh[i:i+mid]
            if hashofsub in hashes:
                if i >= hashes[hashofsub] + mid:
                    flg = True
                    break
            else:
                hashes[hashofsub] = i
        
        if flg:
            ok = mid
        else:
            ng = mid

    print(ok)

Submission status: Runtime Error

Solution code:
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            vars()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)

import sys
import numpy as np

def z_algo(S):  # [z_algo, "i8[:](i8[:])"],
    # Z-algoirhm  O(n)
    # Z[i] := S と S[i:] で prefix が何文字一致しているか
    # 検証: https://atcoder.jp/contests/abc150/submissions/15829530
    i, j, n = 1, 0, len(S)
    Z = np.zeros(S.shape, dtype=np.int64)
    Z[0] = n
    while i < n:
        while i+j < n and S[j] == S[i+j]:
            j += 1
        if j == 0:
            i += 1
            continue
        Z[i] = j
        d = 1
        while i+d < n and d+Z[d] < j:
            Z[i+d] = Z[d]
            d += 1
        i += d
        j -= d
    return Z

def solve(N, S):
    ans = 0
    for i in range(N):
        Z = z_algo(S[i:])
        for idx_Z, z in enumerate(Z):
            an = min(z, idx_Z)
            ans = max(ans, an)
    return ans

numba_compile([
    [z_algo, "i8[:](u1[:])"],
    [solve, "i8(i8,u1[:])"]
])

def main():
    N = int(sys.stdin.buffer.readline())
    S = np.frombuffer(sys.stdin.buffer.readline(), dtype=np.uint8).copy()
    ans = solve(N, S)
    print(ans)

main()

Submission status: Runtime Error

Solution code:
class RollingHash:
    def __init__(self, s):
        b1, b2 = 1007, 2009
        self.mod1, self.mod2 = 10**9+7, 10**9+9
        self.size = len(s)
        self.string = s

        self.hash1 = self.make_hashtable(b1, mod1)
        self.hash2 = self.make_hashtable(b2, mod2)
        self.pow1 = self.make_powtable(b1, mod1)
        self.pow2 = self.make_powtable(b2, mod2)

    def make_hashtable(self, B, MOD):
        hashtable = [0] * (self.size+1)
        for i in range(1, self.size+1):
            hashtable[i] = (hashtable[i-1] * B + ord(self.string[i-1]))%MOD
        return hashtable
    
    def make_powtable(self, B, MOD):
        power = [0] * (self.size+1)
        power[0] = 1
        for i in range(1, self.size+1):
            power[i] = (B * power[i-1])%MOD
        return power

    def get_hash(self, l, length):
        r = length+l-1
        l -= 1
        h1 = (self.hash1[r]-self.hash1[l]*self.pow1[r-l])%self.mod1
        h2 = (self.hash2[r]-self.hash2[l]*self.pow2[r-l])%self.mod2
        return (h1, h2)

from collections import defaultdict

def solve1():
    N = int(input())
    S = input()
    size = len(S)
    hash_table = RollingHash(S)

    ans = 0
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            if S[i-1]!=S[j-1]:continue

            left = 1
            right = min(j-i, size-j+1)+1

            while right-left>1:
                m = (left+right)//2
                if hash_table.get_hash(i, m)==hash_table.get_hash(j, m):
                    left = m
                else:
                    right = m
            ans = max(ans, left)

    print(ans)


def solve2():
    N = int(input())
    S = input()
    size = len(S)
    hash_table = RollingHash(S)

    def check(m):
        d = defaultdict(lambda :10**20)
        for i in range(1, size-m+2):
            h = hash_table.get_hash(i, m)
            d[h] = min(d[h], i)
            if (i-d[h])>=m:
                return True
        return False

    left, right = 0, size//2 + 1
    while right-left>1:
        m = (right+left)//2
        if check(m):
            left = m
        else:
            right = m

    print(left)

if __name__ == "__main__":
    # solve1()
    solve2()

Submission status: Runtime Error

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

lb=0
rb=N+1
while rb-lb>1:
    mid=(lb+rb)//2
    f=0
    x=0
    a=[]
    for i,s in enumerate(S[:mid]):
        x+=pow(26,i)*(ord(s)-ord('a'))
    a+=[x]
    m=pow(26,mid-1)
    se=set([])
    for i,s in enumerate(S[mid:]):
        x-=ord(S[i])
        x//=26
        x+=m*(ord(s)-ord('a'))
        if i>=mid-1:
            se.add(a[i-mid-1])
        if x in se:
            f=1
            break
        else:
            a+=[x]
    if f:
        lb=mid
    else:
        rb=mid
print(lb)

Submission status: Runtime Error

Solution code:
N = int(input())
S = input()
#dp[i][j] S[i-x:i+1]==S[j-x:j+1]となる最大のx
dp = [[0] * (N + 1) for _ in range(N + 1)]
ans = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        if S[i] == S[j]:
            dp[i][j] = min(dp[i - 1][j - 1] + 1, j - i)
    ans = max(ans, dp[i])
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
S = input()
#dp[i][j] S[i-x:i+1]==S[j-x:j+1]となる最大のx
dp = [[0] * (N + 1) for _ in range(N + 1)]
ans = 0
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)
            ans = max(ans, dp[i])
print(ans)

Submission status: Runtime Error

Solution code:
N, S = [int(_) for _ in input().split()]
#dp[i][j] S[i-x:i+1]==S[j-x:j+1]となる最大のx
dp = [[0] * (N + 1) for _ in range(N + 1)]
ans = 0
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)
            ans = max(ans, dp[i])
print(ans)

Submission status: Runtime Error

Solution code:
N, S = [int(_) for _ in input().split()]
#dp[i][j] S[i-x:i+1]==S[j-x:j+1]となる最大のx
dp = [[0] * (N + 1) for _ in range(N + 1)]
ans = 0
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)
        ans = max(ans, dp[i])
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

def main(N, S, dp):
    ans = 0
    for i in range(N - 1):
        for j in range(i + 1, N):
            dp[i, j] = min(j - i, dp[i - 1, j - 1] + 1) if S[i] == S[j] else 0
        ans = max(ans, np.max(dp[i]))
    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', 'i8(i8,i8[:],i8[:,:])')(main)
    # b1: bool, i4: int32, i8: int64, double: f8, [:], [:, :]
    cc.compile()
else:
    try:
        from my_module import main
    except:
        1
    dp = np.zeros((N + 1, N + 1), dtype=int)
    N = int(input())
    S = np.array([ord(_) for _ in input()])
    print(main(N, S, dp))