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


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

ans = 0
for i in range(N):
  lcp = build_lcp(S[i:])
  
  
  for j in range(1,len(S[i:])):
    
    if lcp[j] <= j:
      
      ans = max(ans,lcp[j])
print(ans)

Solution (Python):
def main():
    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)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    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)


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
s = input()
high = n//2
low = 1
ans = 0

while low <= high:
    t = set()
    i = (high+low)//2
    for j in range(n-i*2+1):
        t.add(s[j:i+j])
        if s[i+j:j+2*i] in t:
            if ans < i:
                ans = i
                low = i+1
                break
    if ans < i:
        high = i-1
print(ans)

Solution (Python):
n = int(input())
s = input()
high = n//2
low = 1
ans = 0

while low <= high:
    t = set()
    i = (high+low)//2
    for j in range(n-i*2+1):
        t.add(s[j:i+j])
        if s[i+j:j+2*i] in t:
            if ans < i:
                ans = i
                low = i+1
                break
    if ans < i:
        high = i-1
print(ans)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
S = input()

def Z_algorithm(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

ans = 0
for i in range(N):
    
    LCP = Z_algorithm(S[i:])
    for j, lcp in enumerate(LCP):
        
        if lcp > ans and j >= lcp:
            ans = lcp
print(ans)

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

Solution (Python):


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

dp = [[0]*(n+1) for _ in range(n+1)]
res = 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
        res = max(res, min(dp[i][j], j-i))

print(res)

Solution (Python):


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

ok = 0
ng = n//2+1

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

    d = {}
    isOk = False
    for l in range(n-mid+1):
        ss = s[l:l+mid]
        if ss not in d:
            d[ss] = l
        else:
            l2 = d[ss]
            if l2+mid<=l:
                isOk = True
                break

    if isOk:
        ok = mid
    else:
        ng = mid

print(ok)

Solution (Python):
import collections
mod=10**9+7
base=37
n=int(input())
S=list(ord(s)-96 for s in input())
B=[0]*(n+1)
B[0]=1
for i in range(n):
  B[i+1]=(B[i]*base)%mod

def chk(x):
  ret=False
  h=0
  bx=B[x]
  d=collections.defaultdict(int)
  for i in range(x):
    h=(h*base+S[i])%mod
  d[h]=x
  for i in range(x,n):
    h=(h*base+S[i]-S[i-x]*bx)%mod
    if d[h]==0:
      d[h]=i+1
    elif d[h]<=i-x+1:
      if S[d[h]-x:d[h]]==S[i-x+1:i+1]:
        ret=True
  return ret

l,r=0,n//2
while r-l>1:
  m=(l+r)//2
  if chk(m):
    l=m
  else:
    r=m
print(r if chk(r) else l)

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

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

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

Solution (Python):
import collections
mod=10**9+7
base=257
n=int(input())
S=list(ord(s)-96 for s in input())
B=[0]*(n+1)
B[0]=1
for i in range(n):
  B[i+1]=(B[i]*base)%mod

def chk(x):
  ret=False
  h=0
  bx=B[x]
  d=collections.defaultdict(int)
  for i in range(x):
    h=(h*base+S[i])%mod
  d[h]=x
  for i in range(x,n):
    h=(h*base+S[i]-S[i-x]*bx)%mod
    if d[h]==0:
      d[h]=i+1
    elif d[h]<=i-x+1:
      ret=True
  return ret

l,r=0,n//2
while r-l>1:
  m=(l+r)//2
  if chk(m):
    l=m
  else:
    r=m
print(r if chk(r) else l)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

n = I()
s = S()


def z_algorithm(S):
    l = len(S)
    A = [0] * l
    i = 1; j = 0
    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 p in range(l):
        if p >= A[p] > ret:
            ret = A[p]
    return ret


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



print(ans)

Solution (Python):
import sys

stdin = sys.stdin

sn = lambda : stdin.readline().rstrip()
an = lambda : map(int, stdin.readline().split())
ni = lambda : int(sn())

def main():
  n = ni()
  s = sn()

  i, j = 0, 1
  ans = 0
  while j < n:
    if s[i:j] in s[j:]:
      ans = max(ans, len(s[i:j]))
      j += 1
    else:
      i += 1
    if i == j:
      i += 1
      j += 2
  print(ans)

main()