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()
r=[[0]*(n+1) for _ in range(n+1)]



maxV=0
for i in range(n):
  for j in  range(n):
    ii=n-1-i
    jj=n-1-j
    if s[ii]==s[jj]:
      r[ii][jj]=min(r[ii+1][jj+1]+1,abs(ii-jj))
      maxV=max(maxV,r[ii][jj])

print(maxV)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class SuffixArray(object):
    """
    construct:
        suffix array: O(N(logN)^2)
        lcp array: O(N)
        sparse table: O(NlogN)
    query:
        lcp: O(1)
    """
    def __init__(self,s):
        """
        s: str
        """
        self.__s=s
        self.__n=len(s)
        self.__suffix_array()
        self.__lcp_array()
        self.__sparse_table()

    
    def __suffix_array(self):
        s=self.__s; n=self.__n
        
        sa=list(range(n))
        rank=[ord(s[i]) for i in range(n)]
        tmp=[0]*n
        k=1
        cmp_key=lambda i:(rank[i],rank[i+k] if i+k<n else -1)
        
        while(k<=n):
            sa.sort(key=cmp_key)
            tmp[sa[0]]=0
            for i in range(1,n):
                tmp[sa[i]]=tmp[sa[i-1]]+(cmp_key(sa[i-1])<cmp_key(sa[i]))
            rank=tmp[:]
            k<<=1
        self.__sa=sa
        self.__rank=rank

    
    def __lcp_array(self):
        s=self.__s; n=self.__n
        sa=self.__sa; rank=self.__rank
        lcp=[0]*n
        h=0
        for i in range(n):
            j=sa[rank[i]-1]
            if h>0: h-=1
            if rank[i]==0: continue
            while j+h<n and i+h<n and s[j+h]==s[i+h]: h+=1
            lcp[rank[i]]=h
        self.__lcp=lcp

    
    def __sparse_table(self):
        n=self.__n
        logn=max(0,(n-1).bit_length())
        table=[[0]*n for _ in range(logn)]
        table[0]=self.__lcp[:]
        
        from itertools import product
        for i,k in product(range(1,logn),range(n)):
            if k+(1<<(i-1))>=n:
                table[i][k]=table[i-1][k]
            else:
                table[i][k]=min(table[i-1][k],table[i-1][k+(1<<(i-1))])
        self.__table=table

    def lcp(self,a,b):
        """
        a,b: int 0<=a,b<n
        return LCP length between s[a:] and s[b:]
        """
        if a==b: return self.__n-a
        l,r=self.__rank[a],self.__rank[b]
        l,r=min(l,r)+1,max(l,r)+1
        i=max(0,(r-l-1).bit_length()-1)
        table=self.__table
        return min(table[i][l],table[i][r-(1<<i)])
def resolve():
    n=int(input())
    s=input()
    sa=SuffixArray(s)
    ans=0
    for i in range(n):
        for j in range(i+1,n):
            ans=max(min(j-i,sa.lcp(i,j)),ans)
    print(ans)
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class SuffixArray(object):
    """
    construct:
        suffix array: O(N(logN)^2)
        lcp array: O(N)
        sparse table: O(NlogN)
    query:
        lcp: O(1)
    """
    def __init__(self,s):
        """
        s: str
        """
        self.__s=s
        self.__n=len(s)
        self.__suffix_array()
        self.__lcp_array()
        self.__sparse_table()

    
    def __suffix_array(self):
        s=self.__s; n=self.__n
        
        sa=list(range(n))
        rank=[ord(s[i]) for i in range(n)]
        tmp=[0]*n
        k=1
        cmp_key=lambda i:(rank[i],rank[i+k] if i+k<n else -1)
        
        while(k<=n):
            sa.sort(key=cmp_key)
            tmp[sa[0]]=0
            for i in range(1,n):
                tmp[sa[i]]=tmp[sa[i-1]]+(cmp_key(sa[i-1])<cmp_key(sa[i]))
            rank=tmp[:]
            k<<=1
        self.__sa=sa
        self.__rank=rank

    
    def __lcp_array(self):
        s=self.__s; n=self.__n
        sa=self.__sa; rank=self.__rank
        lcp=[0]*n
        h=0
        for i in range(n):
            if rank[i]==0: continue
            j=sa[rank[i]-1]
            if h>0: h-=1
            while j+h<n and i+h<n and s[j+h]==s[i+h]: h+=1
            lcp[rank[i]]=h
        self.__lcp=lcp

    
    def __sparse_table(self):
        n=self.__n
        logn=max(0,(n-1).bit_length())
        table=[[0]*n for _ in range(logn)]
        table[0]=self.__lcp[:]
        
        from itertools import product
        for i,k in product(range(1,logn),range(n)):
            if k+(1<<(i-1))>=n:
                table[i][k]=table[i-1][k]
            else:
                table[i][k]=min(table[i-1][k],table[i-1][k+(1<<(i-1))])
        self.__table=table

    def lcp(self,a,b):
        """
        a,b: int 0<=a,b<n
        return LCP length between s[a:] and s[b:]
        """
        if a==b: return self.__n-a
        l,r=self.__rank[a],self.__rank[b]
        l,r=min(l,r)+1,max(l,r)+1
        i=max(0,(r-l-1).bit_length()-1)
        table=self.__table
        return min(table[i][l],table[i][r-(1<<i)])
def resolve():
    n=int(input())
    s=input()
    sa=SuffixArray(s)
    ans=0
    for i in range(n):
        for j in range(i+1,n):
            ans=max(min(j-i,sa.lcp(i,j)),ans)
    print(ans)
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    s=input()
    ans=0
    for d in range(1,n):
        count=0
        for i in range(n-d):
            if s[i]==s[i+d]: count+=1
            else: count=0
            ans=max(min(count,d),ans)
    print(ans)
resolve()

Solution (Python):
def z_advanced(s, Z_max):
    """An advanced computation of Z-values of a string."""

    Z = [0] * len(s)
    Z[0] = len(s)

    rt = 0
    lt = 0

    for k in range(1, len(s)):
        if k > rt:
            
            n = 0
            while n + k < len(s) and s[n] == s[n+k]:
                n += 1
            Z[k] = n
            if n > 0:
                lt = k
                rt = k+n-1
        else:
            

            p = k - lt  
            right_part_len = rt - k + 1

            if Z[p] < right_part_len:
                Z[k] = Z[p]
                    
            else:
                i = rt + 1
                while i < len(s) and s[i] == s[i - k]:
                    i += 1
                Z[k] = i - k

                lt = k
                rt = i - 1
                
        Z_max = max(Z_max, min(k, Z[k]))  
    
    
    return Z_max
  
N = int(input())
S = input()
Z_max = 0
for i in range(N):
    Z_max = z_advanced(S[i:], Z_max)

print(Z_max)

Solution (Python):
import sys
input = sys.stdin.readline
from operator import itemgetter

def main():
    n = int(input().strip())
    v = input().strip()
    ans = 0
    dp = [[0] * (n+1) for _ in range(n+1)]
    for i in reversed(range(n)):
        for j in reversed(range(n)):
            if v[i] == v[j]:
                dp[i][j] = dp[i+1][j+1] + 1
                ans = max(ans, min(abs(i-j), dp[i][j]))
    print(ans)
    
if __name__ == '__main__':
    main()

Solution (Python):

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


M = [0]* N
j = 0

for i in range(N):
    while S[i:j] in S[j:N]:
        M[i] = j-i
        j += 1
print(max(M))

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)
    query:
        hash: O(1)
        lcp: O(logN)
        search: O(N)
    """
    __base1=1007; __mod1=10**9
    __base2=1009; __mod2=10**7

    def __init__(self,s):
        """
        s: str
        """
        n=len(s)
        self.__s=s
        self.__n=n
        b1=self.__base1; m1=self.__mod1
        b2=self.__base2; m2=self.__mod2
        H1,H2=[0]*(n+1),[0]*(n+1)
        P1,P2=[1]*(n+1),[1]*(n+1)
        for i in range(n):
            H1[i+1]=(H1[i]*b1+ord(s[i]))%m1
            H2[i+1]=(H2[i]*b2+ord(s[i]))%m2
            P1[i+1]=P1[i]*b1%m1
            P2[i+1]=P2[i]*b2%m2
        self.__H1=H1; self.__H2=H2
        self.__P1=P1; self.__P2=P2

    @property
    def str(self):
        return self.__s

    @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]
        """
        m1=self.__mod1; m2=self.__mod2
        if r is None: r=self.__n
        assert 0<=l<=r<=self.__n
        return ((self.__H1[r]-self.__P1[r-l]*self.__H1[l]%m1)%m1,
                (self.__H2[r]-self.__P2[r-l]*self.__H2[l]%m2)%m2)

    @classmethod
    def lcp(cls,rh1,rh2,l1,l2,r1=None,r2=None):
        """
        rh1,rh2: RollingHash object
        l1,l2,r1,r2: int 0<=l1<=r1<=r1.len,0<=l2<=r2<=rh2.len
        return lcp length between rh1[l1:r1] and rh2[l2:r2]
        """
        if r1 is None: r1=rh1.__n
        if r2 is None: r2=rh2.__n
        assert 0<=l1<=r1<=rh1.__n and 0<=l2<=r2<=rh2.__n
        L=0
        R=min(r1-l1,r2-l2)
        if rh1.hash(l1,l1+R)==rh2.hash(l2,l2+R): return R
        while(R-L>1):
            H=(L+R)//2
            if rh1.hash(l1,l1+H)==rh2.hash(l2,l2+H): L=H
            else: R=H
        return L

    @classmethod
    def search(cls,pattern,text):
        """
        pattern,text: RollingHash object
        return list of index i's satisfying text[i:] starts with pattern
        """
        n=text.__n; m=pattern.__n
        res=[]
        for i in range(n-m+1):
            if text.hash(i,i+m)==pattern.hash(0,m):
                res.append(i)
        return res

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

import sys
from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """5
ababa"""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """2
xy"""
        output = """0"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """13
strangeorange"""
        output = """5"""
        self.assertIO(input, output)

if __name__ == "__main__":
    unittest.main()

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)
    query:
        hash: O(1)
        lcp: O(logN)
    """
    __base1=1007; __mod1=10**9
    __base2=1009; __mod2=10**7

    def __init__(self,S):
        """
        S: str
        """
        n=len(S)
        self.__n=n
        b1=self.__base1; m1=self.__mod1
        b2=self.__base2; m2=self.__mod2
        H1,H2=[0]*(n+1),[0]*(n+1)
        P1,P2=[1]*(n+1),[1]*(n+1)
        for i,s in enumerate(S):
            H1[i+1]=(H1[i]*b1+ord(s))%m1
            H2[i+1]=(H2[i]*b2+ord(s))%m2
            P1[i+1]=P1[i]*b1%m1
            P2[i+1]=P2[i]*b2%m2
        self.__H1=H1; self.__H2=H2
        self.__P1=P1; self.__P2=P2

    @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]
        """
        m1=self.__mod1; m2=self.__mod2
        if r is None: r=self.__n
        assert 0<=l<=r<=self.__n
        return ((self.__H1[r]-self.__P1[r-l]*self.__H1[l]%m1)%m1,
                (self.__H2[r]-self.__P2[r-l]*self.__H2[l]%m2)%m2)

    @classmethod
    def lcp(cls,rh1,rh2,l1,l2,r1=None,r2=None):
        """
        rh1,rh2: RollingHash object
        l1,l2,r1,r2: int 0<=l1<=r1<=r1.len,0<=l2<=r2<=rh2.len
        return lcp length between rh1[l1:r1] and rh2[l2:r2]
        """
        if r1 is None: r1=rh1.__n
        if r2 is None: r2=rh2.__n
        assert 0<=l1<=r1<=rh1.__n and 0<=l2<=r2<=rh2.__n
        L=0
        R=min(r1-l1,r2-l2)
        if rh1.hash(l1,l1+R)==rh2.hash(l2,l2+R): return R
        while(R-L>1):
            H=(L+R)//2
            if rh1.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()
class SuffixArray(object):
    """
    construct:
        suffix array: O(N(logN)^2)
        lcp array: O(N)
        sparse table: O(NlogN)
    query:
        lcp: O(1)
    """
    def __init__(self,s):
        """
        s: str
        """
        self.__s=s
        self.__n=len(s)
        self.__suffix_array()
        self.__lcp_array()
        self.__sparse_table()

    
    def __suffix_array(self):
        s=self.__s; n=self.__n
        
        sa=list(range(n))
        rank=[ord(s[i]) for i in range(n)]
        tmp=[0]*n
        k=1
        cmp_key=lambda i:(rank[i],rank[i+k] if i+k<n else -1)
        
        while(k<=n):
            sa.sort(key=cmp_key)
            tmp[sa[0]]=0
            for i in range(1,n):
                tmp[sa[i]]=tmp[sa[i-1]]+(cmp_key(sa[i-1])<cmp_key(sa[i]))
            rank=tmp[:]
            k<<=1
        self.__sa=sa
        self.__rank=rank

    
    def __lcp_array(self):
        s=self.__s; n=self.__n
        sa=self.__sa; rank=self.__rank
        lcp=[0]*n
        h=0
        for i in range(n):
            j=sa[rank[i]-1]
            if h>0: h-=1
            while j+h<n and i+h<n and s[j+h]==s[i+h]: h+=1
            lcp[rank[i]]=h
        self.__lcp=lcp

    
    def __sparse_table(self):
        n=self.__n
        logn=max(0,(n-1).bit_length())
        table=[[0]*n for _ in range(logn)]
        table[0]=self.__lcp[:]
        
        from itertools import product
        for i,k in product(range(1,logn),range(n)):
            if k+(1<<(i-1))>=n:
                table[i][k]=table[i-1][k]
            else:
                table[i][k]=min(table[i-1][k],table[i-1][k+(1<<(i-1))])
        self.__table=table

    def lcp(self,a,b):
        """
        a,b: int 0<=a,b<n
        return LCP length between s[a:] and s[b:]
        """
        if a==b: return self.__n-a
        l,r=self.__rank[a],self.__rank[b]
        l,r=min(l,r)+1,max(l,r)+1
        i=max(0,(r-l-1).bit_length()-1)
        table=self.__table
        return min(table[i][l],table[i][r-(1<<i)])
def resolve():
    n=int(input())
    s=input()
    sa=SuffixArray(s)
    ans=0
    for i in range(n):
        for j in range(i+1,n):
            ans=max(ans,min(sa.lcp(i,j),j-i))
    print(ans)
resolve()

Solution (Python):
class RollingHash:
    def __init__(self, s: str, base: int=1007, mod: int=10**9+7):
        self.s = s
        self.n = len(s)
        self.base = base
        self.mod = mod

        
        self.hash_cum = [0] * (self.n + 1) 
        self.base_pow = [1] * (self.n + 1) 
        for i in range(self.n):
            self.hash_cum[i+1] = (self.hash_cum[i] * base + ord(s[i])) % mod
            self.base_pow[i+1] = (self.base_pow[i] * base) % mod

    def get_hash(self, l: int, r: int) -> int:
        hash_val = self.hash_cum[r] - self.hash_cum[l] * self.base_pow[r-l] % self.mod
        if hash_val < 0:
            hash_val += self.mod
        return hash_val


class RollingHashMulti:
    def __init__(self, s: str, base_list: list=[1007, 2009], mod_list: list=[10**9+7, 10**9+9]):
        self.n = len(base_list)
        self.base_list = base_list
        self.rh_list = [RollingHash(s, base_list[i], mod_list[i]) for i in range(self.n)]

    def get_hash(self, l: int, r: int) -> tuple:
        return tuple( self.rh_list[i].get_hash(l, r) for i in range(self.n) )




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

rh = RollingHashMulti(s)

def check(x):
    hash_dict = dict()
    for i in range(n-x+1):
        hash_val = rh.get_hash(i, i+x)
        if hash_val in hash_dict:
            if i - hash_dict[hash_val] >= x:
                return True
        else:
            hash_dict[hash_val] = i
    return False


lb = 0
ub = n // 2 + 1
while ub - lb > 1:
    mid = (ub + lb) // 2
    if check(mid):
        lb = mid
    else:
        ub = mid

print(lb)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class SuffixArray:
    """
    construct:
        suffix array: O(N(logN)^2)
        lcp array: O(N)
        sparse table: O(NlogN)
    query:
        get_lcp: O(1)
    """
    def __init__(self, s):
        """
        s: str
        """
        self.__s=s
        self.__n=len(s)
        self.__suffix_array()
        self.__lcp_array()
        self.__sparse_table()

    
    def __suffix_array(self):
        s=self.__s; n=self.__n
        
        sa=list(range(n))
        rank=[ord(s[i]) for i in range(n)]
        tmp=[0]*n
        k=1
        cmp_key=lambda i:(rank[i],rank[i+k] if i+k<n else -1)
        
        while(k<=n):
            sa.sort(key=cmp_key)
            tmp[sa[0]]=0
            for i in range(1,n):
                tmp[sa[i]]=tmp[sa[i-1]]+(cmp_key(sa[i-1])<cmp_key(sa[i]))
            rank=tmp[:]
            k<<=1
        self.__sa=sa
        self.__rank=rank

    
    def __lcp_array(self):
        n=self.__n; s=self.__s;
        sa=self.__sa; rank=self.__rank
        lcp=[0]*n
        h=0
        for i in range(n):
            j=sa[rank[i]-1]
            if h > 0: h -= 1
            while j+h<n and i+h<n and s[j+h]==s[i+h]: h+=1
            lcp[rank[i]]=h
        self.__lcp=lcp

    
    def __sparse_table(self):
        n=self.__n
        logn=max(0,(n-1).bit_length())
        table=[[0]*n for _ in range(logn)]
        table[0]=list(range(n))
        
        for i in range(1,logn):
            for k in range(n):
                if k+(1<<(i-1))>=n:
                    table[i][k]=table[i-1][k]
                    continue
                if self.__lcp[table[i-1][k]]<=self.__lcp[table[i-1][k+(1<<(i-1))]]:
                    table[i][k]=table[i-1][k]
                else:
                    table[i][k]=table[i-1][k+(1<<(i-1))]
        self.__table=table

    def get_lcp(self,a,b):
        """
        a,b: int 0<=a,b<n
        return LCP length between s[a:] and s[b:]
        """
        if a==b: return self.__n-a
        l,r=self.__rank[a],self.__rank[b]
        l,r=min(l,r)+1,max(l,r)+1
        if r-l==1: return self.__lcp[l]
        i=(r-l-1).bit_length()-1
        if self.__lcp[self.__table[i][l]]<=self.__lcp[self.__table[i][r-(1<<i)]]:
            return self.__lcp[self.__table[i][l]]
        else:
            return self.__lcp[self.__table[i][r-(1<<i)]]
def resolve():
    n=int(input())
    s=input()
    sa=SuffixArray(s)
    ans=0
    for i in range(n):
        for j in range(i+1,n):
            ans=max(ans,min(sa.get_lcp(i,j),j-i))
    print(ans)
resolve()

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
 
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] = 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):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class SuffixArray:
    """
    construct:
        suffix array: O(N(logN)^2)
        lcp array: O(N)
        sparse table: O(NlogN)
    query:
        get_lcp: O(1)
    """
    def __init__(self, s):
        """
        s: str
        """
        self.__s=s
        self.__n=len(s)
        self.__suffix_array()
        self.__lcp_array()
        self.__sparse_table()

    
    def __suffix_array(self):
        s=self.__s; n=self.__n
        
        sa=list(range(n))
        rank=[ord(s[i]) for i in range(n)]
        tmp=[0]*n
        k=1
        cmp_key=lambda i:(rank[i],rank[i+k] if i+k<n else -1)
        
        while(k<=n):
            sa.sort(key=cmp_key)
            tmp[sa[0]]=0
            for i in range(1,n):
                tmp[sa[i]]=tmp[sa[i-1]]+(cmp_key(sa[i-1])<cmp_key(sa[i]))
            rank=tmp[:]
            k<<=1
        self.__sa=sa
        self.__rank=rank

    
    def __lcp_array(self):
        n=self.__n; s=self.__s;
        sa=self.__sa; rank=self.__rank
        lcp=[0]*n
        h=0
        for i in range(n):
            j=sa[rank[i]-1]
            if h > 0: h -= 1
            while j+h<n and i+h<n and s[j+h]==s[i+h]: h+=1
            lcp[rank[i]]=h
        self.__lcp=lcp

    
    def __sparse_table(self):
        n=self.__n
        logn=max(0,(n-1).bit_length())
        table=[[0]*n for _ in range(logn)]
        table[0]=list(range(n))
        
        for i in range(1,logn):
            for k in range(n):
                if k+(1<<(i-1))>=n:
                    table[i][k]=table[i-1][k]
                    continue
                if self.__lcp[table[i-1][k]]<=self.__lcp[table[i-1][k+(1<<(i-1))]]:
                    table[i][k]=table[i-1][k]
                else:
                    table[i][k]=table[i-1][k+(1<<(i-1))]
        self.__table=table

    def get_lcp(self,a,b):
        """
        a,b: int 0<=a,b<n
        return LCP length between s[a:] and s[b:]
        """
        if a==b: return self.__n-a
        l,r=self.__rank[a],self.__rank[b]
        l,r=min(l,r)+1,max(l,r)+1
        if r-l==1: return self.__lcp[l]
        i=(r-l-1).bit_length()-1
        if self.__lcp[self.__table[i][l]]<=self.__lcp[self.__table[i][r-(1<<i)]]:
            return self.__lcp[self.__table[i][l]]
        else:
            return self.__lcp[self.__table[i][r-(1<<i)]]
def resolve():
    n=int(input())
    s=input()
    sa=SuffixArray(s)
    ans=0
    for i in range(n):
        for j in range(n):
            ans=max(ans,min(sa.get_lcp(i,j),j-i))
    print(ans)
resolve()

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

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

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

Solution (Python):
n = int(input())
s = input()
res = i = j = 0
while j < n:
  t = s[i:j]
  if t in s[j:]:
    res = max(res, j - i)
    j += 1
  else:
    i += 1
print(res)

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

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

print(mx)

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