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):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def bisect(l,r,f,discrete=True,left=True):
    """
    l,r: l<r int if discrete else float
    f: function defined on [l,...,r] to {False,True}
    if discrete: f defined on Z; else: R
    if left: f satisfies that there uniquely exists d such that iff i<=d then f(i)
    else: iff i>=d then f(i) is True
    return d such as those above
    """
    assert r>l
    if discrete: assert isinstance(l,int) and isinstance(r,int)
    eps=1 if discrete else 10**-12
    if (not left)^f(r): return r if left else r+1
    elif left^f(l): return l-1 if left else l
    while(r-l>eps):
        h=(l+r)//2 if discrete else (l+r)/2
        if (not left)^f(h): l=h
        else: r=h
    return h if not discrete else l if left else r

class RollingHash(object):
    """
    construct: O(N)
    get_hash: O(1)
    LCP: O(logN)
    """
    def __init__(self,S,m1=10**9+9,b1=1007,m2=10**9+7,b2=1009):
        """
        S: string
        m1>m2: prime sufficiently large
        b1,b2: base 0<bi<mi
        """
        assert m1>m2 and 0<b1<m1 and 0<b2<m2
        n=len(S)
        self.__n=n
        self.__m1=m1
        self.__m2=m2
        self.__H1,self.__H2=[0]*(n+1),[0]*(n+1)
        self.__P1,self.__P2=[1]*(n+1),[1]*(n+1)
        for i,s in enumerate(S):
            self.__H1[i+1]=(self.__H1[i]*b1+ord(s))%m1
            self.__H2[i+1]=(self.__H2[i]*b2+ord(s))%m2
            self.__P1[i+1]=self.__P1[i]*b1%m1
            self.__P2[i+1]=self.__P2[i]*b2%m2

    @property
    def len(self):
        return self.__n

    def hash(self,l,r=None):
        """
        l,r: int (0<=l<=r<=n)
        return (hash1,hash2) of S[l:r]
        """
        if r is None: r=self.len
        assert 0<=l<=r<=self.len
        return ((self.__H1[r]-self.__P1[r-l]*self.__H1[l]%self.__m1)%self.__m1,(self.__H2[r]-self.__P2[r-l]*self.__H2[l]%self.__m2)%self.__m2)

    def LCP(self,l1,r1=None,rh2=None,l2=0,r2=None):
        if r1 is None: r1=self.len
        if rh2 is None: rh2=self
        if r2 is None: r2=rh2.len
        assert 0<=l1<=r1<=self.len and 0<=l2<=r2<=rh2.len
        L=0
        R=min(r1-l1,r2-l2)
        if self.hash(l1,l1+R)==rh2.hash(l2,l2+R): return R
        while(R-L>1):
            H=(L+R)//2
            if self.hash(l1,l1+H)==rh2.hash(l2,l2+H): L=H
            else: R=H
        return L

def resolve():
    n=int(input())
    S=input()
    
    rh=RollingHash(S)
    def judge(d):
        
        J={rh.hash(i,i+d):-1 for i in range(n-d+1)}
        for i in range(n-d+1):
            h=rh.hash(i,i+d)
            if J[h]!=-1:
                if i-J[h]>=d: return True
            else: J[h]=i
        return False
    print(bisect(0,n,judge))
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def bisect(l,r,f,discrete=True,left=True):
    """
    l,r: l<r int if discrete else float
    f: function defined on [l,...,r] to {False,True}
    if discrete: f defined on Z; else: R
    if left: f satisfies that there uniquely exists d such that iff i<=d then f(i)
    else: iff i>=d then f(i) is True
    return d such as those above
    """
    assert r>l
    if discrete: assert isinstance(l,int) and isinstance(r,int)
    eps=1 if discrete else 10**-12
    if (not left)^f(r): return r if left else r+1
    elif left^f(l): return l-1 if left else l
    while(r-l>eps):
        h=(l+r)//2 if discrete else (l+r)/2
        if (not left)^f(h): l=h
        else: r=h
    return h if not discrete else l if left else r

class RollingHash(object):
    """
    construct: O(N)
    get_hash: O(1)
    LCP: O(logN)
    """
    def __init__(self,S,m1=10**9+9,b1=1007,m2=10**9+7,b2=2009):
        """
        S: string
        m1>m2: prime sufficiently large
        b1,b2: base 0<bi<mi
        """
        assert m1>m2 and 0<b1<m1 and 0<b2<m2
        n=len(S)
        self.__n=n
        self.__m1=m1
        self.__m2=m2
        self.__H1,self.__H2=[0]*(n+1),[0]*(n+1)
        self.__P1,self.__P2=[1]*(n+1),[1]*(n+1)
        for i,s in enumerate(S):
            self.__H1[i+1]=(self.__H1[i]*b1+ord(s))%m1
            self.__H2[i+1]=(self.__H2[i]*b2+ord(s))%m2
            self.__P1[i+1]=self.__P1[i]*b1%m1
            self.__P2[i+1]=self.__P2[i]*b2%m2

    @property
    def len(self):
        return self.__n

    def hash(self,l,r=None):
        """
        l,r: int (0<=l<=r<=n)
        return (hash1,hash2) of S[l:r]
        """
        if r is None: r=self.len
        assert 0<=l<=r<=self.len
        return ((self.__H1[r]-self.__P1[r-l]*self.__H1[l]%self.__m1)%self.__m1,(self.__H2[r]-self.__P2[r-l]*self.__H2[l]%self.__m2)%self.__m2)

    def LCP(self,l1,r1=None,rh2=None,l2=0,r2=None):
        if r1 is None: r1=self.len
        if rh2 is None: rh2=self
        if r2 is None: r2=rh2.len
        assert 0<=l1<=r1<=self.len and 0<=l2<=r2<=rh2.len
        L=0
        R=min(r1-l1,r2-l2)
        if self.hash(l1,l1+R)==rh2.hash(l2,l2+R): return R
        while(R-L>1):
            H=(L+R)//2
            if self.hash(l1,l1+H)==rh2.hash(l2,l2+H): L=H
            else: R=H
        return L

def resolve():
    n=int(input())
    S=input()
    
    rh=RollingHash(S)
    def judge(d):
        
        
        J={rh.hash(i,i+d):-1 for i in range(n-d+1)}
        for i in range(n-d+1):
            h=rh.hash(i,i+d)
            if J[h]!=-1:
                if i-J[h]>=d: return True
            else: J[h]=i
        return False
    print(bisect(0,n,judge))
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def bisect(l,r,f,discrete=True,left=True):
    """
    l,r: l<r int if discrete else float
    f: function defined on [l,...,r] to {False,True}
    if discrete: f defined on Z; else: R
    if left: f satisfies that there uniquely exists d such that iff i<=d then f(i)
    else: iff i>=d then f(i) is True
    return d such as those above
    """
    assert r>l
    if discrete: assert isinstance(l,int) and isinstance(r,int)
    eps=1 if discrete else 10**-12
    if (not left)^f(r): return r if left else r+1
    elif left^f(l): return l-1 if left else l
    while(r-l>eps):
        h=(l+r)//2 if discrete else (l+r)/2
        if (not left)^f(h): l=h
        else: r=h
    return h if not discrete else l if left else r

class RollingHash(object):
    """
    construct: O(N)
    get_hash: O(1)
    LCP: O(logN)
    """
    def __init__(self,S,m1=10**9+9,b1=1007,m2=10**9+7,b2=2009):
        """
        S: string
        m1>m2: prime sufficiently large
        b1,b2: base 0<bi<mi
        """
        assert m1>m2 and 0<b1<m1 and 0<b2<m2
        n=len(S)
        self.__n=n
        self.__m1=m1
        self.__m2=m2
        self.__H1,self.__H2=[0]*(n+1),[0]*(n+1)
        self.__P1,self.__P2=[1]*(n+1),[1]*(n+1)
        for i,s in enumerate(S):
            self.__H1[i+1]=(self.__H1[i]*b1+ord(s))%m1
            self.__H2[i+1]=(self.__H2[i]*b2+ord(s))%m2
            self.__P1[i+1]=self.__P1[i]*b1%m1
            self.__P2[i+1]=self.__P2[i]*b2%m2
        self.__d=0
        while(m1):
            m1//=10
            self.__d+=1

    @property
    def len(self):
        return self.__n

    def hash(self,l,r=None):
        """
        l,r: int (0<=l<=r<=n)
        return hash of S[l:r]
        """
        if r is None: r=self.len
        assert 0<=l<=r<=self.len
        return (self.__H1[r]-self.__P1[r-l]*self.__H1[l]%self.__m1)%self.__m1*(10**self.__d)+(self.__H2[r]-self.__P2[r-l]*self.__H2[l]%self.__m2)%self.__m2

    def LCP(self,l1,r1=None,rh2=None,l2=0,r2=None):
        if r1 is None: r1=self.len
        if rh2 is None: rh2=self
        if r2 is None: r2=rh2.len
        assert 0<=l1<=r1<=self.len and 0<=l2<=r2<=rh2.len
        L=0
        R=min(r1-l1,r2-l2)
        if self.hash(l1,l1+R)==rh2.hash(l2,l2+R): return R
        while(R-L>1):
            H=(L+R)//2
            if self.hash(l1,l1+H)==rh2.hash(l2,l2+H): L=H
            else: R=H
        return L

def resolve():
    n=int(input())
    S=input()
    
    rh=RollingHash(S)
    def judge(d):
        
        
        J={rh.hash(i,i+d):-1 for i in range(n-d+1)}
        for i in range(n-d+1):
            h=rh.hash(i,i+d)
            if J[h]!=-1:
                if i-J[h]>=d: return True
            else: J[h]=i
        return False
    print(bisect(0,n,judge))
resolve()

Solution (Python):
N = int(input())
S = input()
l = 0
k = 1
for i in range(N - 1):
   while True:
       if S[i : i + k] in S[i + k :]:
           k += 1
       else:
           break
   l = max(l, k - 1)
print(l)

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

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

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
        else:
            dp[i][j] = 0

ans = 0
for i in range(n):
    for j in range(n):
        tmp = min(dp[i][j], abs(i-j))
        if ans < tmp:
            ans = tmp
print(ans)

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



def z_algorithm(S):
    N=len(S)
    A = [N] + [0]*(N-1)
    
    left=1
    length=0
    
    while left < N:
        
        
        while left + length < N and S[length] == S[left+length]:
            length += 1
        
        
        A[left] = length
        
        
        if length == 0:
            left+=1
            continue
        
        
        k=1
        while k+left < N and k+A[k]<length:
            A[left+k] = A[k]
            k += 1
            
        left += k
        length -= k
    return A

c=0
max_num=0
for sub in range(len(S)):
    subS = S[sub:]
    A=z_algorithm(subS)
    for i,a in enumerate(A):
        if i>=a and max_num<a:
            max_num=a
print(max_num)

Solution (Python):
N = int(input())
S = input()
ans = 0
right = 0
for left in range(N - 1):
    while right < N and (S[left : right] in S[right :]):
        right += 1
    if left == right:
        right += 1
    ans = max(ans, right - left - 1)
print(ans)

Solution (Python):
N = int(input())
S = input()
k = 1
for i in range(N - 1):
    while i + k <= N and (S[i : i + k] in S[i + k :]):
        k += 1
print(k - 1)

Solution (Python):
N = int(input())
S = input()
k = 1
for i in range(N - 1):
    while True:
        if S[i : i + k] in S[i + k :]:
            k += 1
        else:
            break
print(k - 1)

Solution (Python):
N = int(input())
S = input()
l = 0
k = 1
for i in range(N - 1):
    while True:
        if S[i : i + k] in S[i + k :]:
            k += 1
        else:
            break
    l = max(l, k - 1)
print(l)

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N = I()
    S = ST()
    
    def z_algorithm(S):
        N = len(S)
        A = [N] + [0] * (N-1)
        left = 1
        length = 0
        while left < N:
            while left+length<N and S[length] == S[left+length]:
                length += 1
            A[left] = length
            if not length:
                left += 1
                continue
            k = 1
            while k+left<N and k+A[k]<length:
                A[left+k] = A[k]
                k += 1
            
            left += k
            length -= k

        return A

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


    """
    
    def meguru_bisect(ok, ng):
        while abs(ok - ng) > 1:
            mid=(ok + ng) // 2
            if is_ok(mid):
                ok=mid
            else:
                ng=mid
        return ok

    def is_ok(l):
        for i,s in enumerate(S[:-l + 1]):
            st = S[i:i+l]
            if st in S[i+l:]:
                return True
        return False

    ans = meguru_bisect(0,len(S))
    print(ans)
    """


if __name__ == '__main__':
    main()

Solution (Python):


n = int(input())
S = input()
N = [0]*n
j = 0
 
for i in range(n):
  while S[i:j] in S[j:n]:
    N[i] = j-i
    j += 1
    
print(max(N))

Solution (Python):
N = int(input())
S = input()
r = 0
ans = 0
for i in range(N):
    while True:
        if S.rfind(S[i : r + 1]) >= r + 1:
            r += 1
            ans = max(ans, r - i)
        else:
            break
print(ans)

Solution (Python):
N = int(input())
S = input()
r = 1
ans = 0
for i in range(N):
    while True:
        if S.rfind(S[i : r + 1]) >= r + 1:
            r += 1
            ans = max(ans, r - i)
        else:
            break
print(ans)

Solution (Python):


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


ans = 0


for i in range(n):
    if n<i+ans:
        break
    
    if s[i+1:].find(s[i-ans:i+1]) != -1:
        ans += 1
        
print(ans)

Solution (Python):
def z_algo(s):
    z = [0]*len(s)
    n = len(s)
    L = 0
    R = 0
    for i in range(1, n):
        if i > R:
            L = i
            R = i
            l = 0
            while l + L < n and s[l] == s[l + i]:
                l += 1
            z[i] = l
            if l > 0:
                R = L + l - 1
        else:
            k = i - L
            right_len = R - i + 1
            if z[k] < right_len:
                z[i] = z[k]
            else:
                L = i
                l = R + 1
                while l < n and s[l - L] == s[l]:
                        l += 1
                z[i] = l - L
                R = l - 1
    return z

ans = 0
N = int(input())
S = input()

for i in range(N):
    LCP = z_algo(S[i:])
    for j, l in enumerate(LCP):
        tmp = min(l, j)
        ans = max(ans, tmp)
print(ans)

Solution (Python):

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


j = 1

for i in range(n):
    seq = s[i:i+j]
    while s[i+j:].find(seq) != -1:
        j += 1
        seq = s[i:i+j]


print(j-1)

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
  
ans = 0
N = int(input())
S = input()
for i in range(N):
    LCP = Z_algo(S[i:])
    for j, l in enumerate(LCP):
        tmp = min(l, j)
        ans = max(ans, tmp)
print(ans)

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

for i in range(n):
    
    for l in range(max_l + 1,((n - i) // 2) + 1):
        
        
        if s[i:i+l] in s[i+l:]:
            if l > max_l:
                max_l = l
        else:
            break
print(max_l)

Solution (Python):
n=int(input())
s=list(input())
f=0
b=-1
for d in range(1,n):
  c=0
  b=-1
  for i in range(n-d):
    if s[i]==s[i+d] and c<d:
      if b==-1:b=i
      c+=1
      f=max(f,c)
      if c>=d:
        break
    else:
      c=0
      b=-1
print(f)

Solution (Python):
n=int(input())
s=list(input())
f=0
b=-1
for d in range(1,n):
  c=0
  b=-1
  for i in range(n-d):
    if c>=d:
      break
    if s[i]==s[i+d]:
      if b==-1:b=i
      c+=1
      f=max(f,c)
    else:
      c=0
      b=-1
print(f)

Solution (Python):
class Rori:
  B1 = 1009
  B2 = 1007
  MOD1 = 10 ** 9 + 7
  MOD2 = 10 ** 9 + 9
  H1, H2 = None, None
  P1, P2 = None, None
  def __init__(s, L):
    n = len(L) + 1
    s.H1 = [0] * n
    s.H2 = [0] * n
    s.P1 = [1] * n
    s.P2 = [1] * n
    for i in range(n - 1):
      S = ord(L[i]) - ord('a') + 1
      s.H1[i + 1] = (s.H1[i] * s.B1 + S) % s.MOD1
      s.H2[i + 1] = (s.H2[i] * s.B2 + S) % s.MOD2
      s.P1[i + 1] = s.P1[i] * s.B1 % s.MOD1
      s.P2[i + 1] = s.P2[i] * s.B2 % s.MOD2
  def hashLR(s, l, r):
    t = (s.H1[r] - s.H1[l] * s.P1[r - l] + s.MOD1) % s.MOD1
    k = (s.H2[r] - s.H2[l] * s.P2[r - l] + s.MOD2) % s.MOD2
    return (t, k)


class AVL:
  import sys
  sys.setrecursionlimit(1000000)
  class Node:
    def __init__(s, k):
      s.k = k
      s.l = None
      s.r = None
      s.d = 1
  def __init__(s):
    s.x = None
  def l_rot(s, z):
    y = z.r
    t = y.l
    y.l, z.r = z, t
    z.d = s.get_depth(z)
    y.d = s.get_depth(y)
    return y
  def r_rot(s, z):
    y = z.l
    t = y.r
    y.r, z.l = z, t
    z.d = s.get_depth(z)
    y.d = s.get_depth(y)
    return y
  def depth(s, node):
    if not node:
      return 0
    else:
      return node.d
  def get_depth(s, node):
    return 1 + max(s.depth(node.l), s.depth(node.r))
  def add(s, k):
    s.x = s.add_sub(s.x, k)
  def add_sub(s, node, k):
    if not node:
      return s.Node(k)
    elif node.k == k:
      return node
    elif node.k > k:
      node.l = s.add_sub(node.l, k)
    else:
      node.r = s.add_sub(node.r, k)
    node.d = s.get_depth(node)
    bal = s.depth(node.l) - s.depth(node.r)
    if bal > 1:
      if node.l.k > k:
        return s.r_rot(node)
      else:
        node.l = s.l_rot(node.l)
        return s.r_rot(node)
    elif bal < -1:
      if node.r.k < k:
        return s.l_rot(node)
      else:
        node.r = s.r_rot(node.r)
        return s.l_rot(node)
    return node
  def check(s, k):
    return s.check_sub(k, s.x)
  def check_sub(s, k, node):
    if node == None:
      return False
    if node.k == k:
      return True
    if node.k > k:
      return s.check_sub(k, node.l)
    else:
      return s.check_sub(k, node.r)

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

def nasu(n):
  L = [None] * (N - n + 1)
  for i in range(len(L)):
    L[i] = R.hashLR(i, i + n)
  T = AVL()
  T.add(L[0])
  for i in range(n, len(L)):
    if T.check(L[i]):
      return True
    T.add(L[i - n + 1])
  return False

def honya(x, y, n):
  for i in range(n):
    if S[x + i] != S[y + i]:
      return i
  return n

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

R = Rori(S)
print(hersCode(N))

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

ans = 0
for l in range(N):
    
    A = [-1]*(N-l)
    c = 0
    S = WholeS[l:]
    for i, s in enumerate(S):
        if i == 0:
            continue
        if c+A[c] > i+A[i-c]:
            A[i] = A[i-c]
        else:
            j = max(0, A[c]-i+c)
            while i+j < N-l and S[j] == S[i+j]:
                j += 1
            A[i] = j
            c = i
        ans = max(ans, A[i] if(i>A[i]) else i)

print(ans)

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



lb = 0
ub = N //2 + 1
flag = False
while (ub - lb > 1):
    mid = (lb + ub) // 2
    s = set()
    for i in range(N - 2*mid + 1):
        s.add(S[i:mid+i])
        if S[mid+i:i+2*mid] in s:
            flag = True
            break
        else:
            flag = False
    if flag == True:
        lb = mid
    else:
        ub = mid
print(lb)

Solution (Python):
class ZAlgorithm(object):
    def __init__(self, s: str):
        self.orig_str = s
        self.Z = self.__create_z(s)

    def __call__(self, i: int):
        return self.Z[i]

    def __create_z(self, s: str):
        n = len(s)
        Z = [0]*n
        Z[0] = n
        l, r = 0, 0

        for t in range(1, n):
            if t>r:
                z = 0
                while t+z<n and s[0+z]==s[t+z]:
                    z += 1
                Z[t] = z
                if z>0:
                    l, r = t, t+z-1
            else:
                p, b = t-l, r-t+1
                if Z[p]<b:
                    Z[t] = Z[p]
                else:
                    i = r+1
                    while i<n and s[i]==s[i-t]:
                        i += 1
                    Z[t] = i-t
                    l, r = t, i-1
        return Z

def f_e():
    n = int(input())
    s = input()
    a = 0
    for i in range(n-1):
        ss = s[i:]
        z_algo = ZAlgorithm(ss)
        for j in range(len(ss)):
            a = max(a, min(z_algo(j), j))
    print(a)

if __name__ == "__main__":
    f_e()

Solution (Python):
def z_algorithm(S):
    """
    文字列の各インデックスについて「SとS[i: len(S) - 1]の最良共通接頭辞の長さ」を求め、
    それを記録した配列Aを O(|S|) で作成します。
    """
    A = [-1 for _ in range(len(S))]
    A[0] = len(S)
    i = 1
    j = 0
    while i < len(S):
        while i + j < len(S) and S[j] == S[i + j]:
            j += 1
        A[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < len(S) and k + A[k] < j:
            A[i + k] = A[k]
            k += 1
        i += k
        j -= k
    return A


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

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

Solution (Python):
from collections import defaultdict

CHRtoINT = defaultdict(int)
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]
for i, c in enumerate(atoz):
    CHRtoINT[c] = i


def RollingHash(S, x, b1 = 1009, b2 = 1007, m1 = 10**9+7, m2 = 10**9+9):
    h1, h2, B1, B2 = 0, 0, 1, 1
    for c in S[:x]:
        h1 = (h1 * b1 + CHRtoINT[c]) % m1
        h2 = (h2 * b2 + CHRtoINT[c]) % m2
        B1 *= b1
        B2 *= b2
    hash = [(h1, h2)] + [None] * (len(S)-x)
    for i, c in enumerate(S[:-x]):
        h1 = (h1 * b1 - CHRtoINT[c] * B1 + CHRtoINT[S[i+x]]) % m1
        h2 = (h2 * b2 - CHRtoINT[c] * B2 + CHRtoINT[S[i+x]]) % m2
        hash[i+1] = (h1, h2)
    return hash

n, S = int(input()), input()
l, r = 0, n//2+1
while l+1 < r:
    m = (l+r)//2
    OK = False
    hash = RollingHash(S, m)
    dic = defaultdict(int)
    for i, h in enumerate(hash):
        if h in dic:
            if i - dic[h] >= m:
                OK = True
                break
        else:
            dic[h] = i
    if OK:
        l = m
    else:
        r = m
print(l)

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

ans = 0
for i in range(1, n):
    cnt = 0
    for j in range(n-i):
        if s[i+j] == s[j]:
            cnt += 1
        else:
            ans = max(ans, min(cnt, i))
            cnt = 0

        if cnt >= i:
            break
    ans = max(ans, min(cnt, i))

print(ans)

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

ans = 0
for i in range(1, n):
    cnt = 0
    for j in range(n-i):
        if s[i+j] == s[j]:
            cnt += 1
        else:
            ans = max(ans, min(cnt, i))
            cnt = 0
    ans = max(ans, min(cnt, i))

print(ans)

Solution (Python):
def z_algorithm(s):
    n = len(s)
    z = [0] * n
    z[0] = n

    i = 1
    lcp = 0
    while i < n:
        while i+lcp < n and s[i+lcp] == s[lcp]:
            lcp += 1
        z[i] = lcp

        if lcp == 0:
            i += 1
            continue

        k = 1
        while i+k < n and k+z[k] < lcp:
            z[i+k] = z[k]
            k += 1
        i += k
        lcp -= k

    return z



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

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

print(ans)

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

ans = 0

for i in range(N):
  if N-i<ans:
    break
    
  if S[i+1:].find(S[i-ans:i+1])>=0:
    ans += 1
print(ans)

Solution (Python):
from collections import defaultdict
N = int(input())
S = list(map(ord, list(input())))
mod = 10**9+7
base = 1234
power = [1]*(N+1)
for i in range(1, N+1):
    power[i] = power[i-1]*base%mod
def check(m):
    if N-m<m:
        return False
    res = 0
    for i in range(m):
        res+=S[i]*power[m-i-1]
        res%=mod
    dic = defaultdict(lambda : -1)
    dic[res] = 0
    for i in range(N-m):
        res = ((res-S[i]*power[m-1])*base
                             +S[i+m])%mod
        if dic[res]>=0:
            index = dic[res]
            if index +m<=i+1:
                return True
        else:
            dic[res] = i+1
    return False
ok = 0
ng = N+1
while ng-ok>1:
    mid = (ok+ng)//2
    
    if check(mid):
        ok = mid
    else:
        ng = mid
print(ok)

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

n += 1
s += "

ans = 0
for i in range(1, n):
    cnt = 0
    for j in range(n-i):
        if s[i+j] == s[j]:
            cnt += 1
        else:
            ans = max(ans, min(cnt, i))
            cnt = 0

print(ans)

Solution (Python):
N = int(input())
S = input()
 
def zal(s):
    i = 1
    j = 0
    _N = len(s)
    Z = [0]*_N
    Z[0] = _N
    res = 0
    while i < _N:
        while i + j < _N and s[j] == s[i+j]:
            j += 1
        Z[i] = j
 
        if Z[i] <= i:
            res = max(res, Z[i])
 
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < _N and k + Z[k] < j:
            Z[i+k] = Z[k]
 
            if Z[i+k] <= i+k:
                res = max(res, Z[i+k])
 
            k += 1
        i += k
        j -= k
    return res
 
ans = 0
for i in range(N):
    _S = S[i:]
    res = zal(_S)
    ans = max(ans, res)
print(ans)

Solution (Python):
N = int(input())
S = input()
ans = 0
for i in range(N):
    if N-i<ans:
        break
    if S[i+1:].find(S[i-ans:i+1])>=0:
        ans += 1
print(ans)

Solution (Python):
N = int(input())
S = input()
mod = 10**9+7
base = 1234
power = [1]*(N+1)
for i in range(1, N+1):
    power[i] = power[i-1]*base%mod
def check(m):
    dic = {}
    for i in range(N-m+1):
        s = S[i:i+m]
        if s in dic.keys():
            if dic[s]+m<=i:
                return True
        else:
            dic[s] = i
    return False
ok = 0
ng = N+1
while ng-ok>1:
    mid = (ok+ng)//2
    
    if check(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Solution (Python):
N = int(input())
S = list(map(ord, list(input())))
mod = 10**9+7
base = 1234
power = [1]*(N+1)
for i in range(1, N+1):
    power[i] = power[i-1]*base%mod
def check(m):
    if N-m<m:
        return False
    res = 0
    for i in range(m):
        res+=S[i]*power[m-i-1]
        res%=mod
    dic = {res:0}
    for i in range(N-m):
        res = ((res-S[i]*power[m-1])*base
                             +S[i+m])%mod
        if res in dic.keys():
            index = dic[res]
            if index +m<=i+1:
                return True
        else:
            dic[res] = i+1
    return False
ok = 0
ng = N+1
while ng-ok>1:
    mid = (ok+ng)//2
    
    if check(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Solution (Python):
def f_e_dp():
    n = int(input())
    s = input()
    dp = [[0]*(n+1) for _ in range(n+1)]
    for i in reversed(range(n)):
        for j in reversed(range(n)):
            if i>=j:
                continue
            if s[i]==s[j]:
                dp[i][j] = min(j-i, dp[i+1][j+1]+1)
    print(max([sorted(r, reverse=True)[0] for r in dp]))

if __name__ == "__main__":
    f_e_dp()

Solution (Python):
def f_e_dp():
    n = int(input())
    s = input()
    dp = [[0]*(n+1) for _ in range(n+1)]
    for i in reversed(range(n)):
        for j in reversed(range(n)):
            if s[i]==s[j] and i<j:
                dp[i][j] = dp[i+1][j+1]+1
    a = 0
    for i in range(n):
        for j in range(n):
            if i<j:
                a = max(a, min(j-i, dp[i][j]))
    print(a)

if __name__ == "__main__":
    f_e_dp()

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

def check(l):
    D = []
    for i in range(N - 2 * l + 1):
        D.append(S[i : i + l])
        if S[i + l : i + 2 * l] in D:
            return True

ok = 0
ng = N // 2 + 1

while ng - ok > 1:
    m = (ok + ng) // 2
    if check(m):
        ok = m
    else:
        ng = m

print(ok)

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
ans = 0
N = int(input())
S = input()
for i in range(N):
    LCP = Z_algo(S[i:])
    for j, l in enumerate(LCP):
        tmp = min(l, j)
        ans = max(ans, tmp)
print(ans)

Solution (Python):
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N = int(input())
        S = input().rstrip()

        ans = 0
        for i in range(N - 1):
            ans = max(self.longest_common_subsequence(S[i:]), ans)

        print(ans)

    
    def longest_common_subsequence(self, s: str) -> int:
        z = [0] * len(s)
        z[0] = len(s)

        
        z_box_start, z_box_end, = 0, 0

        
        for i in range(1, len(s)):
            
            if i > z_box_end:
                
                while i + z[i] < len(s) and s[z[i]] == s[z[i] + i]:
                    z[i] += 1
                
                if z[i] > 0:
                    z_box_start, z_box_end = i, i + z[i] - 1

            
            else:
                
                
                if z[i - z_box_start] <= z_box_end - i:
                    
                    z[i] = z[i - z_box_start]

                
                else:
                    
                    check_target = z_box_end + 1
                    while check_target < len(s) and s[check_target] == s[check_target - i]:
                        check_target += 1
                    z[i] = check_target - i
                    
                    z_box_start, z_box_end = i, check_target - 1

        
        for i, v in enumerate(z):
            z[i] = min(v, i)

        
        return max(z[1:])



if __name__ == '__main__':
    AtCoder().main()