Problem:


Score : 500 points

Problem Statement

Given is a string S of length N.

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

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

l_1 + len \leq l_2

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

If there is no such integer len, print 0.

Constraints

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

|S| = N

S consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

N
S

Output

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

Sample Input 1

5
ababa

Sample Output 1

2

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

Sample Input 2

2
xy

Sample Output 2

0

No non-empty string satisfies the conditions.

Sample Input 3

13
strangeorange

Sample Output 3

5



Sample input:
5
ababa


Sample output:
2

Submission status: Accepted

Solution code:
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)

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

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=2009, 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: Accepted

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,base1=1007,base2=2009,mod1=10**9+7,mod2=10**9+9)

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

else:
    print(0)

Submission status: Accepted

Solution code:
n, s = int(input()), input()
dp = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
    for j in range(i + 1, n):
        if s[i] == s[j]:
            dp[i + 1][j + 1] = min(dp[i][j] + 1, j - i)
from itertools import chain
# max(i for i in chain.from_iterable(dp))
print(max(chain.from_iterable(dp)))

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
def z_algo(s):
    ret = [0]*(len(s))
    ret[0] = len(s)
    i = 1
    j = 0
    while i<len(s):
        while i+j<len(s)  and s[i+j]==s[j]:
            j+=1
        ret[i] = j
        if j==0:
            i+=1
            continue
        k=1
        while i+k<len(s) and k+ret[k] <j:
            ret[i+k] = ret[k]
            k+=1
        i+=k
        j=min(ret[k],j-k) ## j= j-kでもよい
    return ret

n = ni()
s = input()
ans = 0
for i in range(n):
    z = z_algo(s[i:])
    for j in range(len(z)):
        if j>=z[j]:
            ans = max(ans,z[j])
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
s=input()
mx=0
for i in range(1,n):
  c=0
  for j in range(n-i):
    if s[j]==s[j+i]:
      c+=1
      mx=max(mx,c)
      if c==i:
        break
    else:
      c=0
print(mx)

Submission status: Accepted

Solution code:

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    class RollingHash(object):
        """
        construct: O(N)
        query:
            hash: O(1)
            lcp: O(logN)
            search: O(N)
        """
        __base1=1007; __mod1=10**9
        __base2=1009; __mod2=10**7

        def __init__(self,s):
            """
            s: str
            """
            n=len(s)
            self.__s=s
            self.__n=n
            b1=self.__base1; m1=self.__mod1
            b2=self.__base2; m2=self.__mod2
            H1,H2=[0]*(n+1),[0]*(n+1)
            P1,P2=[1]*(n+1),[1]*(n+1)
            for i in range(n):
                H1[i+1]=(H1[i]*b1+ord(s[i]))%m1
                H2[i+1]=(H2[i]*b2+ord(s[i]))%m2
                P1[i+1]=P1[i]*b1%m1
                P2[i+1]=P2[i]*b2%m2
            self.__H1=H1; self.__H2=H2
            self.__P1=P1; self.__P2=P2

        @property
        def str(self):
            return self.__s

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

        def hash(self,l,r=None):
            """
            l,r: int (0<=l<=r<=n)
            return (hash1,hash2) of S[l:r]
            """
            m1=self.__mod1; m2=self.__mod2
            if r is None: r=self.__n
            assert 0<=l<=r<=self.__n
            return ((self.__H1[r]-self.__P1[r-l]*self.__H1[l]%m1)%m1,
                    (self.__H2[r]-self.__P2[r-l]*self.__H2[l]%m2)%m2)

        @classmethod
        def lcp(cls,rh1,rh2,l1,l2,r1=None,r2=None):
            """
            rh1,rh2: RollingHash object
            l1,l2,r1,r2: int 0<=l1<=r1<=r1.len,0<=l2<=r2<=rh2.len
            return lcp length between rh1[l1:r1] and rh2[l2:r2]
            """
            if r1 is None: r1=rh1.__n
            if r2 is None: r2=rh2.__n
            assert 0<=l1<=r1<=rh1.__n and 0<=l2<=r2<=rh2.__n
            L=0
            R=min(r1-l1,r2-l2)
            if rh1.hash(l1,l1+R)==rh2.hash(l2,l2+R): return R
            while(R-L>1):
                H=(L+R)//2
                if rh1.hash(l1,l1+H)==rh2.hash(l2,l2+H): L=H
                else: R=H
            return L

        @classmethod
        def search(cls,pattern,text):
            """
            pattern,text: RollingHash object
            return list of index i's satisfying text[i:] starts with pattern
            """
            n=text.__n; m=pattern.__n
            res=[]
            for i in range(n-m+1):
                if text.hash(i,i+m)==pattern.hash(0,m):
                    res.append(i)
            return res
    
    mod=10**9+7
    N=I()
    S=input()
    rh=RollingHash(S)
    
    from collections import defaultdict

    """
    長さlのpunがあるか
    S[i:i+l]のハッシュ値と，S[j:j+l]のハッシュ値が同じかつ，i+l <= jなら良い．
    i,jのループで回さず，iだけ回してハッシュ値とその時のiを記憶しておく．同じハッシュ値が出てきたらi+l < jの判定をする
    """
    def ch(l):
        dd = defaultdict(lambda: -1)# ハッシュ => i
        for i in range(N-l+1):
            h=rh.hash(i,i+l)
            if dd[h]!=-1:
                ii=dd[h]
                if ii+l <= i:
                    return True
            else:
                dd[h]=i
                
        return False
        
        
    
    ok=0
    ng=N
    while ng-ok>1:
        med=(ok+ng)//2
        if ch(med):
            ok=med
        else:
            ng=med
            
    print(ok)
    
    
    
    

    

main()

Submission status: Accepted

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

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


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


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

Submission status: Accepted

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+1)] for i in range(N+1)]

for i in range(N-1,-1,-1):
    for j in range(N-1,i,-1):
        if S[i] == S[j]:
           dp[i][j] = dp[i+1][j+1] + 1
        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: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

def judge(x):
    d = defaultdict(int)
    d[hash(S[:x])] = 0
    
    for i in range(1, len(S)-x+1):
        k = hash(S[i:i+x])
        
        if k in d:
            if i-d[k]>=x:
                return True
        else:
            d[k] = i
    
    return False

def binary_search():
    l, r = 0, N
    
    while l<=r:
        m = (l+r)//2
        
        if judge(m):
            l = m+1
        else:
            r = m-1
    
    return r

N = int(input())
S = input()[:-1]
print(binary_search())

Submission status: Accepted

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

def Z_algorithm(s):
    N = len(s)
    Z_alg = [0]*N

    Z_alg[0] = N
    i = 1
    j = 0
    while i < N:
        while i+j < N and s[j] == s[i+j]:
            j += 1
        Z_alg[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k + Z_alg[k]<j:
            Z_alg[i+k] = Z_alg[k]
            k += 1
        i += k
        j -= k
    return Z_alg
ans=0
for i in range(n):
    t=s[i:]
    z=Z_algorithm(t)
    ans=max(ans,max([min(j,z[j]) for j in range(len(z))]))

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
ret = 0
for l in range(n):
  while s[l:l+ret+1] in s[l+ret+1:]:
    ret += 1
print(ret)

Submission status: Accepted

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):
        if s[i-1]==s[j-1]:
            dp[i][j]=dp[i-1][j-1]+1
        dp[i][j]=min(dp[i][j],i,j-i)
print(max(max(i)for i in dp))

Submission status: Accepted

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

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N = I()
S = LS2()
for i in range(N):
    S[i] = ord(S[i])-97

# Rolling Hash

mod = 10**9+7
base = 1234


def f(n):  # 長さnで条件を満たす部分列が存在するか
    A = []
    a = 0
    for i in range(n):
        a += S[i]*pow(base,i,mod)
        a %= mod
    A.append(a)
    for i in range(n,N):
        a -= S[i-n]
        a *= pow(base,mod-2,mod)
        a %= mod
        a += S[i]*pow(base,n-1,mod)
        a %= mod
        A.append(a)
    for i in range(N-n+1):
        for j in range(i+n,N-n+1):
            if A[i] == A[j]:
                return True
    return False


left = 0  # 可能
right = N+1  # 不可能
while left + 1 < right:
    mid = (left + right)//2
    if f(mid):
        left = mid
    else:
        right = mid
print(left)

Submission status: Accepted

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
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))"
        return (self.hs[r] - self.hs[l] * self.pw[r - l]) % RHMOD
        

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

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

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 << 61
class RollingHashMOD61:
    """
    MOD == 2 ** 61 - 1
    参考: https://qiita.com/keymoon/items/11fac5627672a6d6a9f6
    """


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

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

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

    MOD = 2 ** 61 - 1
    root = 10000

    rh = RollingHashMOD61(S, root)

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

    print(ok)

Submission status: Accepted

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 = RollingHash(S, root, MOD)

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

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 = RollingHash(S, root, MOD)

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

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 = RollingHash(S, root, MOD)

    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)