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

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





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 max(min(i,Z_alg[i]) for i in range(N))

N = I()
S = S()
ans = 0
while len(S):
  ans = max(ans,Z_algorithm(S))
  S = S[1:]
print(ans)

Solution (Python):
N=int(input())
S=input()
ans=0
for i in range(N-1):
  jstart=i+ans+1
  for j in range(jstart,N):
    if S[i:j] in S[j:]:
      ans=max(ans,j-i)
    else:
      break
print(ans)

Solution (Python):


import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    from collections import defaultdict
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]


    P1 = 2**127-1
    P2 = 2**31-1
    P1 = 10**9*7
    P2 = 10**7-9
    base = 26
    N = II()
    S = list(map(ord,list(input())))
    pow1 = [1]*N
    pow2 = [1]*N
    for i in range(N-1):
        pow1[i+1] = pow1[i]*base%P1
        pow2[i+1] = pow2[i]*base%P2
    hash1 = [0]*(N+1)
    hash2 = [0]*(N+1)
    hash1[1] = hash2[1] = S[0]
    for i in range(2,N+1):
        hash1[i] = (hash1[i-1]*base + S[i-1]) % P1
        hash2[i] = (hash2[i-1]*base + S[i-1]) % P2
    
    def f(x):
        hashes = defaultdict(lambda : -1)
        for i in range(N-x+1):
            
            h1 = (hash1[i+x] - hash1[i] * pow1[x]) % P1
            h2 = (hash2[i+x] - hash2[i] * pow2[x]) % P2
            if hashes[(h1,h2)] == -1:
                hashes[(h1,h2)] = i
            elif hashes[(h1,h2)] + x <= i:
                return True
        
        return False
    
    ok = -1
    ng = N//2+1
    while ng-ok > 1:
        
        m = (ok+ng)//2
        
        if f(m):
            ok = m
        else:
            ng = m
    print(ok)

if __name__ == '__main__':
    main()

Solution (Python):


import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    from collections import defaultdict
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]


    P1 = 2**127-1
    P2 = 2**31-1
    base = 26
    N = II()
    S = list(map(ord,list(input())))
    pow1 = [1]*N
    pow2 = [1]*N
    for i in range(N-1):
        pow1[i+1] = pow1[i]*base%P1
        pow2[i+1] = pow2[i]*base%P2
    hash1 = [0]*(N+1)
    hash2 = [0]*(N+1)
    hash1[1] = hash2[1] = S[0]
    for i in range(2,N+1):
        hash1[i] = (hash1[i-1]*base + S[i-1]) % P1
        hash2[i] = (hash2[i-1]*base + S[i-1]) % P2
    
    def f(x):
        hashes = defaultdict(lambda : -1)
        for i in range(N-x+1):
            
            h1 = (hash1[i+x] - hash1[i] * pow1[x]) % P1
            h2 = (hash2[i+x] - hash2[i] * pow2[x]) % P2
            if hashes[(h1,h2)] == -1:
                hashes[(h1,h2)] = i
            elif hashes[(h1,h2)] + x <= i:
                return True
        
        return False
    
    ok = -1
    ng = N//2+1
    while ng-ok > 1:
        
        m = (ok+ng)//2
        
        if f(m):
            ok = m
        else:
            ng = m
    print(ok)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LS2(): return list(sys.stdin.readline().rstrip())  

N = I()
S = LS2()


def Z_algorithm(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
        if j == 0:
            i += 1
            continue
        
        A[i] = j
        k = 1
        while i+k < N and k+A[k] < j:
            A[i+k] = A[k]
            k += 1
        i += k
        j -= k
    return A


ans = 0
for i in range(N):
    A = Z_algorithm(S)
    for j in range(N-i):
        if A[j] <= j:
            ans = max(ans,A[j])
    del S[0]

print(ans)

Solution (Python):
def main():
    N = int(input())
    S = input()
    
    flags = [[0] * N for _ in range(N)]
    for n, c in enumerate(S):
        for m in range(1, N - n):
            if c == S[n + m]:
                flags[n][m] = 1
    ans = 0
    for m in range(1, N):
        from_n = -1
        for to_n in range(N):
            if flags[to_n][m] == 0:
                ans = max(ans, min(m, to_n - from_n - 1))
                from_n = to_n
        if from_n != to_n:
            ans = max(ans, min(m, to_n - from_n - 1))
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def resolve():
    N = int(input())
    S = input()
    dp = [[0]*(N+1) for _ in range(N+1)]
    for i in reversed(range(N)):
        for j in reversed(range(N)):
            if S[i] == S[j]:
                dp[i][j] = dp[i+1][j+1] + 1
    
    ans = 0
    for i in range(N):
        for j in range(i, N):
            ans = max(min(dp[i][j], j-i), ans)
    print(ans)


if __name__ == "__main__":
    resolve()

Solution (Python):
n = int(input())
S = input()
ans = 0
for d in range(n):
    cnt = 0
    for i in range(n-d):
        if S[i] == S[d+i]:
            cnt += 1
        else:
            cnt = 0
        ans = max(ans, min(cnt, d))
print(ans)

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

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

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

    print(res)

if __name__ == '__main__':
    resolve()

Solution (Python):
n=int(input())
s=input()
dp=[[0]*n for i in range(n)]
for i in range(n-2,-1,-1):
    for j in range(n-1,i,-1):
        if j==n-1:
            if s[j]==s[i]:
                dp[i][j]=1
        else:
            if s[j]==s[i] and dp[i+1][j+1]+1<=j-i:
                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,dp[i][j])
print(ans)

Solution (Python):
n = int(input())
s = input()
 
max_len = 0
j = 0
 
for i in range(n):
    while j < n and s[i:j] in s[j:]:
        j += 1
    max_len = max(max_len,j-i-1)
 
print(max_len)

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

def kAlgo(S, N):
    szS = N
    Z = [0]*szS
    Z[0] = szS
    i = 1 
    j = 0 
    while i < szS:
        while (i + j < szS) and (S[j] == S[i+j]): j += 1
        
        Z[i] = j

        if j == 0:
            i += 1
            continue

        
        k = 1
        while (k < j) and (k + Z[k] < j):
            Z[i+k] = Z[k]
            k += 1

        i += k
        j -= k

    ans = 0
    for i in range(N):
        if Z[i] > i: Z[i] = i
    return max(Z[1:])

ans = 0
for i in range(N-1):
    lenz = kAlgo(S[i:], N-i)
    if ans < lenz:
        ans = lenz

print(ans)

Solution (Python):
N=int(input())
S=input()
ans = 0
j = 0
for i in range(N):
  while j < N and S[i:j] in S[j:]:
    j += 1
  ans = max(ans,j-i-1)
print(ans)

Solution (Python):
def z_algorithm(s):  
    """
    SとS[i:]のLCP(longest common prefix: 最長共通接頭辞の長さ) Z[i]を計算し、Zを返す
    """
    n = len(s)
    z = [0] * n
    z[0] = n
    i = 1
    j = 0
    while i < n:
        while i + j < n and s[j] == s[i + j]:
            j += 1
        z[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while k < j and k + z[k] < j:
            z[i + k] = z[k]
            k += 1
        i += k
        j -= k
    return z



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

ans = 0
for i in range(n):
    Z = z_algorithm(s[i:])
    for j in range(len(Z)):
        if Z[j] > j:
            ans = max(ans, j)
        else:
            ans = max(ans, Z[j])

print(ans)

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

max_len = 0
j = 0

for i in range(n):
    while j < n and s[i:j] in s[j:]:
        j += 1
    max_len = max(max_len,j-i-1)

print(max_len)

Solution (Python):
n=int(input())
ss=input()




def func(s):
  a=[0]*len(s)
  a[0]=len(s)
  i,j=1,0
  while i<len(s):
    while i+j<len(s) and s[j]==s[i+j]:
      j+=1
    a[i]=j
    if j==0:
      i+=1
      continue
    k=1
    while i+k<len(s) and k+a[k]<j:
      a[i+k]=a[k]
      k+=1
    i+=k
    j-=k
  return a
ans=0
for i in range(n):
  a=func(ss[i:])
  for j in range(len(a)):
    ans=max(ans,min(a[j],j))
print(ans)

Solution (Python):
class RollingHash:
    """Rolling Hash"""

    __slots__ = ["_base", "_mod", "_hash", "_power"]

    def __init__(self, source: str, base: int = 1007, mod: int = 10 ** 9 + 7) -> None:
        self._base = base
        self._mod = mod
        self._hash = [0] * (len(source) + 1)
        self._power = [0] * (len(source) + 1)

        self._power[0] = 1
        for i, c in enumerate(source, 1):
            self._hash[i] = (self._hash[i - 1] * self._base + ord(c)) % self._mod
            self._power[i] = self._power[i - 1] * self._base % self._mod

    def get_hash(self, left: int, right: int) -> int:
        """Return hash of interval [left, right)."""
        return (
            self._hash[right] - self._hash[left] * self._power[right - left]
        ) % self._mod


def abc141_e():
    
    N = int(input())
    S = input().rstrip()

    rh = RollingHash(S)
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        flg = False
        memo = set()
        for i in range(N - 2 * mid + 1):
            memo.add(rh.get_hash(i, i + mid))
            if rh.get_hash(i + mid, i + 2 * mid) in memo:
                flg = True
                break
        if flg:
            ok = mid  
        else:
            ng = mid  

    print(ok)  


if __name__ == "__main__":
    abc141_e()

Solution (Python):
from typing import List, Tuple


class RollingHash:
    """Rolling Hash"""

    __slots__ = ["_base", "_mod", "_hash", "_power"]

    def __init__(self, source: str, base: int = 1007, mod: int = 10 ** 9 + 7):
        self._base = base
        self._mod = mod
        self._hash, self._power = self._build(source)

    def _build(self, source: str) -> Tuple[List[int], List[int]]:
        """Compute "hash" and "mod of power of base" of interval [0, right)."""
        hash_, power = [0] * (len(source) + 1), [0] * (len(source) + 1)
        power[0] = 1
        for i, c in enumerate(source, 1):
            hash_[i] = (hash_[i - 1] * self._base + ord(c)) % self._mod
            power[i] = power[i - 1] * self._base % self._mod
        return hash_, power

    def get_hash(self, left: int, right: int):
        """Return hash of interval [left, right)."""
        return (
            self._hash[right] - self._hash[left] * self._power[right - left]
        ) % self._mod


def abc141_e():
    
    N = int(input())
    S = input().rstrip()

    rh = RollingHash(S)
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        flg = False
        memo = set()
        for i in range(N - 2 * mid + 1):
            memo.add(rh.get_hash(i, i + mid))
            if rh.get_hash(i + mid, i + 2 * mid) in memo:
                flg = True
                break
        if flg:
            ok = mid  
        else:
            ng = mid  

    print(ok)  


if __name__ == "__main__":
    abc141_e()

Solution (Python):
from typing import List, Tuple


class RollingHash:
    """Rolling Hash"""

    __slots__ = ["_base", "_mod", "_hash", "_power"]

    def __init__(self, source: str, base: int = 1007, mod: int = 10 ** 9 + 7):
        self._base = base
        self._mod = mod
        self._hash, self._power = self._build(source)

    def _build(self, source: str) -> Tuple[List[int], List[int]]:
        """Compute "hash" and "mod of power of base" of interval [0, right)."""
        length = len(source)
        hash_, power = [0] * (length + 1), [0] * (length + 1)
        power[0] = 1
        for i, c in enumerate(source, 1):
            hash_[i] = (hash_[i - 1] * self._base + ord(c)) % self._mod
            power[i] = power[i - 1] * self._base % self._mod
        return hash_, power

    def get_hash(self, left: int, right: int):
        """Return hash of interval [left, right)."""
        return (
            self._hash[right] - self._hash[left] * self._power[right - left]
        ) % self._mod


def abc141_e():
    
    N = int(input())
    S = input().rstrip()

    rh = RollingHash(S)
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        flg = False
        memo = set()
        for i in range(N - 2 * mid + 1):
            memo.add(rh.get_hash(i, i + mid))
            if rh.get_hash(i + mid, i + 2 * mid) in memo:
                flg = True
                break
        if flg:
            ok = mid  
        else:
            ng = mid  

    print(ok)  


if __name__ == "__main__":
    abc141_e()

Solution (Python):

def resolve():
    N = int(input())
    S = input().rstrip()
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        flg = False
        memo = set()
        for i in range(N - 2 * mid + 1):
            memo.add(hash(S[i : i + mid]))
            if hash(S[i + mid : i + 2 * mid]) in memo:
                flg = True
                break
        if flg:
            ok = mid  
        else:
            ng = mid  
    print(ok)  


resolve()

Solution (Python):
from typing import List, Tuple


class RollingHash:
    """Rolling Hash"""

    __slots__ = ["_base", "_mod", "_hash", "_power"]

    def __init__(self, source: str, base: int = 1007, mod: int = 10 ** 9 + 7):
        self._base = base
        self._mod = mod
        self._hash, self._power = self._build(source)

    def _build(self, source: str) -> Tuple[List[int], List[int]]:
        """Compute "hash" and "mod of power of base" of interval [0, right)."""
        length = len(source)
        hash_, power = [0] * (length + 1), [0] * (length + 1)
        power[0] = 1
        for i, c in enumerate(source, 1):
            hash_[i] = (hash_[i - 1] * self._base + ord(c)) % self._mod
            power[i] = power[i - 1] * self._base % self._mod
        return hash_, power

    def get_hash(self, left: int, right: int):
        """Return hash of interval [left, right)."""
        return (
            self._hash[right] - self._hash[left] * self._power[right - left]
        ) % self._mod


def abc141_e():
    
    N = int(input())
    S = input().rstrip()

    rh = RollingHash(S)
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        flg = False
        memo = set()
        for i in range(N - 2 * mid + 1):
            memo.add(rh.get_hash(i, i + mid))
            if rh.get_hash(i + mid, i + 2 * mid) in memo:
                flg = True
                break
        if flg:
            ok = mid  
        else:
            ng = mid  

    print(ok)  


if __name__ == "__main__":
    abc141_e()

Solution (Python):
from typing import List


class RollingHash:
    """Rolling Hash"""

    __slots__ = ["_base", "_mod", "_hash", "_power"]

    def __init__(self, source: str, base: int = 1007, mod: int = 10 ** 9 + 7):
        self._base = base
        self._mod = mod
        self._hash = self._build_hash_from_zero(source)
        self._power = self._build_base_power(len(source))

    def _build_hash_from_zero(self, source: str) -> List[int]:
        """Compute hash of interval [0, right)."""
        res = [0] * (len(source) + 1)
        for i, c in enumerate(source, 1):
            res[i] = (res[i - 1] * self._base + ord(c)) % self._mod
        return res

    def _build_base_power(self, length: int) -> List[int]:
        """Compute mod of power of base."""
        res = [1] * (length + 1)
        for i in range(1, length + 1):
            res[i] = res[i - 1] * self._base % self._mod
        return res

    def get_hash(self, left: int, right: int):
        """Return hash of interval [left, right)."""
        return (
            self._hash[right] - self._hash[left] * self._power[right - left]
        ) % self._mod


def abc141_e():
    
    N = int(input())
    S = input().rstrip()

    rh = RollingHash(S)
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        flg = False
        memo = set()
        for i in range(N - 2 * mid + 1):
            memo.add(rh.get_hash(i, i + mid))
            if rh.get_hash(i + mid, i + 2 * mid) in memo:
                flg = True
                break
        if flg:
            ok = mid  
        else:
            ng = mid  

    print(ok)  


if __name__ == "__main__":
    abc141_e()

Solution (Python):
from typing import List


class RollingHash:
    """Rolling Hash"""

    __slots__ = ["_length", "_base", "_mod", "_hash", "_power"]

    def __init__(self, source: str, base: int = 1007, mod: int = 10 ** 9 + 7):
        self._length = len(source)
        self._base = base
        self._mod = mod
        self._hash = self._build_hash_from_zero(source)
        self._power = self._build_base_power()

    def _build_hash_from_zero(self, source: str) -> List[int]:
        """Compute hash of interval [0, right)."""
        res = [0] * (self._length + 1)
        for i, c in enumerate(source, 1):
            res[i] = (res[i - 1] * self._base + ord(c)) % self._mod
        return res

    def _build_base_power(self) -> List[int]:
        """Compute mod of power of base."""
        res = [1] * (self._length + 1)
        for i in range(1, self._length + 1):
            res[i] = res[i - 1] * self._base % self._mod
        return res

    def get_hash(self, left: int, right: int):
        """Return hash of interval [left, right)."""
        return (
            self._hash[right] - self._hash[left] * self._power[right - left]
        ) % self._mod


def abc141_e():
    
    N = int(input())
    S = input().rstrip()

    rh = RollingHash(S)
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        flg = False
        memo = set()
        for i in range(N - 2 * mid + 1):
            memo.add(rh.get_hash(i, i + mid))
            if rh.get_hash(i + mid, i + 2 * mid) in memo:
                flg = True
                break
        if flg:
            ok = mid  
        else:
            ng = mid  

    print(ok)  


if __name__ == "__main__":
    abc141_e()

Solution (Python):
from typing import List


class RollingHash:
    """Rolling Hash"""

    __slots__ = ["_source", "_length", "_base", "_mod", "_hash", "_power"]

    def __init__(self, source: str, base: int = 1007, mod: int = 10 ** 9 + 7):
        self._source = source
        self._length = len(source)
        self._base = base
        self._mod = mod
        self._hash = self._build_hash_from_zero()
        self._power = self._build_base_power()

    def _build_hash_from_zero(self) -> List[int]:
        """Compute hash of interval [0, right)."""
        res = [0] * (self._length + 1)
        prev = 0
        for i, c in enumerate(self._source, 1):
            res[i] = (prev * self._base + ord(c)) % self._mod
            prev = res[i]
        return res

    def _build_base_power(self) -> List[int]:
        """Compute mod of power of base."""
        res = [1] * (self._length + 1)
        prev = 1
        for i in range(1, self._length + 1):
            res[i] = prev * self._base % self._mod
            prev = res[i]
        return res

    def get_hash(self, left: int, right: int):
        """Return hash of interval [left, right)."""
        return (
            self._hash[right] - self._hash[left] * self._power[right - left]
        ) % self._mod


def abc141_e():
    
    N = int(input())
    S = input().rstrip()
    rh = RollingHash(S)
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        flg = False
        memo = set()
        for i in range(N - 2 * mid + 1):
            memo.add(rh.get_hash(i, i + mid))
            if rh.get_hash(i + mid, i + 2 * mid) in memo:
                flg = True
                break
        if flg:
            ok = mid  
        else:
            ng = mid  
    print(ok)  


if __name__ == "__main__":
    abc141_e()

Solution (Python):
from typing import List


class RollingHash:
    """Rolling Hash"""

    __slots__ = ["_source", "_length", "_base", "_mod", "_hash", "_power"]

    def __init__(self, source: str, base: int = 1007, mod: int = 10 ** 9 + 7):
        self._source = source
        self._length = len(source)
        self._base = base
        self._mod = mod
        self._hash = self._build_hash_from_zero()
        self._power = self._build_base_power()

    def _build_hash_from_zero(self) -> List[int]:
        """Compute hash of interval [0, right)."""
        res = [0] * (self._length + 1)
        for i, c in enumerate(self._source, 1):
            res[i] = (res[i - 1] * self._base + ord(c)) % self._mod
        return res

    def _build_base_power(self) -> List[int]:
        """Compute mod of power of base."""
        res = [1] * (self._length + 1)
        for i in range(1, self._length + 1):
            res[i] = res[i - 1] * self._base % self._mod
        return res

    def get_hash(self, left: int, right: int):
        """Return hash of interval [left, right)."""
        return (
            self._hash[right] - self._hash[left] * self._power[right - left]
        ) % self._mod


def abc141_e():
    
    N = int(input())
    S = input().rstrip()
    rh = RollingHash(S)
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        flg = False
        memo = set()
        for i in range(N - 2 * mid + 1):
            memo.add(rh.get_hash(i, i + mid))
            if rh.get_hash(i + mid, i + 2 * mid) in memo:
                flg = True
                break
        if flg:
            ok = mid  
        else:
            ng = mid  
    print(ok)  


if __name__ == "__main__":
    abc141_e()

Solution (Python):
from typing import List


class RollingHash:
    __slots__ = ["_source", "_length", "_base", "_mod", "_hash", "_power"]

    def __init__(self, source: str, base: int = 1007, mod: int = 10 ** 9 + 7):
        self._source = source
        self._length = len(source)
        self._base = base
        self._mod = mod
        self._hash = self._get_hash_from_zero()
        self._power = self._get_base_pow()

    def _get_hash_from_zero(self) -> List[int]:
        """Compute hash of interval [0, right)."""
        hash_from_zero = [0] * (self._length + 1)
        cur = 0
        for i, c in enumerate(self._source, 1):
            cur = (cur * self._base + ord(c)) % self._mod
            hash_from_zero[i] = cur
        return hash_from_zero

    def _get_base_pow(self) -> List[int]:
        """Compute mod of power of base."""
        power = [0] * (self._length + 1)
        power[0] = 1
        cur = 1
        for i in range(1, self._length + 1):
            cur *= self._base % self._mod
            power[i] = cur
        return power

    def get_hash(self, left: int, right: int):
        """Compute hash of interval [left, right)."""
        return (
            self._hash[right] - self._hash[left] * self._power[right - left]
        ) % self._mod


def abc141_e():
    
    N = int(input())
    S = input().rstrip()
    rh = RollingHash(S)
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        flg = False
        memo = set()
        for i in range(N - 2 * mid + 1):
            memo.add(rh.get_hash(i, i + mid))
            if rh.get_hash(i + mid, i + 2 * mid) in memo:
                flg = True
                break
        if flg:
            ok = mid  
        else:
            ng = mid  
    print(ok)  


if __name__ == "__main__":
    abc141_e()

Solution (Python):
from typing import List


class RollingHash:
    __slots__ = ["source", "length", "base", "mod", "hash", "power"]

    def __init__(self, source: str, base: int = 1007, mod: int = 10 ** 9 + 7):
        self.source = source
        self.length = len(source)
        self.base = base
        self.mod = mod
        self.hash = self._get_hash_from_zero()
        self.power = self._get_base_pow()

    def _get_hash_from_zero(self) -> List[int]:
        """Compute hash of interval [0, right)."""
        hash_from_zero = [0] * (self.length + 1)
        cur = 0
        for i, c in enumerate(self.source, 1):
            cur = (cur * self.base + ord(c)) % self.mod
            hash_from_zero[i] = cur
        return hash_from_zero

    def _get_base_pow(self) -> List[int]:
        """Compute mod of power of base."""
        power = [1] * (self.length + 1)
        cur = 1
        for i in range(1, self.length + 1):
            cur *= self.base % self.mod
            power[i] = cur
        return power

    def get_hash(self, left: int, right: int):
        """Compute hash of interval [left, right)."""
        return (
            self.hash[right] - self.hash[left] * self.power[right - left]
        ) % self.mod


def abc141_e():
    
    N = int(input())
    S = input().rstrip()
    rh = RollingHash(S)
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        flg = False
        memo = set()
        for i in range(N - 2 * mid + 1):
            memo.add(rh.get_hash(i, i + mid))
            if rh.get_hash(i + mid, i + 2 * mid) in memo:
                flg = True
                break
        if flg:
            ok = mid  
        else:
            ng = mid  
    print(ok)  


if __name__ == "__main__":
    abc141_e()