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):
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)."""
        cur, hash_from_zero = 0, [0]
        for e in self.source:
            cur = (cur * self.base + ord(e)) % self.mod
            hash_from_zero.append(cur)
        return hash_from_zero

    def _get_base_pow(self) -> List[int]:
        """Compute mod of power of base."""
        cur, power = 1, [1]
        for i in range(self.length):
            cur *= self.base % self.mod
            power.append(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, memo = 0, 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 = 1
                break
        if flg:
            ok = mid  
        else:
            ng = mid  
    print(ok)  


if __name__ == "__main__":
    abc141_e()

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7






"""
Z algorithm
def Z(s):
    n = len(s)
    z = [0] * n
    z[0] = n

    L, R = 0, 0
    for i in range(1, n):
        if i >= R:
            L = R = i
            
            while(R < n and s[R - L] == s[R]):
                R += 1
            
            
            z[i] = R - L
        
        elif z[i - L] < R - i:
            z[i] = z[i - L]
        
        else:
            L = i
            while(R < n and s[R - L] == s[R]):
                R += 1
            z[i] = R - L
    return z




N = getN()
S = input()
ans = 0
for i in range(N):
    z = Z(S[i:])
    k = len(z)
    for j in range(k):
        
        
        
        
        ans = max(ans, min(j, z[j]))
print(ans)
"""


N = getN()
S = list(map(ord, list(input())))

base = 1234
power = [1] * (N + 1)

for i in range(1, N + 1):
    power[i] = power[i - 1] * base % mod

def check(m):
    if N - m < m:
        return False
    res = 0
    for i in range(m):
        res += S[i] * power[m - i - 1]
        res %= mod
    dic = {res: 0}
    for i in range(N - m):
        res = ((res - S[i] * power[m - 1]) * base + S[i + m]) % mod
        if res in dic.keys():
            index = dic[res]
            if index + m <= i + 1:
                return True
        else:
            dic[res] = i + 1
    return False

ok = 0
ng = N + 1
while ng - ok > 1:
    mid = (ok + ng) // 2

    if check(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():


    class SuffixArray:
        """
        construct:
            suffix array: O(N(logN)^2)
            lcp array: O(N)
            sparse table: O(NlogN)
        query:
            get_lcp: O(1)
        """

        def __init__(self, s):
            """
            s: str
            """
            self.__s = s
            self.__n = len(s)
            self.__suffix_array()
            self.__lcp_array()
            self.__sparse_table()

        
        def __suffix_array(self):
            s = self.__s
            n = self.__n
            
            sa = list(range(n))
            rank = [ord(s[i]) for i in range(n)]
            tmp = [0]*n
            k = 1
            def cmp_key(i): return (rank[i], rank[i+k] if i+k < n else -1)
            
            while(k <= n):
                sa.sort(key=cmp_key)
                tmp[sa[0]] = 0
                for i in range(1, n):
                    tmp[sa[i]] = tmp[sa[i-1]]+(cmp_key(sa[i-1]) < cmp_key(sa[i]))
                rank = tmp[:]
                k <<= 1
            self.__sa = sa
            self.__rank = rank

        
        def __lcp_array(self):
            n = self.__n
            s = self.__s
            sa = self.__sa
            rank = self.__rank
            lcp = [0]*n
            h = 0
            for i in range(n):
                j = sa[rank[i]-1]
                if h > 0:
                    h -= 1
                while j+h < n and i+h < n and s[j+h] == s[i+h]:
                    h += 1
                lcp[rank[i]] = h
            self.__lcp = lcp

        
        def __sparse_table(self):
            n = self.__n
            logn = max(0, (n-1).bit_length())
            table = [[0]*n for _ in range(logn)]
            table[0] = list(range(n))
            
            for i in range(1, logn):
                for k in range(n):
                    if k+(1 << (i-1)) >= n:
                        table[i][k] = table[i-1][k]
                        continue
                    if self.__lcp[table[i-1][k]] <= self.__lcp[table[i-1][k+(1 << (i-1))]]:
                        table[i][k] = table[i-1][k]
                    else:
                        table[i][k] = table[i-1][k+(1 << (i-1))]
            self.__table = table

        def get_lcp(self, a, b):
            """
            a,b: int 0<=a,b<n
            return LCP length between s[a:] and s[b:]
            """
            if a == b:
                return self.__n-a
            l, r = self.__rank[a], self.__rank[b]
            l, r = min(l, r)+1, max(l, r)+1
            if r-l == 1:
                return self.__lcp[l]
            i = (r-l-1).bit_length()-1
            if self.__lcp[self.__table[i][l]] <= self.__lcp[self.__table[i][r-(1 << i)]]:
                return self.__lcp[self.__table[i][l]]
            else:
                return self.__lcp[self.__table[i][r-(1 << i)]]
    n = int(input())
    s = input()
    sa = SuffixArray(s)
    ans = 0
    for i in range(n):
        for j in range(i+1, n):
            ans = max(ans, min(sa.get_lcp(i, j), j-i))
    print(ans)



resolve()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    
    
    
    INF = 10**10  
    
    N = int(input())
    S=input()
    
    dp = [[0]*N for _ in range(N)]
    
    
    dp[0][0] = 0
    for i in range(N-1):
        if S[i]==S[N-1]:
            dp[N-1][i]=1


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

    
    
resolve()

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

def z_algorithm(s):
    n = len(s)
    res = [0] * n
    i = 1
    j = 0
    while i < n:
        while i + j < n and s[j] == s[i + j]:
            j += 1
        res[i] = j
        
        if j == 0:
            i += 1
            continue
            
        k = 1
        while i + k < n and k + res[k] < j:
            res[i + k] = res[k]
            k += 1
            
        i += k
        j -= k
        
    return res

ans = 0
for i in range(N):
    lcp = z_algorithm(S[i:])
    tmp = max(min(lcp[j], j) for j in range(N - i))
    ans = max(ans, tmp)
print(ans)

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

ans=0

for slide in range(1,N):
    pos=slide
    bpos=0
    while pos<N:
        clen=0
        while pos<N and clen<slide and S[pos]==S[bpos]:
            pos+=1
            bpos+=1
            clen+=1
        
        ans=max(ans,clen)

        if clen==0:
            pos+=1
            bpos+=1

print(ans)

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

MOD = 2 ** 61 - 1
root = 10000

rhs = [0]
for h in map(ord, S):
    rhs.append((root * rhs[-1] + h) % MOD)

pws = [1]
for i in range(N):
    pws.append(pws[-1] * 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 = (rhs[i+mid] - rhs[i] * pws[mid]) % MOD
        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)

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

MOD = 2 ** 61 - 1
root = 10000

rhs = [0]
for h in map(ord, S):
    rhs.append((root * rhs[-1] + h) % MOD)

pws = [1]
for i in range(N):
    pws.append(pws[-1] * 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 = (rhs[i+mid] - rhs[i] * pws[mid]) % MOD
        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)

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

ans = 0
while S:
    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
        else:
            k = 1
            while k < j and k + Z[k] < j:
                Z[i + k] = Z[k]
                k += 1
            i += k
            j -= k    

    ans = max(ans, max(min(i, z) for i, z in enumerate(Z)))

    S = S[1:]
    N -= 1

print(ans)

Solution (Python):
"""
    こんにちは。これはクシャルです
    
    Author : thekushalghosh (クシャル)
    Team   : CodeDiggers
 
    I prefer Python language over the C++ language :p :D
        
    Visit my website : thekushalghosh.github.io
"""
import sys,math,cmath,time,heapq
start_time = time.time()



def solve():
    n = inp()
    s = insr()
    q = [[0 for x in range(n + 1)] for y in range(n + 1)] 
    w = 0
    qw = ""
    qq = 0
    for i in range(1,n + 1): 
        for j in range(i + 1,n + 1):
            if s[i - 1] == s[j - 1] and q[i - 1][j - 1] < j - i: 
                q[i][j] = q[i - 1][j - 1] + 1
                if q[i][j] > w: 
                    w = q[i][j] 
                    index = max(i,qq)
            else: 
                q[i][j] = 0
    if w > 0: 
        for i in range(qq - w + 1,qq + 1): 
            qw = qw + s[i - 1] 
    print(len(qw))
    


 
def main():
    global tt
    if not ONLINE_JUDGE:
        sys.stdin = open("input.txt","r")
        sys.stdout = open("output.txt","w")
    t = 1
    for tt in range(t):
        solve()
    if not ONLINE_JUDGE:
        print("Time Elapsed :",time.time() - start_time,"seconds")
        sys.stdout.close()
    

def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    return(input().strip())
def invr():
    return(map(int,input().split()))
 

def counter(a):
    q = [0] * max(a)
    for i in range(len(a)):
        q[a[i] - 1] = q[a[i] - 1],1
    return(q)
 
def string_counter(a):
    q = [0] * 26
    for i in range(len(a)):
        q[ord(a[i]) - 97] = q[ord(a[i]) - 97],1
    return(q)

def factors(n):
    q = []
    for i in range(1,int(n ** 0.5) + 1):
        if n % i == 0: q.append(i); q.append(n // i)
    return(list(sorted(list(set(q)))))

def prime_factors(n):
    q = []
    while n % 2 == 0: q.append(2); n = n // 2
    for i in range(3,int(n ** 0.5) + 1,2):
        while n % i == 0: q.append(i); n = n // i
    if n > 2: q.append(n)
    return(list(sorted(q)))


        
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
    input = sys.stdin.readline
    
main()

Solution (Python):
import sys

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


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

    res = 0
    for i in range(n):
        for j in range(n):
            if i < j:
                now = min(dp[i][j], j - i)
                res = max(res, now)
    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))


def z_algorithm(s):
    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+z[k]<j:
            z[i+k] = z[k]
            k+=1
        
        i+=k
        j-=k
    
    return z

n = readint()
s = readstr()

ans = 0
for i in range(n):
    z = z_algorithm(s[i:])
    for j in range(n-i):
        if z[j]<=j:
            ans = max(ans,z[j])
print(ans)

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())
    S = readline().strip()

    ans = 0
    dp = [[0] * (N + 1) for _ in range(N + 1)]
    for i in range(N - 1, -1, -1):
        for j in range(N - 1, i - 1, -1):
            if S[i] == S[j]:
                dp[i][j] = dp[i + 1][j + 1] + 1
            if ans < min(j - i, dp[i][j]):
                ans = min(j - i, dp[i][j])

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):

"""
ロリハ解
探索する文字列の長さを二分探索し、重複を探す。
計算量はO((n+m)*log(n//2)) ※mは探索する文字列の長さ
log部分は100には間違いなく収まるので、O(10^5)程度。十分に間に合う。
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n = int(readline())
s = readline().rstrip().decode('utf-8')

class RollingHash(): 
    BASE1 = 1007
    BASE2 = 2009
    MOD1 = 1000000007
    MOD2 = 1000000009
 
    def __init__(self, s):
        self.n = len(s)
        self.hash1 = [0] * (self.n + 1)
        self.hash2 = [0] * (self.n + 1)
        self.power1 = [1] * (self.n + 1)
        self.power2 = [1] * (self.n + 1)
        for i, e in enumerate(s):
            self.hash1[i + 1] = (self.hash1[i] * self.__class__.BASE1 + ord(e)) % self.__class__.MOD1
            self.hash2[i + 1] = (self.hash2[i] * self.__class__.BASE2 + ord(e)) % self.__class__.MOD2
            self.power1[i + 1] = (self.power1[i] * self.__class__.BASE1) % self.__class__.MOD1
            self.power2[i + 1] = (self.power2[i] * self.__class__.BASE2) % self.__class__.MOD2
 
    def get(self, l: int, r: int):
        res1 = self.hash1[r] - self.hash1[l] * self.power1[r - l] % self.__class__.MOD1
        if(res1 < 0):
            res1 += self.__class__.MOD1
        res2 = self.hash2[r] - self.hash2[l] * self.power2[r - l] % self.__class__.MOD2
        if(res2 < 0):
            res2 += self.__class__.MOD2
        return (res1, res2)


def func(mid): 
    dic1 = dict()

    for i in range(n-mid+1):
        res = roliha.get(i,i+mid)
        if res in dic1:
            
            if i-dic1[res] >= mid: 
                return True
            else:
                continue 
        dic1[res] = i
    return False 


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

    return ok

roliha = RollingHash(s)

print(binary_search())

Solution (Python):
def main():
  n = int(input())
  S = input()
  ans = 0
  dp = [0]*(n*n)
  for j in range(n-1, 0, -1):
    for i in range(j-1, -1, -1):
      if j == n-1:
        dp[i*n+j] = int(S[i] == S[j])
      else:
        if S[i] == S[j]:
          dp[i*n+j] = dp[i*n+j+1+n] + 1
      ans = max(ans, min(dp[i*n+j], j-i))
  print(ans)
if __name__ == "__main__":
  main()

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

long=0
for i in range(N-1):
  for j in range(i+long+1,N):
    if not (S[i:j] in S[j:]):
      break
  long=max(long,j-i-1)
print(long)

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

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):
  d=S[i:]
  D=Z_algorithm(d)
  for j in range(N-i):
    ans=max(ans,min(j,D[j]))
print(ans)

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

tmp = 0
for i in range(n-1):
	for j in range(i+tmp+1, n):
		if not s[i:j] in s[j:]:
			break
	tmp = max(tmp, j-i-1)

"""
二重ループ型だが実際はO(ans N)でうごく.
"""

print(tmp)

Solution (Python):
def z_algorithm(s):
    res = [0 for _ in range(len(s))]
    res[0] = len(s)
    i, j = 1, 0
    while i < len(s):
        while i + j < len(s) and s[j] == s[i + j]:
            j += 1
        res[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while k < j and k + res[k] < j:
            res[i + k] = res[k]
            k += 1
        i += k
        j -= k
    return res

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

res = 0

for i in range(N):
    z = z_algorithm(S[i:])
    for j in range(N - i):
        res = max(res, min(j, z[j]))

print(res)

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

res = 0

for i in range(N - 1):
    for j in range(i + res, N):
        if S[i:j] not in S[j:]:
            break
    res = max(res, j - i - 1)

print(res)

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

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

for j in range(N):
    if S[j] == S[-1]:
        dp[-1][j] = 1

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

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

print(ans)

Solution (Python):





import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline




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



lb = 0
ub = n//2 + 1


def check(len):
    
    for l1 in range(n-len):
        for l2 in range(l1+len, n-len+1):
            if s[l1:l1+len] == s[l2:l2+len]:
                return True
    return False


def check3(m):
    
    dic = defaultdict(str)
    
    for i in range(n-m+1):
        s_ = s[i:i+m]
        if s_ in dic.keys():
            if dic[s_]+m<=i:
                return True
        else:
            dic[s_] = i
    return False


mod = 10**9+7
base = 1234
power = [1]*(n+1)
for i in range(1, n+1):
    power[i] = power[i-1]*base%mod

def check2(m):
    res = 0
    for i in range(m):
        res+=s[i]*power[m-i-1]
        res%=mod

    dic = {res: 0}
    
    
    

    for i in range(n-m):
        res = ((res-s[i]*power[m-1])*base
                             +s[i+m])%mod
        if res in dic.keys():
            index = dic[res]
            if index +m<=i+1:
                return True
        else:
            dic[res] = i+1
    return False


while ub > lb+1:
    x = (lb + ub)//2
    if check3(x):
        lb = x
    else:
        ub = x
    


'''
print(3, check(3))
print(4, check(4))
print(5, check(5))
'''

print(lb)

Solution (Python):




import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline




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



lb = 0
ub = n//2 + 1


def check(len):
    for l1 in range(n-len):
        for l2 in range(l1+len, n-len+1):
            if s[l1:l1+len] == s[l2:l2+len]:
                return True
    return False


mod = 10**9+7
base = 1234
power = [1]*(n+1)
for i in range(1, n+1):
    power[i] = power[i-1]*base%mod


def check2(m):
    res = 0
    for i in range(m):
        res+=s[i]*power[m-i-1]
        res%=mod

    dic = {res: 0}
    
    
    

    for i in range(n-m):
        res = ((res-s[i]*power[m-1])*base
                             +s[i+m])%mod
        if res in dic.keys():
            index = dic[res]
            if index +m<=i+1:
                return True
        else:
            dic[res] = i+1
    return False


def check3(m):
    dic = {}
    for i in range(n-m+1):
        s_ = s[i:i+m]
        if s_ in dic.keys():
            if dic[s_]+m<=i:
                return True
        else:
            dic[s_] = i
    return False


while ub > lb+1:
    x = (lb + ub)//2
    if check3(x):
        lb = x
    else:
        ub = x
    


'''
print(3, check(3))
print(4, check(4))
print(5, check(5))
'''

print(lb)

Solution (Python):
import random

class RollingHash(object):
    def __init__(self, S: str, MOD: int = 998244353, BASE: int = 37):
        self.S = S
        self.N = N = len(S)
        self.MOD = MOD
        self.BASE = BASE
        self.S_arr = [ord(x) for x in S]

        self.POWER = [1] * (N + 1)
        self.HASH  = [0] * (N + 1)
        p, h = 1, 0
        for i in range(N):
            self.POWER[i + 1] = p = (p * BASE) % MOD
            self.HASH[i + 1] = h = (h * BASE + self.S_arr[i]) % MOD

    def hash(self, l: int, r: int):
        
        _hash = (self.HASH[r] - self.HASH[l] * self.POWER[r - l]) % self.MOD
        return _hash








def binary_search(left: int, right: int, check_func, search_max:bool=False):
    
    while abs(right - left) > 1:
        mid = (left + right) // 2
    
        if check_func(mid) ^ search_max:
            right = mid
        else:
            left = mid

    return left if search_max else right

def main():
    N = int(input())
    S = input()
    MOD = 10 ** 18 + 3
    
    BASE = random.randint(2, MOD // 2 - 1) * 2 + 1
    rs = RollingHash(S, MOD=MOD, BASE=BASE)

    D = [0] * N
    
    
    def isOK(L):
        if L == 0:
            return True
        
        for i in range(min(L, N - 2 * L + 1)):
            D[i] = rs.hash(i, i + L)
        hashes = set()
        for i in range(L, N - L + 1):
            
            hashes.add(D[i - L])
            D[i] = v = rs.hash(i, i + L)
            
            if v in hashes:
                return True
        return False

    
    
    
    ans = binary_search(0, N // 2 + 1, isOK, search_max=True)
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import random

class RollingHash(object):
    def __init__(self, S: str, MOD: int = 10 ** 9 + 7, BASE: int = 10 ** 5 + 7):
        self.S = S
        self.N = N = len(S)
        self.MOD = MOD
        self.BASE = BASE
        self.S_arr = [ord(x) for x in S]

        self.POWER = [1] * (N + 1)
        self.HASH  = [0] * (N + 1)
        p, h = 1, 0
        for i in range(N):
            self.POWER[i + 1] = p = (p * BASE) % MOD
            self.HASH[i + 1] = h = (h * BASE + self.S_arr[i]) % MOD

    def hash(self, l: int, r: int):
        
        _hash = (self.HASH[r] - self.HASH[l] * self.POWER[r - l]) % self.MOD
        return _hash







def binary_search(left: int, right: int, check_func, search_max:bool=False):
    
    while abs(right - left) > 1:
        mid = (left + right) // 2
    
        if check_func(mid) ^ search_max:
            right = mid
        else:
            left = mid

    return left if search_max else right

def main():
    N = int(input())
    S = input()
    MOD = 998244353
    
    BASE = random.randint(2, MOD // 2 - 1) * 2 + 1
    rs = RollingHash(S, MOD=MOD, BASE=BASE)

    D = [0] * N
    
    
    def isOK(L):
        if L == 0:
            return True
        
        for i in range(min(L, N - 2 * L + 1)):
            D[i] = rs.hash(i, i + L)
        hashes = set()
        for i in range(L, N - L + 1):
            
            hashes.add(D[i - L])
            D[i] = v = rs.hash(i, i + L)
            
            if v in hashes:
                return True
        return False

    
    
    
    ans = binary_search(0, N // 2 + 1, isOK, search_max=True)
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import random

class RollingHash(object):
    def __init__(self, S: str, MOD: int = 10 ** 9 + 7, BASE: int = 10 ** 5 + 7):
        self.S = S
        self.N = N = len(S)
        self.MOD = MOD
        self.BASE = BASE
        self.S_arr = [ord(x) for x in S]

        self.POWER = [1] * (N + 1)
        self.HASH  = [0] * (N + 1)
        p, h = 1, 0
        for i in range(N):
            self.POWER[i + 1] = p = (p * BASE) % MOD
            self.HASH[i + 1] = h = (h * BASE + self.S_arr[i]) % MOD

    def hash(self, l: int, r: int):
        
        _hash = (self.HASH[r] - self.HASH[l] * self.POWER[r - l]) % self.MOD
        return _hash







def binary_search(left: int, right: int, check_func, search_max:bool=False):
    
    while abs(right - left) > 1:
        mid = (left + right) // 2
    
        if check_func(mid) ^ search_max:
            right = mid
            
        else:
            left = mid
            

    return left if search_max else right

def main():
    N = int(input())
    S = input()
    MOD = 998244353
    BASE = 37 
    rs = RollingHash(S, MOD=MOD, BASE=BASE)

    D = [0] * N
    
    
    def isOK(L):
        if L == 0:
            return True
        
        for i in range(min(L, N - 2 * L + 1)):
            D[i] = rs.hash(i, i + L)
        hashes = set()
        for i in range(L, N - L + 1):
            
            hashes.add(D[i - L])
            D[i] = v = rs.hash(i, i + L)
            
            if v in hashes:
                return True
        return False

    
    
    
    ans = binary_search(0, N // 2 + 1, isOK, search_max=True)
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict

class RollingHash(object):
    def __init__(self, S: str, MOD: int = 10 ** 9 + 7, BASE: int = 10 ** 5 + 7):
        self.S = S
        self.N = N = len(S)
        self.MOD = MOD
        self.BASE = BASE
        
        S_arr = [ord(x) for x in S]
        POWER = [1] * (N + 1)
        HASH  = [0] * (N + 1)
        p, h = 1, 0
        for i in range(N):
            POWER[i + 1] = p = (p * BASE) % MOD
            HASH[i + 1] = h = (h * BASE + S_arr[i]) % MOD
        self.S_arr = S_arr
        self.POWER = POWER
        self.HASH = HASH

    def hash(self, l: int, r: int):
        
        _hash = (self.HASH[r] - self.HASH[l] * self.POWER[r - l]) % self.MOD
        return _hash

def main():
    N = int(input())
    S = input()
    MOD = 998244353
    rs = RollingHash(S, MOD=MOD, BASE=37)
    h, p = rs.HASH, rs.POWER

    left, right = 0, N // 2 + 1
    D = [0] * N
    while abs(right - left) > 1:
        mid = (left + right) // 2
        
        hashes = set()
        L = mid
        P = p[L]
        for i in range(min(L, N-2*L+1)):
            D[i] = (h[L+i] - h[i]*P) % MOD
        hashes = set()
        ok = False
        for i in range(L, N-L+1):
            hashes.add(D[i-L])
            D[i] = v = (h[L+i] - h[i]*P) % MOD
            if v in hashes:
                ok = True
                break
        if ok:
            left = mid
        else:
            right = mid

    print(left)

if __name__ == '__main__':
    main()

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

    def rolling_hash(s, mod, base = 37):
        l = len(s)
        h = [0]*(l + 1)
        v = 0
        for i in range(l):
            h[i+1] = v = (v * base + ord(s[i])) % mod
        pw = [1]*(l + 1)
        v = 1
        for i in range(l):
            pw[i+1] = v = v * base % mod
        return h, pw

    def chk(S, mod, D = [0]*N):
        h, pw = rolling_hash(S, mod)
        left = 0; right = N//2+1
        while left+1 < right:
            l = mid = (left + right) >> 1
            p = pw[l]
            for i in range(min(l, N-2*l+1)):
                D[i] = (h[l+i] - h[i]*p) % mod
            s = set()
            ok = 0
            for i in range(l, N-l+1):
                s.add(D[i-l])
                D[i] = v = (h[l+i] - h[i]*p) % mod
                if v in s:
                    ok = 1
                    break
            if ok:
                left = mid
            else:
                right = mid
        return left

    print(chk(S, 10**9 + 9))
solve()