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):
N = int(input())
S = input()

dp = [[0]*N for _ in range(N)]
for i in range(1, N):
  if S[i] == S[0]:
    dp[0][i] = 1

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

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

print(ans)

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

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 i+k < n and k+Z[k] < j:
            Z[i+k] = Z[k]
            k += 1
        i += k
        j -= k
    return Z

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

Solution (Python):
def z_algo(s):
    res = [0] * len(s)
    res[0] = len(s)
    i = 1
    j = 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 i + k < len(s) and k + res[k] < j:
            res[i + k] = res[k]
            k += 1
        i += k
        j -= k
    return res


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

ans = 0
for i in range(n):
    res = z_algo(s[i:])
    for i, lcp in enumerate(res):
        ans = max(ans, min(lcp, i))
print(ans)

Solution (Python):
import types

_atcoder_code = """


__version__ = '0.0.1'
"""

atcoder = types.ModuleType('atcoder')
exec(_atcoder_code, atcoder.__dict__)

_atcoder_string_code = """
import copy
import functools
import typing


def _sa_naive(s: typing.List[int]) -> typing.List[int]:
    sa = list(range(len(s)))
    return sorted(sa, key=lambda i: s[i:])


def _sa_doubling(s: typing.List[int]) -> typing.List[int]:
    n = len(s)
    sa = list(range(n))
    rnk = copy.deepcopy(s)
    tmp = [0] * n
    k = 1
    while k < n:
        def cmp(x: int, y: int) -> bool:
            if rnk[x] != rnk[y]:
                return rnk[x] - rnk[y]
            rx = rnk[x + k] if x + k < n else -1
            ry = rnk[y + k] if y + k < n else -1
            return rx - ry
        sa.sort(key=functools.cmp_to_key(cmp))
        tmp[sa[0]] = 0
        for i in range(1, n):
            tmp[sa[i]] = tmp[sa[i - 1]] + (1 if cmp(sa[i - 1], sa[i]) else 0)
        tmp, rnk = rnk, tmp
        k *= 2
    return sa


def _sa_is(s: typing.List[int], upper: int) -> typing.List[int]:
    '''
    SA-IS, linear-time suffix array construction
    Reference:
    G. Nong, S. Zhang, and W. H. Chan,
    Two Efficient Algorithms for Linear Time Suffix Array Construction
    '''

    threshold_naive = 10
    threshold_doubling = 40

    n = len(s)

    if n == 0:
        return []
    if n == 1:
        return [0]
    if n == 2:
        if s[0] < s[1]:
            return [0, 1]
        else:
            return [1, 0]

    if n < threshold_naive:
        return _sa_naive(s)
    if n < threshold_doubling:
        return _sa_doubling(s)

    sa = [0] * n
    ls = [False] * n
    for i in range(n - 2, -1, -1):
        if s[i] == s[i + 1]:
            ls[i] = ls[i + 1]
        else:
            ls[i] = s[i] < s[i + 1]

    sum_l = [0] * (upper + 1)
    sum_s = [0] * (upper + 1)
    for i in range(n):
        if not ls[i]:
            sum_s[s[i]] += 1
        else:
            sum_l[s[i] + 1] += 1
    for i in range(upper + 1):
        sum_s[i] += sum_l[i]
        if i < upper:
            sum_l[i + 1] += sum_s[i]

    def induce(lms: typing.List[int]) -> None:
        nonlocal sa
        sa = [-1] * n

        buf = copy.deepcopy(sum_s)
        for d in lms:
            if d == n:
                continue
            sa[buf[s[d]]] = d
            buf[s[d]] += 1

        buf = copy.deepcopy(sum_l)
        sa[buf[s[n - 1]]] = n - 1
        buf[s[n - 1]] += 1
        for i in range(n):
            v = sa[i]
            if v >= 1 and not ls[v - 1]:
                sa[buf[s[v - 1]]] = v - 1
                buf[s[v - 1]] += 1

        buf = copy.deepcopy(sum_l)
        for i in range(n - 1, -1, -1):
            v = sa[i]
            if v >= 1 and ls[v - 1]:
                buf[s[v - 1] + 1] -= 1
                sa[buf[s[v - 1] + 1]] = v - 1

    lms_map = [-1] * (n + 1)
    m = 0
    for i in range(1, n):
        if not ls[i - 1] and ls[i]:
            lms_map[i] = m
            m += 1
    lms = []
    for i in range(1, n):
        if not ls[i - 1] and ls[i]:
            lms.append(i)

    induce(lms)

    if m:
        sorted_lms = []
        for v in sa:
            if lms_map[v] != -1:
                sorted_lms.append(v)
        rec_s = [0] * m
        rec_upper = 0
        rec_s[lms_map[sorted_lms[0]]] = 0
        for i in range(1, m):
            left = sorted_lms[i - 1]
            right = sorted_lms[i]
            if lms_map[left] + 1 < m:
                end_l = lms[lms_map[left] + 1]
            else:
                end_l = n
            if lms_map[right] + 1 < m:
                end_r = lms[lms_map[right] + 1]
            else:
                end_r = n

            same = True
            if end_l - left != end_r - right:
                same = False
            else:
                while left < end_l:
                    if s[left] != s[right]:
                        break
                    left += 1
                    right += 1
                if left == n or s[left] != s[right]:
                    same = False

            if not same:
                rec_upper += 1
            rec_s[lms_map[sorted_lms[i]]] = rec_upper

        rec_sa = _sa_is(rec_s, rec_upper)

        for i in range(m):
            sorted_lms[i] = lms[rec_sa[i]]
        induce(sorted_lms)

    return sa


def suffix_array(s: typing.Union[str, typing.List[int]],
                 upper: typing.Optional[int] = None) -> typing.List[int]:
    if isinstance(s, str):
        return _sa_is([ord(c) for c in s], 255)
    elif upper is None:
        n = len(s)
        idx = list(range(n))
        idx.sort(key=functools.cmp_to_key(lambda l, r: s[l] - s[r]))
        s2 = [0] * n
        now = 0
        for i in range(n):
            if i and s[idx[i - 1]] != s[idx[i]]:
                now += 1
            s2[idx[i]] = now
        return _sa_is(s2, now)
    else:
        assert 0 <= upper
        for d in s:
            assert 0 <= d <= upper

        return _sa_is(s, upper)


def lcp_array(s: typing.Union[str, typing.List[int]],
              sa: typing.List[int]) -> typing.List[int]:
    '''
    Reference:
    T. Kasai, G. Lee, H. Arimura, S. Arikawa, and K. Park,
    Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its
    Applications
    '''

    if isinstance(s, str):
        s = [ord(c) for c in s]

    n = len(s)
    assert n >= 1

    rnk = [0] * n
    for i in range(n):
        rnk[sa[i]] = i

    lcp = [0] * (n - 1)
    h = 0
    for i in range(n):
        if h > 0:
            h -= 1
        if rnk[i] == 0:
            continue
        j = sa[rnk[i] - 1]
        while j + h < n and i + h < n:
            if s[j + h] != s[i + h]:
                break
            h += 1
        lcp[rnk[i] - 1] = h

    return lcp


def z_algorithm(s: typing.Union[str, typing.List[int]]) -> typing.List[int]:
    '''
    Reference:
    D. Gusfield,
    Algorithms on Strings, Trees, and Sequences: Computer Science and
    Computational Biology
    '''

    if isinstance(s, str):
        s = [ord(c) for c in s]

    n = len(s)
    if n == 0:
        return []

    z = [0] * n
    j = 0
    for i in range(1, n):
        z[i] = 0 if j + z[j] <= i else min(j + z[j] - i, z[i - j])
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        if j + z[j] < i + z[i]:
            j = i
    z[0] = n

    return z
"""

atcoder.string = types.ModuleType('atcoder.string')
exec(_atcoder_string_code, atcoder.string.__dict__)
z_algorithm = atcoder.string.z_algorithm

from collections import deque


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

ans = 0
for i in range(n):
    zs = z_algorithm(s[i:])
    for j in range(i+1,n):
        ind = j-i
        dist = j-i
        v = min(dist,zs[ind])
        ans = max(ans,v)

print(ans)

Solution (Python):

M = int(input())
T = input()
ans = 0
for l in range(M):
    i, j = 1, 0
    S = T[l:]
    N = M-l
    Z = [0]*N
    Z[0] = N
    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 i+k < N and k+Z[k] < j:
            Z[i+k] = Z[k]
            k += 1
        i += k
        j -= k
    for i in range(N):
        ans = max(ans, min(i, Z[i]))

print(ans)

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

def gene_hash(i,j): 
    return (hash1[j]-hash1[i]*power1[j-i]%mod1)%mod1

base1 = 1007
mod1 = 10**9+7

hash1 = [0]*(n+1)
power1 = [1]*(n+1)

for i,e in enumerate(s):
    hash1[i+1] = (hash1[i]*base1 + ord(e))%mod1
    power1[i+1] = (power1[i]*base1)%mod1
    
lef = 0
rig = n//2 + 1

while rig - lef > 1:
    mid = (rig+lef)//2
    Flag = False
    for i in range(n-2*mid+1):
        if Flag:
            break
        now = gene_hash(i,i+mid)
        for j in range(i+mid,n-mid+1):
            if now == gene_hash(j,j+mid):
                Flag = True
                break
    if Flag:
        lef = mid
    else:
        rig = mid
print(lef)

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

def z_algorythm(s):
    n = len(s)
    LCP = [0]*n
    c = 0
    for i in range(1, n):
        if i + LCP[i-c] < c + LCP[c]:
            LCP[i] = LCP[i-c]
        else:
            j = max(0, c+LCP[c]-i)
            while i+j < n and s[j] == s[i+j]:
                j += 1
            LCP[i] = j
            c = i
    LCP[0] = n
    return LCP

ans = 0
for i in range(n):
    LCP = z_algorythm(s[i:])
    for j, l in enumerate(LCP):
        if j >= l:
            ans = max(ans, l)
print(ans)

Solution (Python):
n = int(input())
s = input()
left = 0
right = n // 2 + 1
while right - left > 1:
    mid = (right + left) // 2
    length = mid
    check = set()
    for i in range(n - length + 1):
        s1 = s[i:i+length]
        check.add(s1)
        if s[i+length: i + 2*length] in check:
            left = mid
            break
    else:
        right = mid
print(left)

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):
def main():
    N = int(input())
    S = input()

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

if __name__ == "__main__":
    main()

Solution (Python):
import sys
readline = sys.stdin.readline

N = int(readline())
S = readline().rstrip()

dp = [[0] * (N + 1) for i in range(N + 1)]

ans = 0
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
      if dp[i][j] > j - i:
        dp[i][j] = j - i
      if ans < dp[i][j]:
        ans = dp[i][j]
print(ans)

Solution (Python):
import sys
readline = sys.stdin.readline

N = int(readline())
S = readline().rstrip()





dp = [[0] * (N + 1) for i in range(N + 1)]

ans = 0
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
      ans = max(ans, min(dp[i][j], j - i))
print(ans)

Solution (Python):
import sys
import itertools

import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import permutations
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


N = int(input())
S = input()
dp = [[0] * 5005 for _ in range(5005)]

for i in range(N - 1, -1, -1):
    for j in range(N - 1, -1, -1):
        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(N):
        if i >= j:
            continue
        now = min(dp[i][j], j - i)
        ans = max(now, ans)
print(ans)

Solution (Python):
def z_algorithm(s):
    n = len(s)
    if(n == 0):
        return []
    if(type(s) is str):
        s2 = [0] * n
        for i, si in enumerate(s):
            s2[i] = ord(si)
        s = s2
    z = [0] * n
    j = 0
    for i in range(1, n):
        z[i] = 0 if (j + z[j] <= i) else min(j + z[j] - i, z[i-j])
        while(i+z[i] < n):
            if(s[z[i]] != s[i + z[i]]):
                break
            z[i] += 1
        if(j + z[j] < i + z[i]):
            j = i
    z[0] = n
    return z

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

ans = 0
for i in range(n-1):
    si = s[i:]
    z = z_algorithm(si)
    for j,zj in enumerate(z[1:],1):
        ans = max(ans, min(zj, j))
print(ans)

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


def z_algorithm(s):
    """
    各iについてs[0..n)とs[i..n)のLCP(Longest Common Prefix)の長さを求める
    s: str or (list of int )
    """
    n = len(s)
    if n==0:
        return []
    z = [None]*n
    z[0] = 0
    j = 0
    for i in range(1,n):
        k = 0 if j + z[j] <= i else min(j+z[j]-i, z[i-j])
        z[i] = k
        while i+k<n and s[k]==s[i+k]:
            k += 1
        z[i] = k
        if j+z[j] < i+z[i]:
            j = i
    z[0] = n
    return z
n = int(input())
s = input()
ans = 0
for i in range(n):
    z = z_algorithm(s[i:])
    val = -1
    for j in range(len(z)):
        val = max(val, min(z[j], j))
    ans = max(ans, val)

print(ans)

Solution (Python):
import sys



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


def main():
    N = int(input())
    S = list(map(ord,input()))

    ans =0
    for k in range(N+1,0,-1):
        i=0
        count =0
        while i<N-k:
            if S[i]==S[i+k]:
                count+=1
                ans =max(ans,count)
            else:
                count=0
            if count==k:
                break

            i+=1

    print(ans)









if __name__ == "__main__":
    main()

Solution (Python):
import sys



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


def main():
    N = int(input())
    S = list(input())



    ans =0
    for k in range(N+1,0,-1):
        i=0
        count =0
        while i<N-k:
            if S[i]==S[i+k]:
                count+=1
                ans =max(ans,count)
            else:
                count=0
            if count==k:
                break

            i+=1

    print(ans)









if __name__ == "__main__":
    main()

Solution (Python):
import sys



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


def main():
    N = int(input())
    S = list(input())



    ans =0
    for k in range(N+1,0,-1):
        i=0
        count =0
        while i<N-k:
            if S[i]==S[i+k]:
                count+=1
                ans =max(ans,min(count,k))
            else:
                count=0
            if ans==k:
                break

            i+=1

    print(ans)









if __name__ == "__main__":
    main()

Solution (Python):
import sys



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


def main():
    N = int(input())
    S = list(input())



    ans =0
    for k in range(N+1,0,-1):
        i=0
        count =0
        while i<N-k:
            if S[i]==S[i+k]:
                count+=1
                ans =max(ans,min(count,k))
            else:
                count=0

            i+=1

    print(ans)









if __name__ == "__main__":
    main()

Solution (Python):
import sys



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


def main():
    N = int(input())
    S = list(input())



    ans =0
    for k in range(1,N):
        i=0
        count =0
        while i<N-k:
            if S[i]==S[i+k]:
                count+=1
                ans =max(ans,min(count,k))
            else:
                count=0

            i+=1

    print(ans)









if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
s = tuple(map(lambda x: ord(x) - ord("a") + 1, input()))
base = 1007
mod = 2**61 - 1

length = n//2
b = [1] * (length + 1)
shash = [0] * (length+1)
for i in range(1, length + 1):
    b[i] = b[i-1] * base % mod
    shash[i] = (shash[i - 1] * base + s[i - 1]) % mod

for ans in reversed(range(1, length+1)):
    
    hash_ = 0
    check = {}
    
    for left in range(n - ans + 1):
        if left == 0:
            hash_ = shash[ans]
            check[hash_] = left
            
        else:
            hash_ = base * hash_ - b[ans] * s[left - 1] + s[left + ans - 1]
            hash_ %= mod
            if hash_ in check.keys():
                
                if check[hash_] <= left - ans:
                    print(ans)
                    
                    
                    
                        
                            
                            
                    
                    sys.exit()
            else:
                check[hash_] = left
                
        
print(0)

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

l,r=0,1
res=0
def check(l,r):
    
    if not l<r:
        return False
    t=S[l:r]
    s=S[r:]
    n=(r-l)
    for i in range(len(s)-n+1):
        if s[i:i+n]==t:
            return True
    return False
        


while l<N and r<N:
    if r==l:
        r+=1
    if check(l,r):
        res=max(r-l,res)
        r+=1
    else:
        l+=1
    
print(res)

Solution (Python):
import numpy as np
from numba import njit
 
@njit(cache=True)
def main(N, s):
    dpt = np.zeros((N+1, N+1), dtype=np.int16)
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            if s[j-1] == s[i-1]:
                if j - dpt[i-1][j-1] > i:
                    dpt[i][j] = dpt[i-1][j-1] + 1
 
    return np.amax(dpt)
 
if __name__ == '__main__':
    N = int(input())
    s = np.array([ord(c) for c in input()]) 
 
    print(main(N, s))

Solution (Python):
import sys









MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

def z_algorithm(s: list):
    n = len(s)
    if n == 0: return []
    z = [-1] * n
    z[0] = 0; j = 0
    for i in range(1, n):
        k = z[i] = 0 if j + z[j] <= i else min(j + z[j] - i, z[i - j])
        while i + k < n and s[k] == s[i + k]: k += 1
        z[i] = k
        if j + z[j] < i + z[i]: j = i
    z[0] = n
    return z

def z_algorithm2(s: str):
    n = len(s)
    s2 = list(map(ord, s))
    return z_algorithm(s2)

def Main():
    n = read_int()
    s = read_str()
    ans = 0
    for i in range(n):
        lcp = z_algorithm2(s[i:])
        for j, x in enumerate(lcp):
            ans = max(ans, min(j, x))
    print(ans)

if __name__ == '__main__':
    Main()

Solution (Python):
def Z_algo(S):
    n = len(S)
    LCP = [0]*n
    i = 1
    j = 0
    c = 0
    for i in range(1, n):
        
        if i+LCP[i-c] < c+LCP[c]:
            LCP[i] = LCP[i-c]
        else:
            j = max(0, c+LCP[c]-i)
            while i+j < n and S[j] == S[i+j]: j+=1
            LCP[i] = j
            c = i
    LCP[0] = n
    return LCP

x=int(input())

s=input()
ans=0

for i in range(x):
    t=s[i:]
    lst=Z_algo(t)
    for i,v in enumerate(lst):
        cnt=min(i,v)
        ans=max(ans,cnt)


print(ans)

Solution (Python):
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
from typing import overload
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def z_algo(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 < j and k + Z[k] < j:
            Z[i + k] = Z[k]
            k += 1
        
        i += k
        j -= k
    return Z


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

    res = 0
    for i in range(N - 1):
        Z = z_algo(S[i:])
        t = 0
        for i, z in enumerate(Z):
            if i < z:
                continue
            t = max(t, z)
        res = max(res, t)
        
    print(res)


if __name__ == "__main__":
    main()

Solution (Python):
from random import randint


class RollingHash:
    def __init__(self, s):
        self.base = [7073, 7577, 5445, 2742, 6972, 7547, 2267, 286, 6396, 7147,
                     3307, 188, 266, 8253, 2818, 9527, 5110, 1207, 4633, 6196,
                     309, 2646, 7533, 85, 9870, 4730, 6862, 9213, 7456, 7098,
                     6805, 674, 5821, 4864, 8061, 1826, 2219, 459, 5937, 5667,
                     9033, 5552, 7263, 2402, 9809, 3701, 7048, 2874, 8350, 6006,
                     973, 3317, 2522, 5546, 1669, 1545, 7972, 4979, 9905, 173,
                     6812, 7715, 5006, 6068, 6340, 4989, 5510, 6380, 1200, 6739,
                     5527, 4000, 6519, 3448, 2933, 6048, 3133, 1667, 9086, 8368,
                     4914, 7142, 2770, 7752, 391, 7052, 5476, 3105, 8322, 3501,
                     7454, 3167, 8730, 9002, 4564, 138, 2197, 7238, 3411, 7433][randint(0, 99)]
        self.mod = 4611686018427387903
        self.size = len(s)
        self.string = s

        self.hash = self.make_hashtable(s)
        self.pow = self.make_powtable()

    def make_hashtable(self, _s):
        hashtable = [0] * (self.size + 1)
        for i in range(self.size):
            hashtable[i + 1] = (hashtable[i] * self.base + ord(_s[i])) % self.mod
        return hashtable

    def make_powtable(self):
        power = [1] * (self.size + 1)
        for i in range(self.size):
            power[i + 1] = (self.base * power[i]) % self.mod
        return power

    def get_hash(self, left, right):
        """get hash of s[left:right]"""
        return (self.hash[right] - self.hash[left] * self.pow[right - left]) % self.mod

    def contain(self, a):
        """return a in s"""
        m = len(a)
        if m > self.size:
            return False
        hashs = self.get_hash(0, m)
        hasha = 0
        for i in range(m):
            hasha = (hasha * self.base + ord(a[i])) % self.mod
        for i in range(self.size - m + 1):
            if hasha == hashs:
                return True
            hashs = self.get_hash(i, m + i)
        return hasha == hashs


from collections import defaultdict


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


def check(m):
    d = defaultdict(lambda: 10000000)
    for i in range(n - m + 1):
        h = rh.get_hash(i, i + m)
        d[h] = min(d[h], i)
        
        if i - d[h] >= m:
            return True
    return False


l, r = 0, n // 2 + 1
while l + 1 < r:
    mid = (l + r) // 2
    if check(mid):
        l = mid
    else:
        r = mid
print(l)

Solution (Python):
from random import randint


class RollingHash:
    def __init__(self, s):
        self.base = [7073, 7577, 5445, 2742, 6972, 7547, 2267, 286, 6396, 7147,
                     3307, 188, 266, 8253, 2818, 9527, 5110, 1207, 4633, 6196,
                     309, 2646, 7533, 85, 9870, 4730, 6862, 9213, 7456, 7098,
                     6805, 674, 5821, 4864, 8061, 1826, 2219, 459, 5937, 5667,
                     9033, 5552, 7263, 2402, 9809, 3701, 7048, 2874, 8350, 6006,
                     973, 3317, 2522, 5546, 1669, 1545, 7972, 4979, 9905, 173,
                     6812, 7715, 5006, 6068, 6340, 4989, 5510, 6380, 1200, 6739,
                     5527, 4000, 6519, 3448, 2933, 6048, 3133, 1667, 9086, 8368,
                     4914, 7142, 2770, 7752, 391, 7052, 5476, 3105, 8322, 3501,
                     7454, 3167, 8730, 9002, 4564, 138, 2197, 7238, 3411, 7433][randint(0, 99)]
        self.mod = 4611686018427387903
        self.size = len(s)
        self.string = s

        self.hash = self.make_hashtable(s)
        self.pow = self.make_powtable()

    def make_hashtable(self, _s):
        hashtable = [0] * (self.size + 1)
        for i in range(self.size):
            hashtable[i + 1] = (hashtable[i] * self.base + ord(_s[i])) % self.mod
        return hashtable

    def make_powtable(self):
        power = [1] * (self.size + 1)
        for i in range(self.size):
            power[i + 1] = (self.base * power[i]) % self.mod
        return power

    def get_hash(self, left, right):
        """get hash of s[left:right]"""
        return (self.hash[right] - self.hash[left] * self.pow[right - left]) % self.mod

    def contain(self, a):
        """return a in s"""
        m = len(a)
        if m > self.size:
            return False
        hashs = self.get_hash(0, m)
        hasha = 0
        for i in range(m):
            hasha = (hasha * self.base + ord(a[i])) % self.mod
        for i in range(self.size - m + 1):
            if hasha == hashs:
                return True
            hashs = self.get_hash(i, m + i)
        return hasha == hashs


from collections import defaultdict


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


def check(m):
    d = defaultdict(lambda: 10000000)
    for i in range(n - m + 1):
        h = rh.get_hash(i, i + m)
        d[h] = min(d[h], i)
        
        if i - d[h] >= m:
            return True
    return False


l, r = 0, n // 2 + 1
while l + 1 < r:
    mid = (l + r) // 2
    if check(mid):
        l = mid
    else:
        r = mid
print(l)

Solution (Python):
from random import randint


class RollingHash:
    def __init__(self, s):
        self.base = [7073, 7577, 5445, 2742, 6972, 7547, 2267, 286, 6396, 7147,
                     3307, 188, 266, 8253, 2818, 9527, 5110, 1207, 4633, 6196,
                     309, 2646, 7533, 85, 9870, 4730, 6862, 9213, 7456, 7098,
                     6805, 674, 5821, 4864, 8061, 1826, 2219, 459, 5937, 5667,
                     9033, 5552, 7263, 2402, 9809, 3701, 7048, 2874, 8350, 6006,
                     973, 3317, 2522, 5546, 1669, 1545, 7972, 4979, 9905, 173,
                     6812, 7715, 5006, 6068, 6340, 4989, 5510, 6380, 1200, 6739,
                     5527, 4000, 6519, 3448, 2933, 6048, 3133, 1667, 9086, 8368,
                     4914, 7142, 2770, 7752, 391, 7052, 5476, 3105, 8322, 3501,
                     7454, 3167, 8730, 9002, 4564, 138, 2197, 7238, 3411, 7433][randint(0, 100)]
        self.mod = 4611686018427387903
        self.size = len(s)
        self.string = s

        self.hash = self.make_hashtable(s)
        self.pow = self.make_powtable()

    def make_hashtable(self, _s):
        hashtable = [0] * (self.size + 1)
        for i in range(self.size):
            hashtable[i + 1] = (hashtable[i] * self.base + ord(_s[i])) % self.mod
        return hashtable

    def make_powtable(self):
        power = [1] * (self.size + 1)
        for i in range(self.size):
            power[i + 1] = (self.base * power[i]) % self.mod
        return power

    def get_hash(self, left, right):
        """get hash of s[left:right]"""
        return (self.hash[right] - self.hash[left] * self.pow[right - left]) % self.mod

    def contain(self, a):
        """return a in s"""
        m = len(a)
        if m > self.size:
            return False
        hashs = self.get_hash(0, m)
        hasha = 0
        for i in range(m):
            hasha = (hasha * self.base + ord(a[i])) % self.mod
        for i in range(self.size - m + 1):
            if hasha == hashs:
                return True
            hashs = self.get_hash(i, m + i)
        return hasha == hashs


from collections import defaultdict


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


def check(m):
    d = defaultdict(lambda: 10000000)
    for i in range(n - m + 1):
        h = rh.get_hash(i, i + m)
        d[h] = min(d[h], i)
        
        if i - d[h] >= m:
            return True
    return False


l, r = 0, n // 2 + 1
while l + 1 < r:
    mid = (l + r) // 2
    if check(mid):
        l = mid
    else:
        r = mid
print(l)

Solution (Python):


def z_algo(s):
    n = len(s)
    z = [0] * n
    z[0] = n
    i, j = 1, 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 i + k < n 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_algo(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()

    dp = [0] * (N + 1)
    ans = 0

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

    print(ans)
    return


if __name__ == '__main__':
    main()