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 receive_string():
    string_length = int(input())
    string = input()
    return string_length, string

def find_max_duplication(string_length, string):
    start_length = len(string) // 2
    for current_length in range(start_length, 0, -1):
        print('current_length : ', current_length)
        for start in range(start_length - current_length + 1):
            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)

Submission status: Runtime Error

Solution code:
import math
def charToNum(char):
    return ord(char) - 96

def check(string,subLen):
    if subLen == 0: return True
    #長さsubLenの部分文字列すべてについてローリングハッシュを計算して、
    #一致するものがあるかどうかを計算する。
    # setOfRollingHash = set()
    dictOfRollingHash = {}
    totalLen = len(string)
    h = 0
    b = 1
    for i in range(subLen):
        c = string[subLen - 1 - i]
        h += charToNum(c) * b
        b *= 27
    dictOfRollingHash[h] = 0
    maxBase = math.pow(27,subLen - 1)
    for i in range(1,totalLen - subLen + 1):
        h -= maxBase * charToNum(string[i - 1])
        h *= 27
        h += charToNum(string[i + subLen - 1])
        if h in dictOfRollingHash:
            if i - dictOfRollingHash[h] >= subLen:
                return True
        else:
            dictOfRollingHash[h] = i
    return False

N = int(input())
S = input()
ok = 0
ng = N + 1
while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    if check(S,mid):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Runtime Error

Solution code:
n = int(input())
s = list(input())
ans = 0
for i in range(1,n):
    tmpans = 0
    streak = 0
    for j in range(n-i):
        #print(s[j],s[j+i])
        if s[j] == s[j+i]:
            streak += 1
        else:
            tmpans = max(tmpans,min(i,streak))
            streak = 0
    ans = max(tmpans,ans)
if len(ansl) > 0:
    print(ans)

Submission status: Runtime Error

Solution code:
#https://atcoder.jp/contests/abc141/submissions/7539109
#Z-Algorithm
n = int(input())
s = input()
 
a = ""
ans = 0
for i in range(n):
    a += s[i]
    while(len(a) > 0):
        if a in s[i+1:]:    #見つかる限りこの処理
            ans = max(ans,len(a))
            break
        else:               #ダメなら次の文字を接頭辞に、短いものは調べなくてよい
        a = a[1:]
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from typing import List, Union, Optional, AnyStr
from collections import defaultdict
# input関係の定義
sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def fi(): return float(input())
def mfi(): return map(float, input().rstrip().split())
def lmfi(): return list(map(float, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()
# template

# BEGIN CUT HERE
class RollingHash():
    BASE1 = 1007
    BASE2 = 2009
    MOD1 = 1000000007
    MOD2 = 1000000009

    def __init__(self, s: List[str]):
        self.n = len(s)
        self.hash1 = [0] * (self.n + 1)
        self.hash2 = [0] * (self.n + 1)
        self.power1 = [1] * (self.n + 1)
        self.power2 = [1] * (self.n + 1)
        for i, e in enumerate(s):
            self.hash1[i + 1] = (self.hash1[i] * self.__class__.BASE1 + ord(e)) % self.__class__.MOD1
            self.hash2[i + 1] = (self.hash2[i] * self.__class__.BASE2 + ord(e)) % self.__class__.MOD2
            self.power1[i + 1] = (self.power1[i] * self.__class__.BASE1) % self.__class__.MOD1
            self.power2[i + 1] = (self.power2[i] * self.__class__.BASE2) % self.__class__.MOD2

    def get(self, l: int, r: int):
        res1 = self.hash1[r] - self.hash1[l] * self.power1[r - l] % self.__class__.MOD1
        if(res1 < 0):
            res1 += self.__class__.MOD1
        res2 = self.hash2[r] - self.hash2[l] * self.power2[r - l] % self.__class__.MOD2
        if(res2 < 0):
            res2 += self.__class__.MOD2
        return (res1, res2)
# END CUT HERE

def ABC131E():
    N = ii()
    S = li()
    rh = RollingHash(S)
    def check(n: int):
        d = dict()
        for i in range(N - n + 1):
            p = rh.get(i, i + n)
            if p in d.keys():
                if(i - d[p] >= n):
                    return True
            else:
                d[p] = i
        return False
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if check(mid):
            ok = mid
        else:
            ng = mid
    print(ok)



if __name__ == '__main__':
    ABC131E()

Submission status: Runtime Error

Solution code:
#coding:utf-8

import sys

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

T = len(S)

for t in reversed(range(T+1)):
    i = 0
    while 0 < len(S[i:i+t-1]) and len(S[i:i+t-1]) <= len(S[i+t-1:]):
        print(S[i:i+t-1])
        if S[i:i+t-1] in S[i+t-1:]:
            print(S[i:i+t-1])
            print(len(S[i:i+t-1]))
            sys.exit()
        i += 1
print('0')

Submission status: Runtime Error

Solution code:
N = int(input())
S = input()
def Zalgo(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
res = 0
for i in range(N - 1):
    lcp = Zalgo(S[i:])
    for j in range(N - i):
        l = min(j, lcp[j])
        res = max(l, res)
print(res)

Submission status: Runtime Error

Solution code:
import math
N = int(input()) #文字列長
S = input()      #文字列
lst = []         #一致した文字列長

if N < 2:
    exit()

if not len(S) == N:
    exit()

while N >= 2:
#文字列検索　繰り返し回数
    h = math.ceil((N-1)/2)
    #文字列を抽出
    for i in range(h):
        p_str = S[0:i+1]
        #文字列検索
        res = p_str in S[i+1:N]
        if res == True:
            lst.append(int(len(p_str)))
    #一番左の文字を1文字消す
    S = S[1:]
    #文字列長からマイナス1
    N = N - 1

print(max(lst))

Submission status: Runtime Error

Solution code:
import math
N = int(input()) #文字列長
S = input()      #文字列
lst = []         #一致した文字列長

while N >= 2:
#文字列検索　繰り返し回数
    h = math.ceil((N-1)/2)
    #文字列を抽出
    for i in range(h):
        p_str = S[0:i+1]
        #文字列検索
        res = p_str in S[i+1:N]
        if res == True:
            lst.append(int(len(p_str)))
    #一番左の文字を1文字消す
    S = S[1:]
    #文字列長からマイナス1
    N = N - 1

print(max(lst))

Submission status: Runtime Error

Solution code:
class RollingHash:
    def __init__(self, s: str, base: int=1007, mod: int=10**9+7):
        self.s = s
        self.n = len(s)
        self.base = base
        self.mod = mod

        # preprocess
        self.hash_cum = [0] * (self.n + 1) # hash_cum[i] = (hash of s[:i])
        self.base_pow = [1] * (self.n + 1) # base_pow[i] = base ** i
        for i in range(self.n):
            self.hash_cum[i+1] = (self.hash_cum[i] * base + ord(s[i])) % mod
            self.base_pow[i+1] = (self.base_pow[i] * base) % mod

    def get_hash(self, l: int, r: int) -> int:
        hash_val = self.hash_cum[r] - self.hash_cum[l] * self.base_pow[r-l] % self.mod
        if hash_val < 0:
            hash_val += self.mod
        return hash_val


class RollingHashMulti:
    def __init__(self, s: str, base_list: list=[1007, 2009], mod_list: list=[10**9+7, 10**9+9]):
        self.n = len(base_list)
        self.base_list = base_list
        self.rh_list = [RollingHash(s, base_list[i], mod_list[i]) for i in range(self.n)]

    def get_hash(self, l: int, r: int) -> tuple:
        return tuple( self.rh_list[i].get_hash(l, r) for i in range(self.n) )




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

rh = RollingHashMulti(s)

def check(x):
    for i in range(n-2*x+1):
        for j in range(i+x, n-x+i):
            if rh.get_hash(i, i+x) == rh.get_hash(j, j+x):
                return True
    return False


lb = 0
ub = n // 2 + 1
while ub - lb > 1:
    mid = (ub + lb) // 2
    if check(mid):
        lb = mid
    else:
        ub = mid

print(lb)

Submission status: Runtime Error

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

solarr =[]
for i in range(n):
    solarr.append(0)
    if i == 0:
        continue
    head = s[i]
    subarr = s[:i]
    idxarr = []
    tmparr = subarr[:]
    count = subarr.count(head)
    if count == 0:
        continue
    for j in range(count):
        idxarr.append(tmparr.index(head)+len(idxarr))
        if j == count-1:
            continue
        _ = tmparr.pop(idxarr[j])
    j = 0
    while idxarr != []:
        j += 1
        for k,l in enumerate(idxarr):
            if l+j >= i or i+j >= n:
                _ = idxarr.pop(k)
                continue
            if subarr[l+j] != s[i+j]:
                _ = idxarr.pop(k)
    solarr[i] += j
        
print(max(solarr))

Submission status: Runtime Error

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

solarr =[]
for i in range(n):
    solarr.append(0)
    if i == 0:
        continue
    head = s[i]
    subarr = s[:i]
    idxarr = []
    tmparr = subarr[:]
    count = subarr.count(head)
    if count == 0:
        continue
    for j in range(count):
        idxarr.append(tmparr.index(head)+len(idxarr))
        if j == count-1:
            continue
        _ = tmparr.pop(idxarr[j])
    j = 0
    while idxarr != []:
        j += 1
        for k,l in enumerate(idxarr):
            if l+j == i or i+j == n:
                _ = idxarr.pop(k)
                continue
            if subarr[l+j] != s[i+j]:
                _ = idxarr.pop(k)
    solarr[i] += j
        
print(max(solarr))

Submission status: Runtime Error

Solution code:
N = int(input())
S = input()
k = 1
for i in range(N - 1):
    while True:
        if S[i : i + k] in S[i + k :]:
            k += 1
        else:
            break
print(l)

Submission status: Runtime Error

Solution code:
def z_algo(s):
    z = [0]*len(s)
    n = len(s)
    L = 0
    R = 0
    for i in range(1, n):
        if i > R:
            L = i
            R = i
            l = 0
            while l + L < n and s[l] == s[l + i]:
                l += 1
            z[i] = l
            if l > 0:
                R = L + l - 1
        else:
            k = i - L
            right_len = R - i + 1
            if z[k] < right_len:
                z[i] = z[k]
            else:
                L = i
                l = R + 1
                while l < n and s[l - L] == s[l]:
                        l += 1
                z[i] = l - L
                R = l - 1
    return z

ans = 0
N = int(input())
S = input()

for i in range(N):
    LCP = Z_algo(S[i:])
    for j, l in enumerate(LCP):
        tmp = min(l, j)
        ans = max(ans, tmp)
print(ans)

Submission status: Runtime Error

Solution code:
def Z_algo(S):
    n = len(S)
    z = [0]*n
    L = 0
    R = 0
    for i in range(1, n):
        if i > R:
            L = i
            R = i
            while (R < n):
                if s[R - L] == s[R]:
                    z[i] = R - L + 1
                else:
                    break
                R += 1
        else:
            k = i - L
            # print(k)
            if z[k] < R - i + 1:
                z[i] = z[k]
            else:
                L = i
                while (R < n):
                    if s[R - L] == s[R]:
                        z[i] = R - L + 1
                    else:
                        break
                    R += 1
    return z
  
ans = 0
N = int(input())
S = input()
for i in range(N):
    LCP = Z_algo(S[i:])
    for j, l in enumerate(LCP):
        tmp = min(l, j)
        ans = max(ans, tmp)
print(ans)

Submission status: Runtime Error

Solution code:
n=input()
S= input()
C=[]
k=0
for i in range(n):
    for j in range(i+1, n):
        if S[i]==S[j]:
            C.append([i,j])
while C != [] :
    k+=1
    t=[]
    for c in C:
        if c[0]+k < c[1] and c[1]+k  in range(len(S)) and S[c[0]+k]==S[c[1]+k]:
            t.append(c)
    C=t        
print(k)

Submission status: Runtime Error

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

A=[0 for i in range(length-max_num)]
length=len(S)
max_num=0
for c in range(len(S)):

    for i in range(1,length-max_num):
        if i+ A[i] < c+A[c]:
            A[i] = A[i-c]
        else:
            j=max(0,c+A[c]-i)
            while i+j<length and S[j]==S[i+j]:
                j+=1
            A[i]=j
            if max_num<A[i] and i>=A[i]:
                max_num = A[i]
print(max_num)

Submission status: Runtime Error

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

A=[0 for i in range(length-max_num)]

for c in range(len(S)):

    for i in range(1,length-max_num):
        if i+ A[i] < c+A[c]:
            A[i] = A[i-c]
        else:
            j=max(0,c+A[c]-i)
            while i+j<length and subS[j]==subS[i+j]:
                j+=1
            A[i]=j
            if max_num<A[i] and i>=A[i]:
                max_num = A[i]
print(max_num)

Submission status: Runtime Error

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

# Zアルゴリズムで解く

c=0
max_num=0
A=[0 for i in range(length-max_num)]

for sub in range(len(S)):
    subS = S[sub:]
    length = len(subS)
    if length <= max_num:
        break

    for i in range(1,length-max_num):
        if i+ A[i-c] < c+A[c]:
            A[i] = A[i-c]
        else:
            j=max(0,c+A[c]-i)
            while i+j<length and subS[j]==subS[i+j]:
                j+=1
            A[i]=j
            if max_num<A[i] and i>=A[i]:
                max_num = A[i]
print(max_num)

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
S = list(map(ord, list(input())))
mod = 10**9+7
base = 1234
power = [1]*(N+1)
for i in range(1, N+1):
    power[i] = power[i-1]*base%mod
def check(m):
    if N-m<m:
        return False
    res = 0
    for i in range(m):
        res+=S[i]*power[m-i-1]
        res%=mod
    dic = {res:0}
    for i in range(N-m):
        res = ((res-S[i]*power[m-1])*base
                             +S[i+m])%mod
        if res in dic.keys():
            index = dic[res]
            if index +m<=i+1:
                return True
        else:
            dic[res] = i+1
    return False
ok = 0
ng = N+1
while ng-ok>1:
    mid = (ok+ng)//2
    
    if check(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
S = list(map(ord, list(input())))
mod = 10**9+7
base = 100
power = [1]*(N+1)
for i in range(1, N+1):
    power[i] = power[i-1]*base%mod
def check(m):
    if N-m<m:
        return False
    rolling_hash = [0]*(N-m+1)
    res = 0
    for i in range(m):
        res+=S[i]*power[m-i-1]
        res%=mod
    rolling_hash[0] = res
    dic = {res:0}
    for i in range(N-m):
        tmp = ((rolling_hash[i]-S[i]*power[m-1])*base
                             +S[i+m])%mod
        rolling_hash[i+1] = tmp
        if tmp in dic.keys():
            index = dic[tmp]
            if index +m<=i+1:
                return True
        else:
            dic[rolling_hash[i+1]] = i+1
    return False
ok = 0
ng = N+1
while ng-ok>1:
    mid = (ok+ng)//2
    if check(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Runtime Error

Solution code:
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
ans = 0
for i in range(N):
    LCP = Z_algo(S[i:])
    for j, l in enumerate(LCP):
        tmp = min(l, j-i+1)
        ans = max(ans, tmp)
print(ans)

Submission status: Runtime Error

Solution code:
inf = float('inf')

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

dp = [[-inf] * N for _ in range(N)]

def rec(i, j):
    if not (0 <= i < j < N):
        return 0
    if dp[i][j] != -inf:
        return dp[i][j]
    res = 0
    if S[i] == S[j] and i + rec(i+1, j+1) < j:
        res = max(res, rec(i+1, j+1) + 1, rec(i+1, j), rec(i, j+1))
    else:
        res = max(res, rec(i+1, j), rec(i+1, j))
    dp[i][j] = res
    return res

ans = 0

for i in range(N):
    for j in range(i+1, N):
        ans = max(ans, rec(i, j))

print(ans)

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline

def main():
    def hash_ini(t):
        h = t[0]
        hash_table[0] = h
        p = 1
        for i in range(1, len(t)+1):
            h = hash_table[i] = (h * base + t[i]) % hash_md
            p = pw[i] = p * base % hash_md

    def hash(s):
        res = 0
        for i, c in enumerate(s[::-1]):
            res = (res + pw[i] * (ord(c) - ord_a)) % hash_md
        return res

    # インデックスがi以上j未満の文字列のハッシュ
    def hash_ij(i, j):
        return (hash_table[j] - hash_table[i] * pw[j - i]) % hash_md

    n = int(input())
    s = input()[:-1]

    # 初期化
    base = 29
    hash_md = pow(3, 19)
    ord_a = ord('a')
    t = [ord(c) - ord_a for c in s]
    hash_table = [0] * (len(t)+1)
    pw = [1] * (len(t)+1)
    hash_ini(t)

    ok = 0
    ng = n // 2 + 1
    while ok + 1 < ng:
        br = False
        w = (ok + ng) // 2
        for i in range(n - 2 * w + 1):
            ptn = hash_ij(i, i + w)
            for j in range(i + w, n - w + 1):
                if hash_ij(j, j + w) == ptn:
                    ok = w
                    br = True
                    break
            if br: break
        else:
            ng = w
    print(ok)

main()

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline

def main():
    def hash_ini(t):
        h = t[0]
        hash_table[0] = h
        p = 1
        for i in range(1, len(t)):
            h = hash_table[i] = (h * base + t[i]) % hash_md
            p = pw[i] = p * base % hash_md

    def hash(s):
        res = 0
        for i, c in enumerate(s[::-1]):
            res = (res + pw[i] * (ord(c) - ord_a)) % hash_md
        return res

    # インデックスがi以上j未満の文字列のハッシュ
    def hash_ij(i, j):
        return (hash_table[j] - hash_table[i] * pw[j - i]) % hash_md

    n = int(input())
    s = input()[:-1]

    # 初期化
    base = 29
    hash_md = pow(3, 19)
    ord_a = ord('a')
    t = [ord(c) - ord_a for c in s]
    hash_table = [0] * len(t)
    pw = [1] * len(t)
    hash_ini(t)

    ok = 0
    ng = n // 2 + 1
    while ok + 1 < ng:
        br = False
        w = (ok + ng) // 2
        for i in range(n - 2 * w + 1):
            ptn = hash_ij(i, i + w)
            for j in range(i + w, n - w + 1):
                if hash_ij(j, j + w) == ptn:
                    ok = w
                    br = True
                    break
            if br: break
        else:
            ng = w
    print(ok)

main()

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline

def main():
    def hash_ij(i, j):
        if i + j == 0: return 0
        res = hash_table[i][j]
        if res == -1:
            if i > 0:
                res = (hash_ij(i - 1, j - 1) * base + target[j - 1]
                       - target[i - 1] * power(j - i)) % hash_md
            else:
                res = (hash_ij(i, j - 1) * base + target[j - 1]) % hash_md
            hash_table[i][j] = res
        return res

    def power(e):
        if e == 0: return 1
        res = pw[e]
        if res == -1:
            res = pw[e] = power(e - 1) * base % hash_md
        return res

    n = int(input())
    target = input()[:-1]

    # 初期化
    base = 29  # 文字種以上の素数
    hash_md = pow(3, 37)  # 2のべき乗以外がよい
    ord_a = ord('a')
    target = [ord(c) - ord_a for c in target]
    hash_table = [[-1] * (len(target) + 1) for _ in range(len(target))]
    pw = [-1] * (len(target) + 1)

    ok = 0
    ng = n // 2 + 1
    while ok + 1 < ng:
        br = False
        w = (ok + ng) // 2
        for i in range(n - 2 * w + 1):
            ptn = hash_ij(i, i + w)
            for j in range(i + w, n - w + 1):
                if hash_ij(j, j + w) == ptn:
                    ok = w
                    br = True
                    break
            if br: break
        else:
            ng = w
    print(ok)

main()

Submission status: Runtime Error

Solution code:
class Rori:
  B1 = 1009
  B2 = 1007
  MOD1 = 10 ** 9 + 7
  MOD2 = 10 ** 9 + 9
  H1, H2 = None, None
  P1, P2 = None, None
  def __init__(s, L):
    n = len(L) + 1
    s.H1 = [0] * n
    s.H2 = [0] * n
    s.P1 = [1] * n
    s.P2 = [1] * n
    for i in range(n - 1):
      S = ord(L[i]) - ord('a') + 1
      s.H1[i + 1] = (s.H1[i] * s.B1 + S) % s.MOD1
      s.H2[i + 1] = (s.H2[i] * s.B2 + S) % s.MOD2
      s.P1[i + 1] = s.P1[i] * s.B1 % s.MOD1
      s.P2[i + 1] = s.P2[i] * s.B2 % s.MOD2
  def hashLR(s, l, r):
    t = ((s.H1[r] - s.H1[l] * s.P1[r - l]) % s.MOD1 + s.MOD1) % s.MOD1
    k = ((s.H2[r] - s.H2[l] * s.P2[r - l]) % s.MOD2 + s.MOD2) % s.MOD2
    return (t, k)


class AVL:
  import sys
  sys.setrecursionlimit(1000000)
  class Node:
    def __init__(s, k):
      s.k = k
      s.l = None
      s.r = None
      s.d = 1
  def __init__(s):
    s.x = None
  def l_rot(s, z):
    y = z.r
    t = y.l
    y.l, z.r = z, t
    z.d = s.get_depth(z)
    y.d = s.get_depth(y)
    return y
  def r_rot(s, z):
    y = z.l
    t = y.r
    y.r, z.l = z, t
    z.d = s.get_depth(z)
    y.d = s.get_depth(y)
    return y
  def depth(s, node):
    if not node:
      return 0
    else:
      return node.d
  def get_depth(s, node):
    return 1 + max(s.depth(node.l), s.depth(node.r))
  def add(s, k):
    s.x = s.add_sub(s.x, k)
  def add_sub(s, node, k):
    if not node:
      return s.Node(k)
    elif node.k == k:
      return node
    elif node.k > k:
      node.l = s.add_sub(node.l, k)
    else:
      node.r = s.add_sub(node.r, k)
    node.d = s.get_depth(node)
    bal = s.depth(node.l) - s.depth(node.r)
    if bal > 1:
      if node.l.k > k:
        return s.r_rot(node)
      else:
        node.l = s.l_rot(node.l)
        return s.r_rot(node)
    elif bal < -1:
      if node.r.k < k:
        return s.l_rot(node)
      else:
        node.l = s.r_rot(node.l)
        return s.l_rot(node)
    return node
  def check(s, k):
    return s.check_sub(k, s.x)
  def check_sub(s, k, node):
    if node == None:
      return False
    if node.k == k:
      return True
    if node.k > k:
      return s.check_sub(k, node.l)
    else:
      return s.check_sub(k, node.r)

def hersCode(n):
  ok = 0
  ng = n
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if nasu(mid):
      ok = mid
    else:
      ng = mid
  return ok

def nasu(n):
  L = [None] * (N - n + 1)
  for i in range(len(L)):
    L[i] = R.hashLR(i, i + n)
  T = AVL()
  T.add(L[0])
  for i in range(n, len(L)):
    if T.check(L[i]):
      return True
    T.add(L[i - n + 1])
  return False

def honya(x, y, n):
  for i in range(n):
    if S[x + i] != S[y + i]:
      return i
  return n

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

R = Rori(S)
print(hersCode(N))

Submission status: Runtime Error

Solution code:
class Rori:
  B1 = 1009
  B2 = 1007
  MOD1 = 10 ** 9 + 7
  MOD2 = 10 ** 9 + 9
  H1, H2 = None, None
  P1, P2 = None, None
  def __init__(s, L):
    n = len(L) + 1
    s.H1 = [0] * n
    s.H2 = [0] * n
    s.P1 = [1] * n
    s.P2 = [1] * n
    for i in range(n - 1):
      S = ord(L[i]) - ord('a') + 1
      s.H1[i + 1] = (s.H1[i] * s.B1 + S) % s.MOD1
      s.H2[i + 1] = (s.H2[i] * s.B2 + S) % s.MOD2
      s.P1[i + 1] = s.P1[i] * s.B1 % s.MOD1
      s.P2[i + 1] = s.P2[i] * s.B2 % s.MOD2
  def hashLR(s, l, r):
    t = ((s.H1[r] - s.H1[l] * s.P1[r - l]) % s.MOD1 + s.MOD1) % s.MOD1
    k = ((s.H2[r] - s.H2[l] * s.P2[r - l]) % s.MOD2 + s.MOD2) % s.MOD2
    return (t, k)

class AVL:
  import math
  class Node:
    def __init__(s, k):
      s.k = k
      s.l = None
      s.r = None
      s.d = 1
  def __init__(s):
    s.x = None
  def l_rot(s, z):
    y = z.r
    t = y.l
    y.l, z.r = z, t
    z.d = s.get_depth(z)
    y.d = s.get_depth(y)
    return y
  def r_rot(s, z):
    y = z.l
    t = y.r
    y.r, z.l = z, t
    z.d = s.get_depth(z)
    y.d = s.get_depth(y)
    return y
  def depth(s, node):
    if not node:
      return 0
    else:
      return node.d
  def get_depth(s, node):
    return 1 + max(s.depth(node.l), s.depth(node.r))
  def add(s, k):
    s.x = s.add_sub(s.x, k)
  def add_sub(s, node, k):
    if not node:
      return s.Node(k)
    elif node.k == k:
      return node
    elif node.k > k:
      node.l = s.add_sub(node.l, k)
    else:
      node.r = s.add_sub(node.r, k)
    node.d = s.get_depth(node)
    bal = s.depth(node.l) - s.depth(node.r)
    if bal > 1:
      if node.l.k > k:
        return s.r_rot(node)
      else:
        node.l = s.l_rot(node.l)
        return s.r_rot(node)
    elif bal < -1:
      if node.r.k < k:
        return s.l_rot(node)
      else:
        node.l = s.r_rot(node.l)
        return s.l_rot(node)
    return node
  def check(s, k):
    return s.check_sub(k, s.x)
  def check_sub(s, k, node):
    if node == None:
      return False
    if node.k == k:
      return True
    if node.k > k:
      return s.check_sub(k, node.l)
    else:
      return s.check_sub(k, node.r)

def hersCode(n):
  ok = 0
  ng = n
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if nasu(mid):
      ok = mid
    else:
      ng = mid
  return ok

def nasu(n):
  L = [None] * (N - n + 1)
  for i in range(len(L)):
    L[i] = R.hashLR(i, i + n)
  T = AVL()
  T.add(L[0])
  for i in range(n, len(L)):
    if T.check(L[i]):
      return True
    T.add(L[i - n + 1])
  return False

def honya(x, y, n):
  for i in range(n):
    if S[x + i] != S[y + i]:
      return i
  return n

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

R = Rori(S)
print(hersCode(N))

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
#include <boost/range/irange.hpp>
using namespace std;
 
using ll = long long;
using boost::irange;
 
int main(){
 
    int N;
    string S;
    cin >> N >> S;

    int ans = 0;
    int index = 0;

    for(int i : irange(1,N-1)){
        auto it = search(S.begin() + i, S.end(), S.begin()+index, S.begin() + i);
        if (it != S.end()){
            ans = i - index;
        }
        else{
            index++;
        }
    }
    cout << ans << endl;
 
    return 0;
}

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict,deque
from heapq import heappush,heappop,heapify

N=input()
AL=defaultdict(lambda: set())
IN=defaultdict(lambda: 0)
BEGIN=set()

for i in range(N):
	A=map(int, sys.stdin.readline().split())
	for j in range(N-2):
		x=i+1
		x_next=i+1
		y=A[j]
		y_next=A[j+1]
		#print x,y,x_next,y_next
		if x>y: x,y=y,x
		if x_next>y_next: x_next,y_next=y_next,x_next
		IN[(x_next,y_next)]+=1
		AL[(x,y)].add((x_next,y_next))

		if j==0:
			BEGIN.add((x,y))

hq=[]

for x,y in BEGIN:
	if IN[(x,y)]==0:
		heappush(hq, (1,x,y))


DAY=defaultdict(lambda: 1)	#距離

ans=-1
while hq:
	cost,fro_x,fro_y=heappop(hq)
	fro=(fro_x,fro_y)
	for to in AL[fro]:
		IN[to]-=1
		alt=DAY[fro]+1
		if DAY[to]<alt and IN[to]==0:
			ans=max(ans,alt)
			DAY[to]=alt
			heappush(hq,(alt,to[0],to[1]))

print ans

Submission status: Runtime Error

Solution code:
'''Z algorithm https://snuke.hatenablog.com/entry/2014/12/03/214243'''
N = int(input())
S = input()
dp = [[0]*1001 for _ in range(1001)]

def solve(s1, s2):
  for i in range(len(s1)):
    for j in range(len(s2)):
      if s1[i] == s2[j]:
        dp[i+1][j+1] = dp[i][j] + 1
      else:
        dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
  return dp[len(s1)][len(s2)]

ans = 0
for i in range(1, N):
  ans = max(ans, solve(S[0:i], S[i:]))
print(ans)

Submission status: Runtime Error

Solution code:
'''Z algorithm https://snuke.hatenablog.com/entry/2014/12/03/214243'''
N = int(input())
S = input()

def solve(s1, s2):
  dp = [[0]*1001 for _ in range(1001)]
  for i in range(len(s1)):
    for j in range(len(s2)):
      if s1[i] == s2[j]:
        dp[i+1][j+1] = dp[i][j] + 1
      else:
        dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
  return dp[len(s1)][len(s2)]

ans = 0
for i in range(1, N):
  ans = max(ans, solve(S[0:i], S[i:]))
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
S = input()
sride = 1
count = 0
max_num = 0
for i in range(N-1):
  for j in range(N-sride):
    if S[j] == S[j+sride]:
      count += 1
      max_num = max(max_num, count)
    else:
      count = 0
    if count == sride:
      max_num = max(max_nuzm, count)
      break
  sride += 1
  count = 0
print(max_num)

Submission status: Runtime Error

Solution code:
N = int(input())
S = input()
max_range = N//2
count_list = [[0 for j in range 50005] for i in range 5005]
print(count_list.shape)
print(count_list)

Submission status: Runtime Error

Solution code:
def resolve():
    import sys
    input=sys.stdin.readline
    N = int(input().rstrip())
    S = input().rstrip()

    def z_algo(s):
        """
        param s:str
        return list of int with length len(s)
        """
        # initialization
        n=len(s)
        z=[0]*n
        z[0]=n
        # construct
        L,R=0,0
        for i in range(1,n):
            if i>R: # 過去の結果が全く使えない
                L=R=i
                while(R<n and s[R-L]==s[R]): R+=1
                z[i]=R-L
                R-=1 # 0-indexedでiと比較するため
            elif z[i-L]<R-i+1:
                z[i]=z[i-L]
            else:
                L=i
                R+=1 # Rまでは確定しているので、R+1から確認
                while(R<n and s[R-L]==s[R]): R+=1
                z[i]=R-L
                R-=1
        return z

    ans = 0
    for i in range(N-1):
        z = z_algo(S[i:])
        for i, _z in enumerate(z):
            ans=max(ans,min(j,z[j]))
    print(ans)

resolve()