Problem:


Score : 500 points

Problem Statement

Given is a string S of length N.

Find the maximum length of a non-empty string that occurs twice or more in S as contiguous substrings without overlapping.

More formally, find the maximum positive integer len such that there exist integers l_1 and l_2 ( 1 \leq l_1, l_2 \leq N - len + 1 ) that satisfy the following:

l_1 + len \leq l_2

S[l_1+i] = S[l_2+i] (i = 0, 1, ..., len - 1)

If there is no such integer len, print 0.

Constraints

2 \leq N \leq 5 \times 10^3

|S| = N

S consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the maximum length of a non-empty string that occurs twice or more in S as contiguous substrings without overlapping. If there is no such non-empty string, print 0 instead.

Sample Input 1

5
ababa

Sample Output 1

2

The strings satisfying the conditions are: a, b, ab, and ba. The maximum length among them is 2, which is the answer.
Note that aba occurs twice in S as contiguous substrings, but there is no pair of integers l_1 and l_2 mentioned in the statement such that l_1 + len \leq l_2.

Sample Input 2

2
xy

Sample Output 2

0

No non-empty string satisfies the conditions.

Sample Input 3

13
strangeorange

Sample Output 3

5



Sample input:
5
ababa


Sample output:
2

Submission status: Wrong Answer

Solution code:
import sys
# input関係の定義
sys.setrecursionlimit(200000)
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 si(): return 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, opt=2):
        self.n = len(s)
        self.opt = opt
        self.hash1 = [0] * (self.n + 1)
        self.power1 = [1] * (self.n + 1)
        if opt == 2:  # rollinghash by 2 mod
            self.hash2 = [0] * (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.power1[i + 1] = (self.power1[i] * self.__class__.BASE1) % self.__class__.MOD1
        if opt == 2:  # rollinghash by 2 mod
            for i, e in enumerate(s):
                self.hash2[i + 1] = (self.hash2[i] * self.__class__.BASE2 + ord(e)) % self.__class__.MOD2
                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
        if self.opt == 2:
            res2 = self.hash2[r] - self.hash2[l] * self.power2[r - l] % self.__class__.MOD2
            if(res2 < 0):
                res2 += self.__class__.MOD2

        if self.opt == 2:
            return (res1, res2)
        else:
            return res1
# END CUT HERE
if not __debug__:
    import io
    import random
    class MyStdin(io.TextIOWrapper):
        @classmethod
        def readline(cls):
            N = 200000
            yield "{}\n".format(N)
            yield "{}\n".format(''.join([chr(random.randint(0, 25) + ord("a")) for i in range(N)]))

def ABC131E():
    N = int(input().rstrip())
    S = input().rstrip()
    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__':
    if not __debug__:
        input = MyStdin.readline().__next__
    else:
        input = sys.stdin.readline
    import cProfile
    cProfile.run('ABC131E()', sort=1)

Submission status: Wrong Answer

Solution code:
a = 0

Submission status: Wrong Answer

Solution code:
n = int(input())
s = list(input())
x = n//2
while x > 0:
    now = 0
    now2 = x
    count = 0
    while count < x and now + 2*x < n:
        #print("A",now,now2,count,x)
        if s[now+count] == s[now+now2+count]:
            count += 1
        else:
            count = 0
            now2 += 1
        if count < x:
            if now + now2 + count == n:
                now2 = x
                now += 1
                count = 0
        #print(now,now2,count,x)
    if count == x:
        print(x)
        break
    else:
        x -= 1
if x == 0:
    print(0)

Submission status: Wrong Answer

Solution code:
#coding:utf-8

import sys

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

T = len(S)

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

Submission status: Wrong Answer

Solution code:

class ZAlgorithm(object):
    def __init__(self, s: str):
        self.lcp = self.__create_z(s)

    def __call__(self, i: int):
        return self.lcp[i]

    def __create_z(self, s: str):
        n = len(s)
        lcp = [n] + [0]*(n-1)
        l, r = 0, 0

        for t in range(1, n):
            if t>r:
                z = 0
                while t+z<n and s[0+z]==s[t+z]:
                    z += 1
                lcp[t] = z
                if z>0:
                    l, r = t, t+z-1
            else:
                p, b = t-l, r-t+1
                if lcp[p]<b:
                    lcp[t] = lcp[p]
                else:
                    i = r+1
                    while i<n and s[i]==s[i-t]:
                        i += 1
                    lcp[t] = i-t
                    l, r = t, i-1
        return lcp

def main():
    n, *s = open(0).read().split()
    a = 0
    for i in range(int(n)-1):
        ss = s[i:]
        z_algo = ZAlgorithm(ss)
        for j in range(len(ss)):
            a = max(a, min(z_algo(j), j))
    print(a)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
n = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip()


dp = [[0 for i in range(n)] for j in range(n)]
#初期条件
for j in range(1, n):
    if S[0] == S[j]:
        dp[0][j] = 1

#print(dp)

for i in range(1, n-1):
    for j in range(i+1, n):
        if S[i] ==S[j]:
            if j-1 !=i:
                dp[i][j] = dp[i-1][j-1] +1

maxp = 0
for i in range(n-1):
    for j in range(i+1, n):
        if maxp < dp[i][j]:
            maxp = dp[i][j]
#print(dp)
print(maxp)

Submission status: Wrong Answer

Solution code:
import sys
n = int(sys.stdin.readline())
S = sys.stdin.readline()


dp = [[0 for i in range(n)] for j in range(n)]
#初期条件
for j in range(1, n):
    if S[0] == S[j]:
        dp[0][j] = 1

#print(dp)

for i in range(1, n-1):
    for j in range(i+1, n):
        if S[i] ==S[j]:
            dp[i][j] = min(dp[i-1][j-1] +1, n//2)

maxp = 0
for i in range(n-1):
    for j in range(i+1, n):
        if maxp < dp[i][j]:
            maxp = dp[i][j]
#print(dp)
print(maxp)

Submission status: Wrong Answer

Solution code:
import sys
n = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip()


dp = [[0 for i in range(n)] for j in range(n)]
#初期条件
for j in range(n):
    if S[0] == S[j]:
        dp[0][j] = 1
    else:
        dp[0][j] = 0

#print(dp)

for i in range(n):
    for j in range(n):
        if S[i] ==S[j]:
            dp[i][j] = min(dp[i-1][j-1] +1, n//2)
        else:
            dp[i][j] = 0

maxp = 0
for i in range(n):
    for j in range(n):
        if maxp < dp[i][j] and i !=j:
            maxp = dp[i][j]
#print(dp)
print(maxp)

Submission status: Wrong Answer

Solution code:
import sys
n = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip()


dp = [[0 for i in range(n)] for j in range(n)]
#初期条件
for j in range(1, n):
    if S[0] == S[j]:
        dp[0][j] = 1
    else:
        dp[0][j] = 0

#print(dp)

for i in range(1, n-1):
    for j in range(i+1, n):
        if S[i] ==S[j]:
            dp[i][j] = min(dp[i-1][j-1] +1, n//2)
        else:
            dp[i][j] = 0

maxp = 0
for i in range(1, n-1):
    for j in range(i+1, n):
        if maxp < dp[i][j]:
            maxp = dp[i][j]
#print(dp)
print(maxp)

Submission status: Wrong Answer

Solution code:
import sys
n = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip()


dp = [[0 for i in range(n)] for j in range(n)]
#初期条件
for j in range(1, n):
    if S[0] == S[j]:
        dp[0][j] = 1
    else:
        dp[0][j] = 0

#print(dp)

for i in range(1, n-1):
    for j in range(i+1, n):
        if S[i] ==S[j]:
            dp[i][j] = min(dp[i-1][j-1] +1, n//2)
        else:
            dp[i][j] = 0

maxp = 0
for i in range(n-1):
    for j in range(i+1, n):
        if maxp < dp[i][j]:
            maxp = dp[i][j]
#print(dp)
print(maxp)

Submission status: Wrong Answer

Solution code:
import sys
n = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip()


dp = [[0 for i in range(n)] for j in range(n)]
#初期条件
for j in range(1, n):
    if S[0] == S[j]:
        dp[0][j] = 1

#print(dp)

for i in range(1, n):
    for j in range(i+1, n):
        if S[i] ==S[j]:
            dp[i][j] = min(dp[i-1][j-1] +1, n//2)

maxp = 0
for i in range(n):
    for j in range(i+1, n):
        if maxp < dp[i][j]:
            maxp = dp[i][j]
#print(dp)
print(maxp)

Submission status: Wrong Answer

Solution code:
import sys
n = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip()


dp = [[0 for i in range(n)] for j in range(n)]
#初期条件
for j in range(1, n):
    if S[0] == S[j]:
        dp[0][j] = 1

#print(dp)

for i in range(1, n):
    for j in range(1, n):
        if S[i] ==S[j] and i<j:
            dp[i][j] = dp[i-1][j-1] +1

maxp = 0
for i in range(n):
    for j in range(n):
        if maxp < dp[i][j] and dp[i][j]<= n/2:
            maxp = dp[i][j]

print(maxp)

Submission status: Wrong Answer

Solution code:
import sys
n = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip()


dp = [[0 for i in range(n)] for j in range(n)]
#print(dp)

for i in range(n):
    for j in range(n):
        if S[i] ==S[j] and i<j:
            dp[i][j] = dp[i-1][j-1] +1

maxp = 0
for i in range(n):
    for j in range(n):
        if maxp < dp[i][j] and dp[i][j]<= n/2:
            maxp = dp[i][j]

print(maxp)

Submission status: Wrong Answer

Solution code:
import sys
n = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip()


dp = [[0 for i in range(n)] for j in range(n)]
#print(dp)

for i in range(n):
    for j in range(n):
        if S[i] ==S[j] and i<j:
            dp[i][j] = dp[i-1][j-1] +1

maxp = 0
for i in range(n):
    for j in range(n):
        if maxp < dp[i][j] and dp[i][j]<= n//2:
            maxp = dp[i][j]

print(maxp)

Submission status: Wrong Answer

Solution code:
from collections import *
def z(s):
    n = len(s)
    a = [0]*n
    a[0] = n
    i, j = 1, 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 = int(input())
s = input()
r = 0
for i in range(1, n):
    a = z(s[i:] + s)
    c = Counter(a)
    for k in c:
        if c[k] >= 2 and r < k:
            r = k
print(r)

Submission status: Wrong Answer

Solution code:
N=int(input())
S = input()
ss = sorted([S[i:] for i in range(N)])
ans = 0
for i in range(N-1):
  a, b = ss[i:i+2]
  j = 0
  M = min(abs(len(a)-len(b)), len(a), len(b))
  while j < M:
    if a[j]!=b[j]:
      break
    j+=1
  ans = max(ans, j)
print(ans)

Submission status: Wrong Answer

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

ms = 0
for i in range(N):
    ts = 0
    for j in range(N - i):
        if S[j] == S[j+i]:
            ts += 1
            if ts > ms:
                ms = ts
            if ts == i:
                break
        else:
            ts = 0
print(ms)

Submission status: Wrong Answer

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

def z_algo(S):
    '''
    SとS[i : ](i = 0, 1, ..., N - 1)のLCP(最長共通接頭辞、longest-common prefix)の長さをO(N)で求める。
    '''
    N = len(S)
    A = [- 1]*N 
    A[0] = N 
    j = 1 
    i = 1 
    while i < N: 
        c = j + A[j] - i
        if c <= 0:
            k = 0
            while i + k < N and S[k] == S[i + k]:
                k += 1
            A[i] = k
            j = i
        elif c > 0:
            if A[i - j] == c:
                k = 0
                while i + k + c < N and S[c + k] == S[i + c + k]:
                    k += 1
                A[i] = c + k
                j = i
            elif A[i - j] > c:
                A[i] = c
                j = i
            else:
                A[i] = A[i - j]
        i += 1
    return A

res = 0
for i in range(0, N - 1):
    res = max(res, max(z_algo(S[i:])[1:]))
print(res)

Submission status: Wrong Answer

Solution code:
import math

def Z_Algorithm(S, N):
    c = 0
    A = [0] * N
    res = 0
    flag = True
    for i in range(1,N):
        # print('else', i, c)
        j = max(0, c+A[c]-i)
        while i+j < N and S[j] == S[i+j] and j < i: j += 1
        A[i] = j
        c = i
        if res < j:
            res = j
    return res

def solve():
    N = int(input())
    S = input()
    result = 0
    for i in range(N//2+1):
        Z = Z_Algorithm(S[i:], N-i)

        if result < Z:
            result = Z
            
        if result == math.ceil(N/2):
            break
        
    print(result)

Submission status: Wrong Answer

Solution code:
n=int(input())
s=input()
r=[[0]*(n+1) for _ in range(n+1)]

#print(r)

maxV=0
for i in range(n):
  for j in  range(n-i):
    ii=n-1-i
    jj=n-1-j
    if s[ii]==s[jj]:
      r[ii][jj]=min(r[ii+1][jj+1]+1,abs(ii-jj))
      maxV=max(maxV,r[ii][jj])

print(maxV)

Submission status: Wrong Answer

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[0:N]
        if res == True:
            lst.append(int(len(p_str)))
    #一番左の文字を1文字消す
    S = S[1:]
    #文字列長からマイナス1
    N = N - 1

#出力　lstのなかで一番大きい数値を返す
print(max(lst))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    s=input()
    count=0
    ans=0
    for d in range(n):
        for i in range(n-d):
            if s[i]==s[i+d]: count+=1
            else: count=0
            ans=max(min(count,d),ans)
    print(ans)
resolve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    s=input()
    count=0
    ans=0
    for d in range(1,n):
        for i in range(n-d):
            if s[i]==s[i+d]: count+=1
            else: count=0
            ans=max(min(count,d),ans)
    print(ans)
resolve()

Submission status: Wrong Answer

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):
    hash_dict = dict()
    for i in range(n-x+1):
        hash_val = rh.get_hash(i, i+x)
        if hash_val in hash_dict and i - hash_dict[hash_val] >= x:
            return True

        hash_dict[hash_val] = i
    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: Wrong Answer

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+1):
            if rh.get_hash(i, i+x) == rh.get_hash(j, j+x):
                return True
    return False


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

print(lb)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

dp = [[0] * 5005 for _ in range(5005)]

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

Submission status: Wrong Answer

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

dp = [[0] * 5005 for _ in range(5005)]

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

#output
M = N // 2
len = 0

for i in range(M):
    for j in range(N-2*M+i):
        if S[j:(j+M-i)] in S[(j+M-i+1):N]:
            len = M-i+1
            break
    else:
        continue
    break
print(len)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def bisect(l,r,f,discrete=True,left=True):
    """
    l,r: l<r int if discrete else float
    f: function defined on [l,...,r] to {False,True}
    if discrete: f defined on Z; else: R
    if left: f satisfies that there uniquely exists d such that iff i<=d then f(i)
    else: iff i>=d then f(i) is True
    return d such as those above
    """
    assert r>l
    if discrete: assert isinstance(l,int) and isinstance(r,int)
    eps=1 if discrete else 10**-12
    if (not left)^f(r): return r if left else r+1
    elif left^f(l): return l-1 if left else l
    while(r-l>eps):
        h=(l+r)//2 if discrete else (l+r)/2
        if (not left)^f(h): l=h
        else: r=h
    return h if not discrete else l if left else r

class RollingHash(object):
    """
    construct: O(N)
    get_hash: O(1)
    LCP: O(logN)
    """
    def __init__(self,S,m1=10**9+9,b1=2009,m2=10**9+7,b2=1007):
        """
        S: string
        m1>m2: prime sufficiently large
        b1,b2: base 0<bi<mi
        """
        assert m1>m2 and 0<b1<m1 and 0<b2<m2
        n=len(S)
        self.__n=n
        self.__m1=m1
        self.__m2=m2
        self.__H1,self.__H2=[0]*(n+1),[0]*(n+1)
        self.__P1,self.__P2=[1]*(n+1),[1]*(n+1)
        for i,s in enumerate(S):
            self.__H1[i+1]=(self.__H1[i]*b1+ord(s))%m1
            self.__H2[i+1]=(self.__H2[i]*b2+ord(s))%m2
            self.__P1[i+1]=self.__P1[i]*b1%m1
            self.__P2[i+1]=self.__P2[i]*b2%m2
        self.__d=0
        while(m1):
            m1//=10
            self.__d+=1

    @property
    def len(self):
        return self.__n

    def hash(self,l,r=None):
        """
        l,r: int (0<=l<=r<=n)
        return hash of S[l:r]
        """
        if r is None: r=self.len
        assert 0<=l<=r<=self.len
        return (self.__H1[r]-self.__P1[r-l]*self.__H1[l]%self.__m1)%self.__m1*(10**self.__d)+(self.__H2[r]-self.__P2[r-l]*self.__H2[l]%self.__m2)%self.__m2

    def LCP(self,l1,r1=None,rh2=None,l2=0,r2=None):
        if r1 is None: r1=self.len
        if rh2 is None: rh2=self
        if r2 is None: r2=rh2.len
        assert 0<=l1<=r1<=self.len and 0<=l2<=r2<=rh2.len
        L=0
        R=min(r1-l1,r2-l2)
        if self.hash(l1,l1+R)==rh2.hash(l2,l2+R): return R
        while(R-L>1):
            H=(L+R)//2
            if self.hash(l1,l1+H)==rh2.hash(l2,l2+H): L=H
            else: R=H
        return L

def resolve():
    n=int(input())
    S=input()
    # d=0ではtrue,d=nではfalseなので、そこでbisectする
    rh=RollingHash(S)
    def judge(d):
        # S[0:d],...,S[n-d:n]に重複があり、かつd離れているか判定
        # initialize
        J={rh.hash(i,i+d):-1 for i in range(n-d+1)}
        for i in range(n-d+1):
            h=rh.hash(i,i+d)
            if J[h]!=-1 and i-J[h]>=d: return True
            else: J[h]=i
        return False
    print(bisect(0,n,judge))

resolve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def bisect(l,r,f,discrete=True,left=True):
    """
    l,r: l<r int if discrete else float
    f: function defined on [l,...,r] to {False,True}
    if discrete: f defined on Z; else: R
    if left: f satisfies that there uniquely exists d such that iff i<=d then f(i)
    else: iff i>=d then f(i) is True
    return d such as those above
    """
    assert r>l
    if discrete: assert isinstance(l,int) and isinstance(r,int)
    eps=1 if discrete else 10**-12
    if (not left)^f(r): return r if left else r+1
    elif left^f(l): return l-1 if left else l
    while(r-l>eps):
        h=(l+r)//2 if discrete else (l+r)/2
        if (not left)^f(h): l=h
        else: r=h
    return h if not discrete else l if left else r

class RollingHash(object):
    """
    construct: O(N)
    get_hash: O(1)
    LCP: O(logN)
    """
    def __init__(self,S,m1=10**9+9,b1=1007,m2=10**9+7,b2=1009):
        """
        S: string
        m1>m2: prime sufficiently large
        b1,b2: base 0<bi<mi
        """
        assert m1>m2 and 0<b1<m1 and 0<b2<m2
        n=len(S)
        self.__n=n
        self.__m1=m1
        self.__m2=m2
        self.__H1,self.__H2=[0]*(n+1),[0]*(n+1)
        self.__P1,self.__P2=[1]*(n+1),[1]*(n+1)
        for i,s in enumerate(S):
            self.__H1[i+1]=(self.__H1[i]*b1+ord(s))%m1
            self.__H2[i+1]=(self.__H2[i]*b2+ord(s))%m2
            self.__P1[i+1]=self.__P1[i]*b1%m1
            self.__P2[i+1]=self.__P2[i]*b2%m2
        self.__d=0
        while(m1):
            m1//=10
            self.__d+=1

    @property
    def len(self):
        return self.__n

    def hash(self,l,r=None):
        """
        l,r: int (0<=l<=r<=n)
        return hash of S[l:r]
        """
        if r is None: r=self.len
        assert 0<=l<=r<=self.len
        return (self.__H1[r]-self.__P1[r-l]*self.__H1[l]%self.__m1)%self.__m1*(10**self.__d)+(self.__H2[r]-self.__P2[r-l]*self.__H2[l]%self.__m2)%self.__m2

    def LCP(self,l1,r1=None,rh2=None,l2=0,r2=None):
        if r1 is None: r1=self.len
        if rh2 is None: rh2=self
        if r2 is None: r2=rh2.len
        assert 0<=l1<=r1<=self.len and 0<=l2<=r2<=rh2.len
        L=0
        R=min(r1-l1,r2-l2)
        if self.hash(l1,l1+R)==rh2.hash(l2,l2+R): return R
        while(R-L>1):
            H=(L+R)//2
            if self.hash(l1,l1+H)==rh2.hash(l2,l2+H): L=H
            else: R=H
        return L

def resolve():
    n=int(input())
    S=input()
    # d=0ではtrue,d=nではfalseなので、そこでbisectする
    rh=RollingHash(S)
    def judge(d):
        # S[0:d],...,S[n-d:n]に重複があり、かつd離れているか判定
        # initialize
        J={rh.hash(i,i+d):-1 for i in range(n-d+1)}
        for i in range(n-d+1):
            h=rh.hash(i,i+d)
            if J[h]!=-1 and i-J[h]>=d: return True
            else: J[h]=i
        return False
    print(bisect(0,n,judge))

resolve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# input=lambda :sys.stdin.readline().rstrip()
def bisect(l,r,f,discrete=True,left=True):
    """
    l,r: l<r int if discrete else float
    f: function defined on [l,...,r] to {False,True}
    if discrete: f defined on Z; else: R
    if left: f satisfies that there uniquely exists d such that iff i<=d then f(i)
    else: iff i>=d then f(i) is True
    return d such as those above
    """
    assert r>l
    if discrete: assert isinstance(l,int) and isinstance(r,int)
    eps=1 if discrete else 10**-12
    if (not left)^f(r): return r if left else r+1
    elif left^f(l): return l-1 if left else l
    while(r-l>eps):
        h=(l+r)//2 if discrete else (l+r)/2
        if (not left)^f(h): l=h
        else: r=h
    return h if not discrete else l if left else r

class RollingHash(object):
    """
    construct: O(N)
    get_hash: O(1)
    LCP: O(logN)
    """
    def __init__(self,S,m1=10**9+9,b1=1007,m2=10**9+7,b2=1009):
        """
        S: string
        m1>m2: prime sufficiently large
        b1,b2: base 0<bi<mi
        """
        assert m1>m2 and 0<b1<m1 and 0<b2<m2
        n=len(S)
        self.__n=n
        self.__m1=m1
        self.__m2=m2
        self.__H1,self.__H2=[0]*(n+1),[0]*(n+1)
        self.__P1,self.__P2=[1]*(n+1),[1]*(n+1)
        for i,s in enumerate(S):
            self.__H1[i+1]=(self.__H1[i]*b1+ord(s))%m1
            self.__H2[i+1]=(self.__H2[i]*b2+ord(s))%m2
            self.__P1[i+1]=self.__P1[i]*b1%m1
            self.__P2[i+1]=self.__P2[i]*b2%m2
        self.__d=0
        while(m1):
            m1//=10
            self.__d+=1

    @property
    def len(self):
        return self.__n

    def hash(self,l,r=None):
        """
        l,r: int (0<=l<=r<=n)
        return hash of S[l:r]
        """
        if r is None: r=self.len
        assert 0<=l<=r<=self.len
        return (self.__H1[r]-self.__P1[r-l]*self.__H1[l]%self.__m1)%self.__m1*(10**self.__d)+(self.__H2[r]-self.__P2[r-l]*self.__H2[l]%self.__m2)%self.__m2

    def LCP(self,l1,r1=None,rh2=None,l2=0,r2=None):
        if r1 is None: r1=self.len
        if rh2 is None: rh2=self
        if r2 is None: r2=rh2.len
        assert 0<=l1<=r1<=self.len and 0<=l2<=r2<=rh2.len
        L=0
        R=min(r1-l1,r2-l2)
        if self.hash(l1,l1+R)==rh2.hash(l2,l2+R): return R
        while(R-L>1):
            H=(L+R)//2
            if self.hash(l1,l1+H)==rh2.hash(l2,l2+H): L=H
            else: R=H
        return L

def resolve():
    n=int(input())
    S=input()
    # d=0ではtrue,d=nではfalseなので、そこでbisectする
    rh=RollingHash(S)
    def judge(d):
        # S[0:d],...,S[n-d:n]に重複があり、かつd離れているか判定
        # initialize
        J={rh.hash(i,i+d):-1 for i in range(n-d+1)}
        for i in range(n-d+1):
            h=rh.hash(i,i+d)
            if J[h]!=-1 and i-J[h]>=d: return True
            else: J[h]=i
        return False
    print(bisect(0,n-1,judge))

resolve()

Submission status: Wrong Answer

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):
        if j == 0:
            idxarr.append(subarr.index(head))
        else:
            idxarr.append(subarr[idxarr[-1]+1:].index(head) + idxarr[-1]+1)
    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: Wrong Answer

Solution code:
stringCount = int(input())
targetString = input()
 
def z_algorithm(str):
  '''
  引数として渡された文字列の各 index(以下i) について
  「str と str[i:|str|-1] の最長共通接頭辞の長さ」を記録した配列 result を返します。
  
  計算量 : O(|S|) 
  Parameters
  ----------
  str : string
    対象文字列
  
  Returns
  -------
  result : array[int]
    strとstr[index:]の最長共通接頭辞の長さ
  
  '''
  strLength = len(str)
  result = [0] * strLength
  # 結果の一番最初は対象の文字列全体マッチする
  result[0] = strLength
  i = 1
  j = 0
  
  while i < strLength:
    while (i + j) < strLength and str[j] == str[j+i]:
      j += 1
    if j > (strLength // 2):
      result[i] = 0
    else:
      result[i] = j
    if j == 0:
      i += 1
      continue
    k = 1
    # 今回抽出した文字列内に、これまでの結果が含まれている場合は流用する
    while (i+k) < strLength and (k + result[k]) < j:
      result[i+k] = result[k]
      k += 1
    i += k
    j -= k
  return result
 
response = 0
for i in range(len(targetString)):
  str = targetString[i:]
  result = z_algorithm(str)
  result[0] = 0
  for i in range(len(result)):
    if (i+1) < result[i]:
      result[i] = 0
  maxCount = max(result)
  if response < maxCount:
    response = maxCount
 
print(response)