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:
from collections import deque

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

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


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

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

else:
    print(0)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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


n = int(input())
s = input()
rh = RollingHash(s)

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

else:
    print(0)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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


n = int(input())
s = input()
rh = RollingHash(s)

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

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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


n = int(input())
s = input()
rh = RollingHash(s)

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

Submission status: Wrong Answer

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

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

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

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

ans = 0
for i in range(N):
    for j in range(N):
        ans = max(ans, min(dp[i][j], j-i))

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
s = input()
### ローリングハッシュ rolling hash
import random
M = 10**9+7
# M = 1<<63 - 1
# M = 92709568269121

# b = random.choice(range(2,100))
b = 1234
def rhash_list(s):
    l = [chr(v) for v in range(ord("a"), ord("z")+1)]
    d = {c:i+2 for i,c in enumerate(l)}
    ans = 0
    v = 1
    l = [0]
    for item in s:
        ans += d[item]*v
        v *= b
        ans %= M
        v %= M
        l.append(ans)
    return l
l = rhash_list(s)
if len(set(s))==n:
    ans = 0
else:
    binv = pow(b,M-2,M)
    pows = [None]*(n+1)
    v = 1
    for j in range(n+1):
        pows[j] = v
        v *= binv
        v %= M
#         pow(binv,j,M)
    ans = 0
    from collections import defaultdict
    for i in range(n//2, 0, -1):
        d = defaultdict(list)
        for j in range(n-i+1):
            d[((l[j+i]-l[j])*pows[j])%M].append(j)
        for v in d.values():
            if v[0]+i<=v[-1]:
                ans = i
                break
        if ans>0:
            break
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
s = input()
### ローリングハッシュ rolling hash
import random
M = 10**9+7
# M = 1<<63 - 1
# M = 92709568269121

b = random.choice(range(2,100))
def rhash_list(s):
    l = [chr(v) for v in range(ord("a"), ord("z")+1)]
    d = {c:i+2 for i,c in enumerate(l)}
    ans = 0
    v = 1
    l = [0]
    for item in s:
        ans += d[item]*v
        v *= b
        ans %= M
        v %= M
        l.append(ans)
    return l
l = rhash_list(s)
if len(set(s))==n:
    ans = 0
else:
    binv = pow(b,M-2,M)
    pows = [None]*(n+1)
    v = 1
    for j in range(n+1):
        pows[j] = v
        v *= binv
        v %= M
#         pow(binv,j,M)
    ans = 0
    from collections import defaultdict
    for i in range(n//2, 0, -1):
        d = defaultdict(list)
        for j in range(n-i+1):
            d[((l[j+i]-l[j])*pows[j])%M].append(j)
        for v in d.values():
            if v[0]+i<=v[-1]:
                ans = i
                break
        if ans>0:
            break
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
s = input()
### ローリングハッシュ rolling hash
import random
# M = 10**9+7
# M = 1<<63 - 1
M = 92709568269121

b = random.choice(range(2,100))
def rhash_list(s):
    l = [chr(v) for v in range(ord("a"), ord("z")+1)]
    d = {c:i+2 for i,c in enumerate(l)}
    ans = 0
    v = 1
    l = [0]
    for item in s:
        ans += d[item]*v
        v *= b
        ans %= M
        v %= M
        l.append(ans)
    return l
l = rhash_list(s)
if len(set(s))==n:
    ans = 0
else:
    binv = pow(b,M-2,M)
    pows = [None]*(n+1)
    v = 1
    for j in range(n+1):
        pows[j] = v
        v *= binv
        v %= M
#         pow(binv,j,M)
    ans = 0
    from collections import defaultdict
    for i in range(n//2, 0, -1):
        d = defaultdict(list)
        for j in range(n-i+1):
            d[((l[j+i]-l[j])*pows[j])%M].append(j)
        for v in d.values():
            if v[0]+i<=v[-1]:
                ans = i
                break
        if ans>0:
            break
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
s = input()
### ローリングハッシュ rolling hash
import random
# M = 10**9+7
M = (1<<63) - 1

b = random.choice(range(1,M))
def rhash_list(s):
    l = [chr(v) for v in range(ord("a"), ord("z")+1)]
    d = {c:i+2 for i,c in enumerate(l)}
    ans = 0
    v = 1
    l = [0]
    for item in s:
        ans += d[item]*v
        v *= b
        ans %= M
        v %= M
        l.append(ans)
    return l
l = rhash_list(s)
if len(set(s))==n:
    ans = 0
else:
    binv = pow(b,M-2,M)
    pows = [None]*(n+1)
    v = 1
    for j in range(n+1):
        pows[j] = v
        v *= binv
        v %= M
#         pow(binv,j,M)
    ans = 0
    from collections import defaultdict
    for i in range(n//2, 0, -1):
        d = defaultdict(list)
        for j in range(n-i+1):
            d[((l[j+i]-l[j])*pows[j])%M].append(j)
        for v in d.values():
            if v[0]+i<=v[-1]:
                ans = i
        if ans>0:
            break
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
s = input()
### ローリングハッシュ rolling hash
import random
# M = 10**9+7
# M = 1<<63 - 1
# M = 9007199254740997
M = 2147483647

b = random.choice(range(1,M))
def rhash_list(s):
    l = [chr(v) for v in range(ord("a"), ord("z")+1)]
    d = {c:i+2 for i,c in enumerate(l)}
    ans = 0
    v = 1
    l = [0]
    for item in s:
        ans += d[item]*v
        v *= b
        ans %= M
        v %= M
        l.append(ans)
    return l
l = rhash_list(s)
if len(set(s))==n:
    ans = 0
else:
    binv = pow(b,M-2,M)
    pows = [None]*(n+1)
    v = 1
    for j in range(n+1):
        pows[j] = v
        v *= binv
        v%= M
#         pow(binv,j,M)
    ans = 0
    from collections import defaultdict
    for i in range(n//2, 0, -1):
        d = defaultdict(list)
        for j in range(n-i+1):
            d[((l[j+i]-l[j])*pows[j])%M].append(j)
        for k,v in d.items():
            if v[0]+i<=v[-1]:
                ans = i
        if ans>0:
            break
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
s = input()
### ローリングハッシュ rolling hash
import random
M = 10**9+7
# M = 1<<63 - 1

b = random.choice(range(1,M))
def rhash_list(s):
    l = [chr(v) for v in range(ord("a"), ord("z")+1)]
    d = {c:i+1 for i,c in enumerate(l)}
    ans = 0
    v = 1
    l = [0]
    for item in s:
        ans += d[item]*v
        v *= b
        ans %= M
        v %= M
        l.append(ans)
    return l
l = rhash_list(s)
if len(set(s))==n:
    ans = 0
else:
    binv = pow(b,M-2,M)
    ans = 0
    from collections import defaultdict
    for i in range(n//2, 0, -1):
        d = defaultdict(list)
        for j in range(n-i+1):
            d[((l[j+i]-l[j])*pow(binv,j,M))%M].append(j)
        for k,v in d.items():
            if v[0]+i<=v[-1]:
                ans = i
        if ans>0:
            break
print(ans)

Submission status: Wrong Answer

Solution code:
class RollingHash:

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

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

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


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


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

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

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

    MOD = 2 ** 61 - 1
    root = 10000

    rh = RollingHashMOD61(S, root)

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

    print(ok)

Submission status: Wrong Answer

Solution code:
class RollingHash:

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

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

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


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


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

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

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

    MOD = 2 ** 61 - 1
    root = 10000

    rh = RollingHashMOD61(S, root)

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

    print(ok)

Submission status: Wrong Answer

Solution code:
class RollingHash:

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

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

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


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


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

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

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

    MOD = 2 ** 61 - 1
    root = 10000

    rh = RollingHashMOD61(S, root)

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

    print(ok)

Submission status: Wrong Answer

Solution code:
class RollingHash:

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

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

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


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


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

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

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

    MOD = 2 ** 61 - 1
    root = 10000

    rh = RollingHashMOD61(S, root)

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

    print(ok)

Submission status: Wrong Answer

Solution code:
class RollingHash:

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

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

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


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


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

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

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

    MOD = 2 ** 61 - 1
    root = 10000

    rh = RollingHashMOD61(S, root)

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

    print(ok)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input() + '_'
    
dp = [[0]*(n+1) for i in range(n+1)]
for i in range(n-2, -1, -1):
    for j in range(n-1, i,-1):
        if i + dp[i+1][j+1] >= j:
            break
        if s[i] == s[j]:
            dp[i][j] = dp[i+1][j+1] + 1