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

    while abs(right - left) > 1:
        mid = (left + right) // 2
        ok = False
        hash_to_left = defaultdict(list)
        L = mid
        for i in range(N - L + 1):
            _hash = (h[i+L] - h[i] * p[L]) % MOD
            
            
            
            for j in hash_to_left[_hash]:
                if j+L <= i and S[i:i+L] == S[j:j+L]:
                    ok = True
                    break
            if ok:
                break
            hash_to_left[_hash].append(i)

    
        if ok:
            left = mid
        else:
            right = mid

    print(left)
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    
    
    
    
    
    

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

    rs = RollingHash(S, MOD=998244353, BASE=37)

    
    
    def isOK(L):
        if L == 0:
            return True
        hash_to_left = defaultdict(list)
        for i in range(N - L + 1):
            _hash = rs.hash(i, i + L)
            
            
            
            for j in hash_to_left[_hash]:
                if j+L <= i:
                    return True
            hash_to_left[_hash].append(i)

        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
        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)
        if _hash < 0:
            _hash += 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()

    rs = RollingHash(S, MOD=998244353, BASE=37)

    
    
    def isOK(L):
        if L == 0:
            return True
        hash_to_left = defaultdict(list)
        for i in range(N - L + 1):
            _hash = rs.hash(i, i + L)
            
            
            
            for j in hash_to_left[_hash]:
                if j+L <= i and S[i:i+L] == S[j:j+L]:
                    return True
            hash_to_left[_hash].append(i)

        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
        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)
        if _hash < 0:
            _hash += 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()

    rs = RollingHash(S)

    
    
    def isOK(L):
        if L == 0:
            return True
        hash_to_left = defaultdict(list)
        for i in range(N - L + 1):
            _hash = rs.hash(i, i + L)
            
            
            
            for j in hash_to_left[_hash]:
                if j+L <= i and S[i:i+L] == S[j:j+L]:
                    return True
            hash_to_left[_hash].append(i)

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

if __name__ == '__main__':
    main()

Solution (Python):

def z_algorithm(S):
    
    
    
    
    
    
    

    lenS = len(S)
    A = [0] * lenS
    i = 1; j = 0
    A[0] = lenS
    
    
    while i < lenS:
        
        
        while i + j < lenS and S[j] == S[i + j]:
            j += 1
        
        if j == 0:
            i += 1
            continue

        A[i] = j

        
        

        
        
        
        
        

        
        
        
        
        
        
        
        
        k = 1
        while k + A[k] < j and i + k < lenS:
            A[i + k] = A[k]
            k += 1
        
        
        i += k

        
        
        
        
        
        

        
        
        
        
        
        
        j -= k
    return A

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

    ans = 0

    
    
    
    

    for i in range(N-1):
        A = z_algorithm(S[i:])
        
        
        
        
        
        ans = max(ans, max([min(i, a) for i, a in enumerate(A)]))

    print(ans)

if __name__ == '__main__':
    main()

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

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

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

    print(ans)

if __name__ == "__main__":
  main()

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


class RollingHash:

    def __init__(self,string):
        base1 = 1007
        mod1 = 10**9+7

        base2 = 2009
        mod2 = 10**9+9

        self.string = string
        n = len(string)
        hash1 = [0]*(n+1)
        power1 = [1]*(n+1)

        hash2 = [0]*(n+1)
        power2 = [1]*(n+1)
        for i,e in enumerate(string):
            hash1[i+1] = (hash1[i]*base1 + ord(e))%mod1
            power1[i+1] = (power1[i]*base1)%mod1
            hash2[i+1] = (hash2[i]*base2 + ord(e))%mod2
            power2[i+1] = (power2[i]*base2)%mod2

        self.hash1 = hash1
        self.power1 = power1
        self.hash2 = hash2
        self.power2 = power2
        self.base1 = base1
        self.mod1 = mod1
        self.base2 = base2
        self.mod2 = mod2

    def calc(self,i,j):
        ans = ((self.hash1[j]-self.hash1[i]*self.power1[j-i]%self.mod1)%self.mod1)*(10**10)
        ans += (self.hash2[j]-self.hash2[i]*self.power2[j-i]%self.mod2)%self.mod2
        return ans

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

    rh = RollingHash(S)


    ans = 0
    l = 0
    r = N


    while r-l > 1:
        mid = (l+r)//2
        seen = set()
        dic = {}
        found = False
        for i in range(N-mid+1):
            if not i < i+mid-1: continue

            hash = rh.calc(i,i+mid-1)
            
            if hash in seen:
                for _i,j in dic[hash]:
                    if j < i and S[_i:j+1] == S[i:i+mid]:
                        ans = max(ans,mid)
                        found = True
                        break
                else: continue

                dic[hash].append((i,i+mid-1))
                break
            else:
                dic[hash] = [(i,i+mid-1)]
                seen.add(hash)


        if found:
            l = mid
        else:
            r = mid

    print(ans)



if __name__ == "__main__":
  main()

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

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

Solution (Python):
class RollingHash():
    def __init__(self, s, base, mod):
        self.mod = mod
        self.pw = pw = [1]*(len(s)+1)

        l = len(s)
        self.h = h = [0]*(l+1)

        v = 0
        for i in range(l):
            h[i+1] = v = (v * base + ord(s[i])) % mod
        v = 1
        for i in range(l):
            pw[i+1] = v = v * base % mod
    def get(self, l, r): 
        return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod

    def check(self, d):
        ma = {}
        for i in range(N-d+1): 
            p = self.get(i,i+d)
            if p in ma:
                if i - ma[p] >= d: 
                  return True
            else:
                ma[p] = i
        return False
            
              
N =int(input())
S = str(input())

base1 = 1007
mod1 = 10**9+7

RH = RollingHash(S,base1,mod1)

left = 0
right = N//2+1
while right - left >1:
  mid = (left+right)//2
  if RH.check(mid): 
    left = mid
  else:
    right = mid

print(left)

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

Solution (Python):









def z_algorithm(S: str):
    '''SとS[i]の最長共通接頭辞長 Z[i] の配列を返す O(len(S))'''
    Z = [-1] * len(S)  
    Z[0] = len(S)
    i = 1  
    j = 0  
    while i < len(S):
        while (i + j < len(S) 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(N - i):
        if Z[j] <= j:
            ans = max(ans, Z[j])
print(ans)

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

Solution (Python):
n = int(input())
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
    return A
ans = 0
s = input()
for i in range(n):
    string = z_algo(s[i:])
    for j in range(len(string)):
        if j  >= string[j]:
            ans = max(ans, string[j])
print(ans)

Solution (Python):
import math

import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

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

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
    for i,pi in enumerate(prefix):
        if i < pi:
            prefix[i] = i
    for pi in prefix:
        if ma < pi:
            ma = pi
    return ma

if __name__ == '__main__':
    main()

Solution (Python):
def z_algo(s):
    """https://www.youtube.com/watch?v=f6ct5PQHqM0
    """
    n = len(s)
    ret = [0] * n

    ref_frm, ref_tail = -1, -1  
    for frm in range(1, n):
        cont = max(0, min(ret[frm - ref_frm], ref_tail - frm)) if ~ref_frm else 0

        while (frm + cont < n) and (s[cont] == s[frm + cont]): cont += 1
        ret[frm] = cont
        if ref_tail < frm + cont:
            ref_tail = frm + cont
            ref_frm = frm
    ret[0] = n
    return ret


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

    ret = 0
    t = ''
    for c in reversed(S):
        
        
        
        
        t = c + t
        lcp = z_algo(t)
        for diff, len_ in enumerate(lcp):
            ret = max(ret, min(diff, len_))
    print(ret)


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
S = list(input())
dp = [[0]*(N) for _ in range(N)]
for i in range(N-1):
    if S[i] == S[N-1]:
        dp[i][N-1] = 1

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

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

Solution (Python):
def Z(S):
    n = len(S)
    LCP = [0]*n
    i = 1
    j = 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

a = 0
n, s = open(0)
for i in range(int(n)):
    for j, l in enumerate(Z(s[i:])):
        a = max(a, min(l, j))
print(a)

Solution (Python):
def z_algo(s: str) -> list:
    """LCP(0,i)のlist"""
    N = len(s)
    ret = [-1] * N
    ret[0] = N
    i, j = 1, 0
    while i < N:
        while i + j < N and s[j] == s[i + j]:
            j += 1
        ret[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < N and k + ret[k] < j:
            ret[i + k] = ret[k]
            k += 1
        i += k
        j -= k
    return ret


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

    ret = 0
    t = ''
    for c in reversed(S):
        t = c + t
        lcp = z_algo(t)
        for diff, len_ in enumerate(lcp):
            ret = max(ret, min(diff, len_))
    print(ret)


if __name__ == '__main__':
    main()

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

def z_algorithm(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
    return A


length = n

ans = 0
for i in range(length):
    temp = z_algorithm(s[i:])
    for j in range(len(temp)):
        if min(temp[j],j) > ans:
            ans = min(temp[j],j)
print(ans)

Solution (Python):
def Z_algo(S):
    N = len(S)
    result = 0
    c = 0
    Z = [0]*N
    for i in range(1, N):
        l = i - c
        if (i + Z[l] < c + Z[c]):
            Z[i] = Z[l]
        else:
            j = max(0, c + Z[c] - i)
            if i + j >= N:
                j = min(j, N-i-1)
            while(S[j] == S[i + j]):
                j += 1
                if i + j >= N:
                    break
            Z[i] = j
            c = i
        result = max(result, min(Z[i], i))
    return result

L = int(input())
P = list(input())
ans = 0

for k in range(L):
    ans = max(ans, Z_algo(P[k:]))

print(ans)

Solution (Python):
N = int(input())
S = list(input())
dp = [[0]*(N) for _ in range(N)]
for i in range(N):
  if S[-1] == S[i]:
    dp[-1][i] = 1
    dp[i][-1] = 1
  

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

Solution (Python):
import collections
n,s = int(raw_input()), raw_input()

def f(k, s):	
 	cc,q = collections.Counter(), collections.deque()
	for j in range(k - 1, len(s)):
		q.append(s[j - k + 1:j+1])
		if len(q) == k + 1: cc[q.popleft()] += 1
		if q[-1] in cc: return True	
	return False

lo,hi = 0, n/2
while(lo < hi):
	med = (lo + hi + 1) / 2
	if f(med, s):  lo = med
	else:hi = med - 1
print lo

Solution (Python):
import collections
n = int(raw_input())
s = raw_input()

def f(k, s):	
	if k == 0:
		return True
 	cc = collections.Counter()
	q = collections.deque()
	for j in range(k - 1, len(s)):
		q.append(s[j - k + 1:j+1])
		if len(q) == k + 1:
			u = q.popleft()
			cc[u] += 1
		if s[j- k+1:j+1] in cc:
			return True	
	return False
lo,hi = 0, n/2 + 1
while(lo < hi):
	med = (lo + hi + 1) / 2
	if f(med, s):
		lo = med
	else:
		hi = med - 1

print lo

Solution (Python):
import collections
n = int(raw_input())
s = raw_input()

def f(k, s):	
	if k == 0:
		return True
 	cc = collections.Counter()
	q = collections.deque()
	for j in range(k - 1, len(s)):
		q.append(s[j - k + 1:j+1])
		if len(q) == k + 1:
			u = q.popleft()
			cc[u] += 1
		if s[j- k+1:j+1] in cc:
			return True	
	return False
lo,hi = 0, n
while(lo < hi):
	med = (lo + hi + 1) / 2
	if f(med, s):
		lo = med
	else:
		hi = med - 1

print lo

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

Solution (Python):
import sys
input = sys.stdin.readline
from collections import *

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

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

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

Solution (Python):
def z_algorithm(s):
    n = len(s)
    z = [0 for i in range(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 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, z[j])
print(ans)

Solution (Python):
import numpy as np

N = int(input())
S = np.array(list(input()))


def match_length(s1, s2, m):
    x = np.zeros(len(s1) + 2, dtype=bool)
    x[1:-1] = (s1 == s2)

    l = max(np.diff(np.nonzero(x == 0)[0]) - 1)
    return min(m, l)


ans = 0
for i in range(1, N - 1):
    ans = max(ans, match_length(S[i:], S[:-i], i))
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import *

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

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

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

Solution (Python):
import sys
input = sys.stdin.readline
from collections import *

def judge(x):
    d = defaultdict(int)
    q = deque([])
    
    for i in range(x):
        q.append(S[i])
        
    d[''.join(q)] = 0
    
    for i in range(x, N):
        q.append(S[i])
        q.popleft()
        k = ''.join(q)
        
        if k in d:
            if i-x+1-d[k]>=x:
                return True
        else:
            d[k] = i-x+1
    
    return False

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

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

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

s = list(s)
s.reverse()
import copy
ans = 0
for i in range(n):
    if i != 0:
        s.pop()
    t = copy.copy(s)
    t.reverse()
    t = ''.join(t)
    Z = z_algorithm(t)
    for i, z in enumerate(Z):
        ans = max(ans, min(i, z))
print(ans)

Solution (Python):
from sys import stdin
def main():
    
    readline=stdin.readline
    n=int(readline())
    s=readline().strip()

    ans=0
    for i in range(n):
        res=z_algorithm(s[i:])
        for j in range(n-i):
            ans=max(ans,min(res[j],j))

    print(ans)

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

if __name__=="__main__":
    main()

Solution (Python):
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

N = ri()
S = rs()

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

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

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

def Zalgo(S):
    N = len(S)
    A = [0]*N

    froms = -1
    lasts = -1
    for i in range(1, N):
        same = 0
        if froms != -1:
            same = min(A[i-froms], lasts-i)
            same = max(0, same)
        while i+same<N and S[same] == S[i+same]:
            same += 1
        
        if i+same > lasts:
            lasts = i+same
            froms = i
        A[i] = same
    A[0] = N
    return A

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

ans = 0
for i in range(N):
    A = Zalgo(S[i:])
    res = 0
    L = len(A)
    for j,a in enumerate(A):
        res = max(res, min(j, a))
    ans = max(res, ans)
print(ans)

Solution (Python):
m = int(input())
s = input().rstrip()
def zalgo(s):
  n = len(s)
  lcp = [0]*n
  lcp[0] = n
  i = 1
  j = 0
  while i < n:
    while i+j < n and s[j] == s[i+j]:
      j += 1
    lcp[i] = j
    if j == 0:
      i += 1
      continue
    k = 1
    while i+k < n and k+lcp[k] < j:
      lcp[i+k] = lcp[k]
      k += 1
    i += k
    j -= k
  return lcp
ans = 0
for i in range(m):
  ss = s[i:]
  lcp = zalgo(ss)
  ans = max([ans]+[min(lcp[j],j) for j in range(m-i)])
print(ans)

Solution (Python):
from collections import defaultdict as dd
N = int(input())
s = str(input())
maxlen = N//2

def solve(tgt):
    dic = dd(int)
    st = s[tgt:2*tgt]
    dic[st] += 1
    ls = [st]
    for char in s[2*tgt:]:
        st = st[1:]+char
        dic[st] += 1
        ls.append(st)
    st = s[:tgt]
    if dic[st] > 0:
        return True
    dic[ls[0]] -= 1
    for i,char in enumerate(s[tgt:N-tgt]):
        st = st[1:]+char
        if dic[st] > 0:
            return True
        dic[ls[i+1]] -= 1
    return False

ng = maxlen + 1
ok = 0
while ng-ok > 1:
    tgt = (ok+ng)//2
    if solve(tgt):
        ok = tgt
    else:
        ng = tgt
print(ok)

Solution (Python):
from collections import defaultdict as dd
N = int(input())
s = str(input())
maxlen = N//2

def solve(tgt):
    dic = dd(int)
    st = s[tgt:2*tgt]
    dic[st] += 1
    ls = [st]
    for char in s[2*tgt:]:
        st = st[1:]+char
        dic[st] += 1
        ls.append(st)
    st = s[:tgt]
    if dic[st] > 0:
        return True
    dic[ls[0]] -= 1
    for i,char in enumerate(s[tgt:N-tgt]):
        st = st[1:]+char
        if dic[st] > 0:
            return True
        dic[ls[i+1]] -= 1
    return False

ng = maxlen + 1
ok = 0
while ng-ok > 1:
    tgt = (ok+ng)//2
    if solve(tgt):
        ok = tgt
    else:
        ng = tgt
print(ok)

Solution (Python):
def solve():
    N = int(input())
    Ss = input().rstrip()

    dp = [[0]*(N+1) for _ in range(N+1)]
    for i in reversed(range(N)):
        for j in reversed(range(N)):
            if Ss[i] == Ss[j]:
                dp[i][j] = dp[i+1][j+1] + 1
            else:
                dp[i][j] = 0

    ans = 0
    for i in range(N):
        for j in range(N):
            L = j-i if j-i <= dp[i][j] else dp[i][j]
            if L > ans:
                ans = L

    print(ans)


solve()

Solution (Python):
def solve():
    N = int(input())
    Ss = input().rstrip()

    def isOK(L):
        setCand = set()
        RHs = []
        for i in range(N-L+1):
            RH = hash(Ss[i:i+L])
            RHs.append(RH)
            if i-L >= 0:
                setCand.add(RHs[i-L])
            if RH in setCand:
                return True
        return False

    ng, ok = N//2+1, 0
    while abs(ok-ng) > 1:
        mid = (ng+ok) // 2
        if isOK(mid):
            ok = mid
        else:
            ng = mid

    print(ok)


solve()

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):
def main():
  n = int(input())
  S = input()
  ans = 0
  dp = [[0]*n for _ in range(n)]
  for j in range(n-1, 0, -1):
    for i in range(j-1, -1, -1):
      if j == n-1:
        dp[i][j] = int(S[i] == S[j])
      else:
        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)
if __name__ == "__main__":
  main()

Solution (Python):
n = int(input())
S = input()
dp = [[0]*n for _ in range(n)]
for i in range(n-1, -1, -1):
  for j in range(n-1, -1, -1):
    if i == n-1:
      dp[i][j] = int(S[i] == S[j])
    elif j == n-1:
      dp[i][j] = dp[j][i]
    else:
      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):
    ans = max(ans, min(dp[i][j], j-i))
print(ans)

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N = NI()
    S = SI()
    dp = [[0] * (N+1) for _ in range(N)]

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

if __name__ == '__main__':
    main()