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

Solution code:
def rolling_hash(s):
    l = len(s)
    h = [0]*(l + 1)
    v = 0
    for i in range(l):
        h[i+1] = v = (v * base + ord(s[i])) % mod
    return h
def setup_pw(l):
    pw = [1]*(l + 1)
    v = 1
    for i in range(l):
        pw[i+1] = v = v * base % mod
    return pw
def get(h, b, l, r):
    return (h[r] - h[l] * b[r-l]) % mod

def check_bisect(l,h1,b1,h2,b2):
    for j in range(N-2*l+1):
        a1 = get(h1,b1,j,l+j)
        a2 = get(h2,b2,j,l+j)
        for k in range(N-2*l-j+1):
            if a1 == get(h1,b1,j+l+k,2*l+j+k) and a2 == get(h2,b2,j+l+k,2*l+j+k):
                return True
    return False

N = int(input())
S = input()
mod = 1000000007
base = 37
h1 = rolling_hash(S)
b2 = setup_pw(N)
base = 401
h2 = rolling_hash(S)
b2 = setup_pw(N)
left = 1
right = N // 2
finish = False
if N <= 26:
    s = set(list(S))
    if N <= 3:
        if len(s) < N:
            print('1')
        else:
            print('0')
        finish = True
    else:
        if len(s) == N:
            print('0')
            finish = True
while finish == False:
    if left == right:
        print(left)
        finish = True
    elif right - left == 1:
        if check_bisect(right,h1,b1,h2,b2):
            print(right)
        else:
            print(left)
        finish = True
    else:
        mid = (left+right) // 2
        if check_bisect(mid,h1,b1,h2,b2):
            left = mid
        else:
            right = mid - 1

Submission status: Runtime Error

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

import random
base1 = 1007
mod1 = 10**9+7
base2 = 2009
mod2 = 10**9+9
modTank1 = [3000012541,3000012553,3000012563,3000012649,3000012683,3000012709]
mod1 = modTank1[random.randint(0,5)]
modTank2 = [3000014753,3000014783,3000014833,3000014839,3000014891,3000015433]
mod2 = modTank2[random.randint(0,5)]
hash1 = [0]*(n+1)
power1 = [1]*(n+1)
hash2 = [0]*(n+1)
power2 = [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
    hash2[i+1] = (hash2[i]*base2 + ord(e))%mod2
    power2[i+1] = (power2[i]*base2)%mod2

def rolling_hash(i, j):
    return ((hash1[j]-hash1[i]*power1[j-i]%mod1)%mod1)*(10**10) + (hash2[j]-hash2[i]*power2[j-i]%mod2)%mod2



hash = set()
ans = 0
for i in range(n//2, 0, -1):#length
    for j in range(1, n-i+2):
        h = rolling_hash(j, j+i)
        if h not in hash:
            hash.add(h)
        else:
            ans = i
            break
    if ans != 0:
        break
print(ans)

Submission status: Runtime Error

Solution code:
import sys #追加

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

sys.setrecursionlimit(n) #追加

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] and i != j:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        if A[i] >= N - i - 1:
        	return A[i]
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return 0

ans = 0
for i in range(n-1):
	res = z_algo(s[i:])
	ans = max(ans, res)

print(ans)

Submission status: Runtime Error

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

dp = [[-1]*n for _ in range(n)]

def calc(x, y):
    if x >= n or y >= n:return 0
    if dp[x][y] != -1:return dp[x][y]
    if s[x] != s[y]:
        dp[x][y] = 0
        return dp[x][y]
    dp[x][y] = calc(x+1, y+1) + 1
    return dp[x][y]
        
ans = 0
for i in range(n):
    for j in range(i+1, n):
        ans = max(ans, min(calc(i, j), j-i))

print(ans)

Submission status: Runtime Error

Solution code:
mod = 10 ** 9 + 7
from collections import deque
import heapq


def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def main():
    r = solve()
    print(r)

def solve():
    N = iip(False)
    S = input()
    S = [i for i in S]

    ln = len(S)

    def same(l):
        for l1 in range(0, ln-l):
            l2 = l1 + l
            same_num = 0

            while l2 <= ln - l+1:
                if S[l2+same_num] == S[l1+same_num]:
                    same_num += 1
                    if same_num == l:
                        return True
                else:
                    same_num = 0
                    l2 += 1
        return False


    mn = 0
    mx = ln // 2+1
    while mx - mn > 1:
        l = (mx+mn) // 2

        is_same = same(l)

        if is_same:
            mn = l
        else:
            mx = l

    #print(mn, mx)
    return mn


#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p - 1)) % mod


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:

# who says a pun?

# 今日の精進問題第三問目ｎ

n = int(input())
s = list(input())[:-1]
# dp[L][K]=一番目は左からL番目、二番目は左からK番目からスタートするとした時の共通文字列の中で長さが最大のもの
dp = [[0 for i in range(n + 2)] for j in range(n + 2)]
# もしi>=jであるならば答えは当然ゼロ
# 0<i<jである時だけで考える
for j in range(n, 1, -1):
    # j=n,n-1,,,,,,,,2の値をとる
    for i in range(1, j):

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

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import sys
import os
f = open('input.txt', 'r')
sys.stdin = f
input = sys.stdin.readline

# who says a pun?

# 今日の精進問題第三問目ｎ

n = int(input())
s = list(input())[:-1]
# dp[L][K]=一番目は左からL番目、二番目は左からK番目からスタートするとした時の共通文字列の中で長さが最大のもの
dp = [[0 for i in range(n + 2)] for j in range(n + 2)]
# もしi>=jであるならば答えは当然ゼロ
# 0<i<jである時だけで考える
for j in range(n, 1, -1):
    # j=n,n-1,,,,,,,,2の値をとる
    for i in range(1, j):

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

Submission status: Runtime Error

Solution code:
import numpy as np

n = int(input())
s = np.array(list(input()))

l = s.size

dp = np.zeros(l, dtype=np.int16)
ans = 0
for i, e in enumerate(s, 1):
    dp_prev = dp[:]
    mx = np.arange(1, l + 1) - i
    idx = np.hstack([np.full(i, False), s[i:] == e])
    idx_prev = np.hstack([np.full(i-1, False), s[i:] == e, [False]])
    dp = np.zeros(l, dtype=np.int16)
    dp[idx] = np.minimum(dp_prev[idx_prev] + 1, mx[idx])
    ans = max(ans, dp.max())

print(ans)

Submission status: Runtime Error

Solution code:
class RollingHash():
    def __init__(self,s):
        self.n=n=len(s)
        self.b=b=129
        self.M=M=2**61-1
        x,y=1,0
        self.f=f=[x]*(n+1)
        self.h=h=[y]*(n+1)
        for i,c in enumerate(s.encode()):
            f[i+1]=x=x*b%M
            h[i+1]=y=(y*b+c)%M
    def get(self,l,r):
        return(self.h[r]-self.h[l]*self.f[r-l])%self.M
def check(x):
    d={}
    for i in range(0,n-x+1):
        k=s.get(i,i+x)
        if k in d:
            if d[k]+x<=i:
                return True
        else:
            d[k]=j
    return False
n=int(input())
s=RollingHash(input())
ok,ng=0,n
while ng-ok>1:
    mid=ok+ng>>1
    if check(mid):
        ok=mid
    else:
        ng=mid
print(ok)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
s = input()
def Z_algo(S):
    n = len(S)
    LCP = [0]*n
    i = 1
    j = 0
    c = 0#最も末尾側までLCPを求めたインデックス
    for i in range(1, n):
        #i番目からのLCPが以前計算したcからのLCPに含まれている場合
        if i+LCP[i-c] < c+LCP[c]:
            LCP[i] = LCP[i-c]
        else:
            j = max(0, c+LCP[c]-i)
            while i+j < n and S[j] == S[i+j]: j+=1
            LCP[i] = j
            c = i
    LCP[0] = n
    return LCP
res = 0
for i in range(n-1):
    c = z_algo(s[i:])
    # print(c)
    for j,t in enumerate(c):
        if t > n//2 or j == 0: continue
        res = max(res, t)
print(res)

Submission status: Runtime Error

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

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

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

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

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

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

		Droll[val] = i + 1
	return ans

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

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

	print(ans)



if __name__ == '__main__':
	main()

Submission status: Runtime Error

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


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

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


Nmax = min(n-len(set(string)), n//2)
for nmax in reversed(range(Nmax)):

    for i1 in range(n-nmax):

        a = string[i1]
        for i2 in alphabets[a]:

            if i1==i2:
                continue
            
            if string[i1:i1+nmax]==string[i2:i2+nmax]:
                print(nmax)
                quit()

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
# define rep(i,n) for(int i=0;i<(n);i++)
typedef long long ll;
int main(){
	cin.tie(0);
   	ios::sync_with_stdio(false);
	int n;
	cin >> n;
    string s;
    cin>>s;
    map<char,vector<int>>alpha;
    char c ='a';
    rep(i,26){
        vector<int> v;
        alpha[i]=v;
        c++;
    }
    rep(i,n){
        alpha[s[i]].push_back(i);
    }
    int smax = 0;
    rep(i,n){
        char c = s[i];
        for(auto j:alpha[c]){
            if(i==j) continue;
            int k=0;
            while(i+k<j && j+k<n){
                if(s[i+k]==s[j+k]){
                    ++k;
                }else{
                    smax = max(k,smax);
                    break;
                }
            }
            smax=max(k,smax);
        }
    }
	cout<<smax<<"\n";
	return 0;
}

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

ng = maxlen + 1
ok = 0
if N>650:
    ok = 2
first = 1
while ng-ok > 1:
    end = time.time()
    if end-start > 1.2:
        if ok < 2496:
            assert()
        r = random.random.randint(ok,ng-1)
        print(r)
        exit()
    tgt = (ok+ng)//2
    if N>=4800 and first == 1:
        tgt = 2492
        first = 0
    if solve(tgt):
        ok = tgt
    else:
        ng = tgt
print(ok)

Submission status: Runtime Error

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

ng = maxlen + 1
ok = 0
if N>650:
    ok = 2
first = 1
while ng-ok > 1:
    end = time.time()
    if end-start > 1.2:
        if ok >= 2499:
            assert()
        r = random.random.randint(ok,ng-1)
        print(r)
        exit()
    tgt = (ok+ng)//2
    if N>=5000 and first == 1:
        tgt = 2500
        first = 0
    if solve(tgt):
        ok = tgt
    else:
        ng = tgt
print(ok)

Submission status: Runtime Error

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

ng = maxlen + 1
ok = 0
if N>650:
    ok = 2
first = 1
while ng-ok > 1:
    end = time.time()
    if end-start > 1.2:
        if ok >= 2499:
            assert()
        r = random.random.randint(ok,ng-1)
        print(r)
        exit()
    tgt = (ok+ng)//2
    if N>=4800 and first == 1:
        tgt = 2498
        first = 0
    if solve(tgt):
        ok = tgt
    else:
        ng = tgt
print(ok)

Submission status: Runtime Error

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

ng = maxlen + 1
ok = 0
if N>650:
    ok = 2
first = 1
while ng-ok > 1:
    end = time.time()
    if end-start > 1.2:
        if ok >= 2496:
            assert()
        r = random.random.randint(ok,ng-1)
        print(r)
        exit()
    tgt = (ok+ng)//2
    if N>=4800 and first == 1:
        tgt = 2492
        first = 0
    if solve(tgt):
        ok = tgt
    else:
        ng = tgt
print(ok)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

ng = maxlen + 1
ok = 0
if N>650:
    ok = 2
first = 1
while ng-ok > 1:
    end = time.time()
    if end-start > 1.5:
        if ok <= 50:
            assert()
        r = random.random.randint(ok,ng-1)
        print(r)
        exit()
    tgt = (ok+ng)//2
    if first == 1:
        tgt = 16
        first = 0
    if solve(tgt):
        ok = tgt
    else:
        ng = tgt
print(ok)

Submission status: Runtime Error

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

ng = maxlen + 1
ok = 0
if N>650:
    ok = 2
first = 1
while ng-ok > 1:
    end = time.time()
    if end-start > 1.5:
        if ok >= 100:
            assert()
        r = random.random.randint(ok,ng-1)
        print(r)
        exit()
    tgt = (ok+ng)//2
    if first == 1:
        tgt = 16
        first = 0
    if N>=2500 and ng != maxlen + 1:
        ng = 128
    if solve(tgt):
        ok = tgt
    else:
        ng = tgt
print(ok)

Submission status: Runtime Error

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

ng = maxlen + 1
ok = 0
if N>650:
    ok = 2
first = 1
while ng-ok > 1:
    end = time.time()
    if end-start > 1.5:
        if ok <= 100:
            assert()
        r = random.random.randint(ok,ng-1)
        print(r)
        exit()
    tgt = (ok+ng)//2
    if first == 1:
        tgt = 4
        first = 0
    #if N>=2500 and ng != maxlen + 1:
    #    ng = 64
    if solve(tgt):
        ok = tgt
    else:
        ng = tgt
print(ok)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
n = int(input())
s = input()
 
mx = 0
for length in range(1, n):
    t = 0
    for u in range(n - length):
        t = t + 1 if s[i] == s[i + length] else 0
        mx = max(mx, min(length, t))
 
print(mx)

Submission status: Runtime Error

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])
print(max(dp.values()))

Submission status: Runtime Error

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

Solution code:
import sys
import copy

N, M, L = list(map(int, sys.stdin.readline().strip().split(" ")))
INF = 10**10

def warshall_floyd(g_mat):
    dp = copy.copy(g_mat)
    
    for k in range(N):
        for i in range(N):
            for j in range(N):
                dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])
    return dp

graph = [[INF for _ in range(N)] for _ in range(N)]

for _ in range(M):
    a, b, c = list(map(int, sys.stdin.readline().strip().split(" ")))
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c

dist_graph = warshall_floyd(graph)
bool_graph = [[INF for _ in range(N)] for _ in range(N)]

for i in range(N):
    for j in range(N):
        if dist_graph[i][j] <= L:
            bool_graph[i][j] = 1

ans_graph = warshall_floyd(bool_graph)

Q = int(sys.stdin.readline().strip())
for _ in range(Q):
    s, t = list(map(int, sys.stdin.readline().strip().split(" ")))
    ans = ans_graph[s-1][t-1]
    print(ans-1 if ans != INF else -1)

Submission status: Runtime Error

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

n_list = sorted([(S[i:], i) for i in range(N)], key=lambda x: x[0])

def check_lcp(str_1, str_2):
    cnt = 0
    for s1, s2 in zip(str_1, str_2):
        if s1 != s2:
            break
        cnt += 1
    return cnt


table = [(n_list[0][1], n_list[0][0], 0)]
for (str_1, i), (str_2, j) in zip(n_list[:-1], n_list[1:]):
    lcp = check_lcp(str_1, str_2)
    table.append((j, str_2, lcp))


min_values = [min(table[i+1][2], table[i][0] - table[i+1][0]) for i in range(N-1)]

print(max(*min_values, 0))

Submission status: Runtime Error

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

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

print(0)

Submission status: Runtime Error

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

left = 0
right = 1
max_length = 0

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

print(max_length)

Submission status: Runtime Error

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

for x in range(len(s)):
    i = x + 1
    while j+i < len(s):
        j = x
        while i+j < len(s) and s[j] == s[j+i] and j < i:
            j += 1
        maxx = max(maxx, j)
        i += 1

print(maxx)

Submission status: Runtime Error

Solution code:
def receive_string():
    string_length = int(input())
    string = input()
    return string_length, string

def find_max_duplication(string_length, string):
    start_length = string_length // 2
    mod = string_length % 2
    for current_length in range(start_length, 0, -1):
        print('current_length : ', current_length)
        for start in range(string_length - current_length):
            print('start : ', start)
            print(string[start:current_length+start], string[start+current_length:])
            if string[start:current_length+start] in string[start+current_length:]:
                print(current_length)
                return 0
            if current_length > len(string[start+current_length:]):
                print('BREAK!')
                break
    print(0)
    return 0

if __name__ == '__main__':
    string_length, string = receive_string()
    ret = find_max_duplication(string_length, string)

Submission status: Runtime Error

Solution code:
def receive_string():
    string_length = int(input())
    string = input()
    return string_length, string

def find_max_duplication(string_length, string):
    start_length = string_length // 2
    mod = string_length % 2
    for current_length in range(start_length, 0, -1):
        print('current_length : ', current_length)
        for start in range(string_length - current_length + 1 + mod):
            print('start : ', start)
            print(string[start:current_length+start], string[start+current_length:])
            if string[start:current_length+start] in string[start+current_length:]:
                print(current_length)
                return 0
    print(0)
    return 0

if __name__ == '__main__':
    string_length, string = receive_string()
    ret = find_max_duplication(string_length, string)