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

Solution (Python):
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def z_algo(S):
    N = len(S)
    A = [0] * N
    i = 1
    j = 0
    A[0] = l = len(S)
    while i < l:
        while i + j < l and S[j] == S[i + j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l - i > k < j - A[k]:
            A[i + k] = A[k]
            k += 1
        i += k
        j -= k

    ret = 0
    for i in range(1, N):
        ret = max(ret, min(A[i], i))

    return ret


def main():

    N = in_n()
    S = in_s()

    ans = 0
    for i in range(N):
        ans = max(ans, z_algo(S[i:]))

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
s = input() + '_'
    
dp = [[0]*(n+1) for i in range(n+1)]
for i in range(n-2, -1, -1):
    for j in range(n-1, i,-1):
        if i + dp[i+1][j+1] >= j:
            break
        if s[i] == s[j]:
            dp[i][j] = dp[i+1][j+1] + 1
print(max(list(map(lambda x: max(x), dp))))

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


def arihon_SA(T):
    rank = [0] * (n + 1)
    SA = [0] * (n + 1)
    temp = [0] * (n + 1)

    def rank_calc(i):
        res1 = rank[i]
        res2 = -1
        if i + k <= n:
            res2 = rank[i + k]
        return (res1, res2)

    for i in range(n + 1):
        SA[i] = i
        if i < n:
            rank[i] = ord(T[i])
        else:
            rank[i] = -1
    k = 1

    while k <= n:
        SA.sort(key=rank_calc)
        temp[SA[0]] = 0
        for i in range(1, n + 1):
            temp[SA[i]] = temp[SA[i - 1]]
            if rank_calc(SA[i - 1]) < rank_calc(SA[i]):
                temp[SA[i]] += 1
        rank = temp[::]
        k *= 2

    return SA





def arihon_LCP(s, SA):
    num = len(s)
    rank = [0] * (num + 1)
    LCP = [-1] * (num)
    for i in range(num + 1):
        rank[SA[i]] = i
    h = 0
    LCP[0] = 0
    for i in range(num):
        j = SA[rank[i] - 1]
        if h > 0:
            h -= 1
        while j + h < num and i + h < num:
            if s[j + h] != s[i + h]:
                break
            else:
                h += 1
        LCP[rank[i] - 1] = h
    return LCP


SA = arihon_SA(s)
LCP = arihon_LCP(s, SA)


num = n.bit_length()
ST = [[0] * (num + 1) for _ in range(n)]

for i in range(n):
    ST[i][0] = LCP[i]

for j in range(num):
    for i in range(n):
        ST[i][j + 1] = ST[i][j]
        delta = 1 << j
        if i + delta < n:
            ST[i][j + 1] = min(ST[i][j + 1], ST[i + delta][j])


def query(a, b):
    if a > b:
        a, b = b, a
    d = (b - a).bit_length() - 1
    delta = 1 << d
    res = min(ST[a][d], ST[b - delta][d])
    return res


ans = 0
for i in range(n):
    for j in range(i + 1, n + 1):
        a = SA[i]
        b = SA[j]
        temp = query(i, j)
        if abs(b - a) >= temp:
            ans = max(ans, temp)
print(ans)

Solution (Python):






base = 27  


def getnum(x):
    return ord(x) - ord("a") + 1






m30 = (1 << 30) - 1
m31 = (1 << 31) - 1
m61 = (1 << 61) - 1
mod = m61
positive_delta = m61 ** 4


def mul(a, b):
    au = a >> 31
    ad = a & m31  
    bu = b >> 31
    bd = b & m31
    mid = ad * bu + au * bd
    midu = mid >> 30
    midd = mid & m30
    return calcmod(au * bu * 2 + midu + (midd << 31) + ad * bd)


def calcmod(a):
    au = a >> 61
    ad = a & m61
    res = au + ad
    if res >= m61:
        res -= m61
    return res



def rollinghash(s):
    num = len(s)
    res = [0] * (num + 1)
    pow_base = [1] * (num + 1)
    for i in range(num):
        res[i + 1] = calcmod(mul(res[i], base) + getnum(s[i]))
        pow_base[i + 1] = calcmod(mul(pow_base[i], base))
    return res, pow_base


def search(left, right, rh):
    return calcmod(rh[right] - mul(rh[left], pow_base[right - left]) + positive_delta)


n = int(input())
s = input()
rh, pow_base = rollinghash(s)

ng = n
ok = 0


def hantei(x, rh):
    kumi = {}
    for i in range(n - x + 1):
        temp = search(i, i + x, rh)
        if temp in kumi:
            pre_idx = kumi[temp]
            if i - pre_idx >= x:
                
                return True
        else:
            kumi[temp] = i
    
    return False


while ng - ok > 1:
    mid = (ng + ok) // 2
    if hantei(mid, rh):
        ok = mid
    else:
        ng = mid
    

print(ok)

Solution (Python):






base = 27  


def getnum(x):
    return ord(x) - ord("a") + 1






m30 = (1 << 30) - 1
m31 = (1 << 31) - 1
m61 = (1 << 61) - 1
mod = m61
positive_delta = m61 ** 4


def mul(a, b):
    au = a >> 31
    ad = a & m31  
    bu = b >> 31
    bd = b & m31
    mid = ad * bu + au * bd
    midu = mid >> 30
    midd = mid & m30
    return calcmod(au * bu * 2 + midu + (midd << 31) + ad * bd)


def calcmod(a):
    au = a >> 61
    ad = a & m61
    res = au + ad
    if res >= m61:
        res -= m61
    return res



def rollinghash(s):
    num = len(s)
    res = [0] * (num + 1)
    pow_base = [1] * (num + 1)
    for i in range(num):
        res[i + 1] = calcmod(mul(res[i], base) + getnum(s[i]))
        pow_base[i + 1] = calcmod(mul(pow_base[i], base))
    return res, pow_base


def search(left, right, rh):
    return calcmod(rh[right] - mul(rh[left], pow_base[right - left]) + positive_delta)


n = int(input())
s = input()
rh, pow_base = rollinghash(s)

ng = n
ok = 0


def hantei(x, rh):
    kumi = {}
    for i in range(n - x + 1):
        temp = search(i, i + x, rh)
        if temp in kumi:
            pre_idx = kumi[temp]
            if i - pre_idx >= x:
                
                return True
        else:
            kumi[temp] = i
    
    return False


while ng - ok > 1:
    mid = (ng + ok) // 2
    if hantei(mid, rh):
        ok = mid
    else:
        ng = mid
    

print(ok)

Solution (Python):
'''
自宅用PCでの解答
'''
import math

import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def z_algorithm(s):
    ma = 0
    prefix = [0]*len(s)
    j = 0
    for i in range(1,len(s)):
        if i+prefix[i-j] < j+prefix[j]:
            prefix[i] = prefix[i-j]
        else:
            k = max(0,j+prefix[j]-i)
            while i+k < len(s) and s[k] == s[i+k]:
                k += 1
            prefix[i] = k
            j = i
    prefix[0] = len(s)
    for i,pi in enumerate(prefix):
        if i < pi:
            prefix[i] = i
    for i in prefix:
        if ma < i:
            ma = i
    return ma

def main():
    n = int(ipt())
    s = input()
    ma = 0
    for i in range(n):
        pf = z_algorithm(s[i::])
        if ma < pf:
            ma = pf

    print(ma)

    return None

if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
S = input()
ok, ng = 0, N + 1
while abs(ok - ng) > 1:
    x = (ok + ng) // 2
    check = set()
    for i in range(N - x + 1):
        check.add(S[i: i + x])
        if S[i + x: i + 2 * x] in check:
            ok = x
            break
    else:
        ng = x

print(ok)

Solution (Python):
import sys

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


def resolve():
    def ZAlgorithm(S):
        n = len(S)
        res = [0] * n
        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

    n = int(input())
    S = input()

    res = 0
    for i in range(n):
        T = S[i:]
        LCP = ZAlgorithm(T)
        for j in range(len(T)):
            l = min(LCP[j], j)
            res = max(res, l)
    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):
import random
from collections import defaultdict


def atoi(s):
    return ord(s) - ord("a") + 1


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

mod = (1 << 61) - 1
b = random.randint(10000, mod - 1)


l = 0
r = (N + 1) // 2 + 1
while r - l > 1:
    d = (r + l) // 2
    memo = defaultdict(int)
    isok = False
    h = 0
    t = pow(b, d, mod)
    for i in range(d):
        h = (h * b + atoi(S[i])) % mod
    memo[h] = 1
    for i in range(1, N - d + 1):
        h = (h*b + atoi(S[i+d-1]) - t * atoi(S[i-1])) % mod
        if not memo[h]:
            memo[h] = i + 1
        elif memo[h] and i - memo[h] + 1 >= d:
            isok = True
    if isok:
        l = d
    else:
        r = d

print(l)

Solution (Python):
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)

import sys
import numpy as np

def z_algo(S):  
    
    
    
    i, j, n = 1, 0, len(S)
    Z = np.zeros(S.shape, dtype=np.int64)
    Z[0] = n
    while i < n:
        while i+j < n and S[j] == S[i+j]:
            j += 1
        if j == 0:
            i += 1
            continue
        Z[i] = j
        d = 1
        while i+d < n and d+Z[d] < j:
            Z[i+d] = Z[d]
            d += 1
        i += d
        j -= d
    return Z

def solve(N, S):
    ans = 0
    for i in range(N):
        Z = z_algo(S[i:])
        for idx_Z, z in enumerate(Z):
            an = min(z, idx_Z)
            ans = max(ans, an)
    return ans

numba_compile([
    [z_algo, "i8[:](u1[:])"],
    [solve, "i8(i8,u1[:])"]
])

def main():
    N = int(sys.stdin.buffer.readline())
    S = np.frombuffer(sys.stdin.buffer.readline(), dtype=np.uint8).copy()
    ans = solve(N, S)
    print(ans)

main()

Solution (Python):
class RollingHash:
    def __init__(self,S,base,M):
        self.N=len(S)
        self.M=M
        self.H=[0]*(self.N+1)
        self.B=[0]*(self.N+1)
        self.B[0]=1
        for i in range(self.N):
            self.B[i+1]=self.B[i]*base%M
            self.H[i+1]=(self.H[i]*base+(ord(S[i])-96))%M
    def get(self,l,r):
        return (self.H[r]-self.H[l]*self.B[r-l]+self.M)%self.M
    def getall(self,L):
        arr=[]
        for i in range(L,self.N+1):
            arr.append(self.get(i-L,i))
        return arr

def Hash(S,base,M):
    H=0
    for c in S:
        H=(H*base+ord(c)-96)%M
    return H
    
def isbad(L):
    arr=RH.getall(L)
    s=set()
    for i in range(L,N-L+1):
        s.add(arr[i-L])
        if arr[i] in s:
            return False
    return True
    
import random
N=int(input())
S=input()
MOD=2**61-1
base=random.randrange(100,MOD)
RH=RollingHash(S,base,MOD)
l,r=-1,N+1
while(r-l>1):
    mid=(l+r)//2
    if isbad(mid):
        r=mid
    else:
        l=mid
print(l)

Solution (Python):
class RollingHash:
    def __init__(self, s):
        b1, b2 = 1007, 2009
        self.mod1, self.mod2 = 10**9+7, 10**9+9
        self.size = len(s)
        self.string = s

        self.hash1 = self.make_hashtable(b1, self.mod1)
        self.hash2 = self.make_hashtable(b2, self.mod2)
        self.pow1 = self.make_powtable(b1, self.mod1)
        self.pow2 = self.make_powtable(b2, self.mod2)

    def make_hashtable(self, B, MOD):
        hashtable = [0] * (self.size+1)
        for i in range(1, self.size+1):
            hashtable[i] = (hashtable[i-1] * B + ord(self.string[i-1]))%MOD
        return hashtable
    
    def make_powtable(self, B, MOD):
        power = [0] * (self.size+1)
        power[0] = 1
        for i in range(1, self.size+1):
            power[i] = (B * power[i-1])%MOD
        return power

    def get_hash(self, l, length):
        r = length+l-1
        l -= 1
        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)

from collections import defaultdict

def solve1():
    N = int(input())
    S = input()
    size = len(S)
    hash_table = RollingHash(S)

    ans = 0
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            if S[i-1]!=S[j-1]:continue

            left = 1
            right = min(j-i, size-j+1)+1

            while right-left>1:
                m = (left+right)//2
                if hash_table.get_hash(i, m)==hash_table.get_hash(j, m):
                    left = m
                else:
                    right = m
            ans = max(ans, left)

    print(ans)


def solve2():
    N = int(input())
    S = input()
    size = len(S)
    hash_table = RollingHash(S)

    def check(m):
        d = defaultdict(lambda :10**20)
        for i in range(1, size-m+2):
            h = hash_table.get_hash(i, m)
            d[h] = min(d[h], i)
            if (i-d[h])>=m:
                return True
        return False

    left, right = 0, size//2 + 1
    while right-left>1:
        m = (right+left)//2
        if check(m):
            left = m
        else:
            right = m

    print(left)

if __name__ == "__main__":
    
    solve2()

Solution (Python):
class RollingHash:
    def __init__(self, s):
        b1, b2 = 1007, 2009
        mod1, mod2 = 10**9+7, 10**9+9
        self.size = len(s)
        self.string = s

        self.hash1 = self.make_hashtable(b1, mod1)
        self.hash2 = self.make_hashtable(b2, mod2)
        self.pow1 = self.make_powtable(b1, mod1)
        self.pow2 = self.make_powtable(b2, mod2)

    def make_hashtable(self, B, MOD):
        hashtable = [0] * (self.size+1)
        for i in range(1, self.size+1):
            hashtable[i] = (hashtable[i-1] * B + ord(self.string[i-1]))%MOD
        return hashtable
    
    def make_powtable(self, B, MOD):
        power = [0] * (self.size+1)
        power[0] = 1
        for i in range(1, self.size+1):
            power[i] = (B * power[i-1])%MOD
        return power

    def get_hash(self, l, length):
        r = length+l-1
        l -= 1
        mod1, mod2 = 10**9+7, 10**9+9
        h1 = (self.hash1[r]-self.hash1[l]*self.pow1[r-l])%mod1
        h2 = (self.hash2[r]-self.hash2[l]*self.pow2[r-l])%mod2
        return (h1, h2)

from collections import defaultdict

def solve1():
    N = int(input())
    S = input()
    size = len(S)
    hash_table = RollingHash(S)

    ans = 0
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            if S[i-1]!=S[j-1]:continue

            left = 1
            right = min(j-i, size-j+1)+1

            while right-left>1:
                m = (left+right)//2
                if hash_table.get_hash(i, m)==hash_table.get_hash(j, m):
                    left = m
                else:
                    right = m
            ans = max(ans, left)

    print(ans)


def solve2():
    N = int(input())
    S = input()
    size = len(S)
    hash_table = RollingHash(S)

    def check(m):
        d = defaultdict(lambda :10**20)
        for i in range(1, size-m+2):
            h = hash_table.get_hash(i, m)
            d[h] = min(d[h], i)
            if (i-d[h])>=m:
                return True
        return False

    left, right = 0, size//2 + 1
    while right-left>1:
        m = (right+left)//2
        if check(m):
            left = m
        else:
            right = m

    print(left)

if __name__ == "__main__":
    
    solve2()

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

print(ans)

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

print(ans)

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

def ZA(n,s):
    Z=[0 for i in range(n)]
    Z[0]=n
    i=1
    j=0
    cand=0
    while i<n:
        while i+j<n and s[j]==s[i+j]:
            j+=1
        Z[i]=j
        cand=max(cand,min(Z[i],i))
        if j==0:
            i+=1
            continue
        k=1
        while k<j and k+Z[k]<j:
            Z[i+k]=Z[k]
            cand=max(cand,min(Z[i],i))
            k+=1
        i+=k
        j-=k
    
    return cand


ans=0
for i in range(n):
    ans=max(ans,ZA(n-i,s[i:]))
print(ans)