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(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    def zalgo(S):
        A=[0]*len(S)
        A[0]=len(S)
        i,j=1,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):
        A=zalgo(S[i:])
        for j,x in enumerate(A):
            if x>j:
                ans=max(ans,j)
            else:
                ans=max(ans,x)
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()

class RollingHash(object):
    __base1=1007; __mod1=10**9+9
    __base2=1009; __mod2=10**9+7

    def __init__(self,s):
        self.__s=s; self.__n=len(s)
        b1=self.__base1; m1=self.__mod1
        b2=self.__base2; m2=self.__mod2
        H1,H2=[0]*(self.__n+1),[0]*(self.__n+1)
        P1,P2=[1]*(self.__n+1),[1]*(self.__n+1)
        for i in range(self.__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

    def __getitem__(self,x):
        if(isinstance(x,int)): x=slice(x,x+1)
        assert(isinstance(x,slice) and ((x.step is None) or (x.step==1)))
        l=x.start; r=x.stop;
        assert(l<=r)
        return ((self.__H1[r]-self.__P1[r-l]*self.__H1[l]%self.__mod1)%self.__mod1,
                (self.__H2[r]-self.__P2[r-l]*self.__H2[l]%self.__mod2)%self.__mod2)

def bisection(l,r,f,left=True,discrete=True):
    eps=1 if(discrete) else 10**-8
    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 (l+r)/2 if(not discrete) else l if(left) else r

from collections import defaultdict
def resolve():
    n=int(input())
    rh=RollingHash(input())

    def check(k):
        D=defaultdict(lambda:-1)
        for i in range(n-k+1):
            h=rh[i:i+k]
            if(D[h]!=-1):
                if(i-D[h]>=k):
                    return True
            else:
                D[h]=i
        return False

    print(bisection(0,n,check))
resolve()

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

ans = 0
for i in range(N):
  j_start = ans + 1
  for j in range(j_start, N-i):
    base = S[i:i+j]
    if base in S[i+j:]:
      ans = max(ans, j)
    else:
      break


print(ans)

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

ans = 0
for i in range(N):
  j_start = ans + 1
  j_end = (N - i) // 2 + 1
  for j in range(j_start, j_end):
    base = S[i:i+j]
    if base in S[i+j:]:
      ans = max(ans, j)
    else:
      break


print(ans)

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

def z_algo(S):
    N = len(S)
    Z = [0]*N
    i = 1
    j = 0
    Z[0] = N
    while i < N:
        while i+j < N and S[j] == S[i+j]:
            j += 1
        if j == 0:
            i += 1
            continue
        Z[i] = j
        k = 1
        while i+k < N and k < j-Z[k]:
            Z[i+k] = Z[k]
            k += 1
        i += k
        j -= k
    return Z

ans = 0
l = 0
while l < N:
    temp = S[l:]
    z = z_algo(temp)
    for i in range(1, len(temp)):
        ans = max(ans, min(i, z[i]))
    l += 1
    
print(ans)

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

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

ans = 0
for i in range(N):
  SS = S[i:]
  Z = z_algo(SS)
  
  for j in range(1,len(SS)):
    if Z[j] > j:
      l = j
    else:
      l = Z[j]
    ans = max(l,ans)
print(ans)

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

    ans, j = 0, 1
    for i in range(N):
        s = S[i:i+j]
        while S[i+j:].find(s) != -1:
            j += 1
            s = S[i:i+j]
            ans += 1

    print(ans)


if __name__ == '__main__':
    solve()

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

ans = 0
for dl in list(range(1, N))[::-1]:
    if dl < ans: break
    cnt = 0
    ans_tmp = 0
    for l1 in range(N - dl):
        l2 = l1 + dl
        if S[l1] == S[l2]:
            
            cnt += 1
        else:
            ans_tmp = max(ans_tmp, cnt)
            cnt = 0
    else:
        ans_tmp = max(ans_tmp, cnt)
    
    
    ans = max(ans, min(dl, ans_tmp))

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()

class RollingHash(object):
    __base1=1007; __mod1=10**9+9
    __base2=1009; __mod2=10**9+7

    def __init__(self,s):
        self.__s=s; self.__n=len(s)
        b1=self.__base1; m1=self.__mod1
        b2=self.__base2; m2=self.__mod2
        H1,H2=[0]*(self.__n+1),[0]*(self.__n+1)
        P1,P2=[1]*(self.__n+1),[1]*(self.__n+1)
        for i in range(self.__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

    def __getitem__(self,x):
        if(isinstance(x,int)): x=slice(x,x+1)
        assert(isinstance(x,slice) and ((x.step is None) or (x.step==1)))
        l=x.start; r=x.stop;
        assert(l<=r)
        return ((self.__H1[r]-self.__P1[r-l]*self.__H1[l]%self.__mod1)%self.__mod1,
                (self.__H2[r]-self.__P2[r-l]*self.__H2[l]%self.__mod2)%self.__mod2)

def bisection(l,r,f,left=True,discrete=True):
    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 (l+r)/2 if not discrete else l if left else r

from collections import defaultdict
def resolve():
    n=int(input())
    S=input()
    rh=RollingHash(S)

    def check(k):
        D=defaultdict(lambda:-1)
        for i in range(n-k+1):
            h=rh[i:i+k]
            if(D[h]!=-1):
                if(i-D[h]>=k): return True
            else:
                D[h]=i
        return False

    print(bisection(0,n,check))
resolve()

Solution (Python):


def z_algo(S):
    N = len(S)
    A = [0] * N
    i = 1
    j = 0
    while (i < N):
        while (i + j < N and S[j] == S[i + j]):
            j += 1 
        A[i] = j
        
        if j == 0:
            i += 1
            continue
        
        
        k = 1
        while (i + k < N and k + A[k] < j):
            
            
            A[i + k] = A[k]
            k += 1
        i += k 
        j -= k 

    return A

def main():
    N = int(input())
    S = input()
    res = 0
    
    
    for i in range(N):
        lcp = z_algo(S[i:])
        for j in range(len(lcp)):
            l = min(j, lcp[j])
            res = max(res, l)
    print(res)

if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict


def len_is_x(x):
    string = defaultdict(int)
    for i in range(x,N-x+1):
        string[S[i:i+x]] += 1
    for i in range(N-x+1):
        if i - x >= 0:
            string[S[i-x:i]] += 1
        if string[S[i:i+x]] >= 1:
            return True
        if i + x*2 <= N:
            string[S[i+x:i+x*2]] = max(string[S[i+x:i+x*2]]-1, 0) 
    return False

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


ng = N // 2 + 1
ok = 0

while (ng - ok) != 1:
    mid = (ok + ng) // 2
    if len_is_x(mid):
        ok = mid
    else:
        ng = mid

print(ok)

Solution (Python):
def main():

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

    i,j=0,1
    ans=0
    while j<n:
        if s[i:j] in s[j:]:
            if j-i>ans: ans=j-i
            j+=1
        else:
            i+=1
            j+=1

    print(ans)

            

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()
tdlist = lambda i, j, value=0: [[value] * j for _ in range(i)]

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

dp = tdlist(n+1, n+1)
for i in range(1, n+1):
    for j in range(1, n+1):
        if s[i-1] == s[j-1]: dp[i][j] = dp[i-1][j-1] + 1

ans = 0
for i in range(n+1):
    for j in range(n+1):
        ans = max(ans, min(abs(i-j), dp[i][j]))

print(ans)

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

res = 0
for k in range(1, N):
    cnt = 0
    for i in range(N - k):
        if i + k < N and S[i + k] == S[i]:
            cnt += 1
        else:
            cnt = 0
        cnt = min(k, cnt)
        res = max(cnt, res)

print(res)

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

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

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()

class RollingHash(object):
    __base1=1007; __mod1=10**9+9
    __base2=1009; __mod2=10**9+7

    def __init__(self,s):
        self.__s=s; self.__n=len(s)
        b1=self.__base1; m1=self.__mod1
        b2=self.__base2; m2=self.__mod2
        H1,H2=[0]*(self.__n+1),[0]*(self.__n+1)
        P1,P2=[1]*(self.__n+1),[1]*(self.__n+1)
        for i in range(self.__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

    def __getitem__(self,x):
        if(isinstance(x,int)): x=slice(x,x+1)
        assert(isinstance(x,slice) and ((x.step is None) or (x.step==1)))
        l=x.start; r=x.stop;
        assert(l<=r)
        return ((self.__H1[r]-self.__P1[r-l]*self.__H1[l]%self.__mod1)%self.__mod1,
                (self.__H2[r]-self.__P2[r-l]*self.__H2[l]%self.__mod2)%self.__mod2)

def bisection(l,r,f,left=True,discrete=True):
    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 (l+r)/2 if not discrete else l if left else r

def resolve():
    n=int(input())
    S=input()
    rh=RollingHash(S)

    from collections import defaultdict
    def check(k):
        D=defaultdict(lambda :-1)
        for i in range(n-k+1):
            hash=rh[i:i+k]
            if(D[hash]!=-1):
                if(i-D[hash]>=k): return True
            else:
                D[hash]=i
        return False

    for k in range(n):
        if(not check(k)):
            print(max(0,k-1))
            return
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()

class RollingHash(object):
    __base1=1007; __mod1=10**9+9
    __base2=1009; __mod2=10**9+7

    def __init__(self,s):
        self.__s=s; self.__n=len(s)
        b1=self.__base1; m1=self.__mod1
        b2=self.__base2; m2=self.__mod2
        H1,H2=[0]*(self.__n+1),[0]*(self.__n+1)
        P1,P2=[1]*(self.__n+1),[1]*(self.__n+1)
        for i in range(self.__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

    def __getitem__(self,x):
        if(isinstance(x,int)): x=slice(x,x+1)
        assert(isinstance(x,slice) and ((x.step is None) or (x.step==1)))
        l=x.start; r=x.stop;
        assert(l<=r)
        return ((self.__H1[r]-self.__P1[r-l]*self.__H1[l]%self.__mod1)%self.__mod1,
                (self.__H2[r]-self.__P2[r-l]*self.__H2[l]%self.__mod2)%self.__mod2)

def bisection(l,r,f,left=True,discrete=True):
    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 (l+r)/2 if not discrete else l if left else r

def resolve():
    n=int(input())
    S=input()
    rh=RollingHash(S)

    from collections import defaultdict
    def check(k):
        D=defaultdict(lambda :-1)
        for i in range(n-k+1):
            hash=rh[i:i+k]
            if(D[hash]!=-1):
                if(i-D[hash]>=k): return True
            else:
                D[hash]=i
        return False

    print(bisection(0,n,check))
resolve()

Solution (Python):
n = int(input())
s = input()
 
res = 0
dp = [[0]* (1+n) for _ in range(n+1)]
for i in range(n-1, -1, -1):
    for j in range(i+1, n):
        if s[i] == s[j]:
            dp[i][j] = dp[i+1][j+1] + (j - i > dp[i+1][j+1])
            res = max(res, dp[i][j])
print(res)

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

ans = 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
        ans = max(ans, min(i, t))

print(ans)

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

def check(length):
    d = set()
    for i in range(n - 2 * length + 1):
        d.add(s[i:i + length])
        if s[i + length:i + 2 * length] in d:
            return True
    return False
 
 
lo = 0
hi = n // 2 + 1
while lo + 1 < hi:
    mid = (lo + hi) // 2
    if check(mid):
        lo = mid
    else:
        hi = mid
if check(hi):
	print(hi)
else:
  	print(lo)

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

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


for i in reversed(range(n)):
  for j in reversed(range(n)):
    if s[i] == s[j]:
      dp[i][j] = dp[i+1][j+1]+1



ans = 0
for i in range(n-1):
  for j in range(i, n):
    ans = max(ans, min(dp[i][j], j-i))
    
print(ans)

Solution (Python):
n = int(input())
s = input()
ans = 0
for l in range(n):
    ss = s[l:]
    length = n - l
    i, j = 1, 0
    a = [0 for _ in range(length)]
    while i < length:
        while i + j < length and ss[j] == ss[i + j]:
            j += 1
        a[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < length and k + a[k] < j:
            a[i + k] = a[k]
            k += 1
        i += k
        j -= k
    for ll, al in enumerate(a):
        if al <= ll:
            ans = max(ans, al)
print(ans)

Solution (Python):
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    s = str(readline().rstrip().decode('utf-8'))
    mt = 0
    for i in range(0, n):
        zs = s[i:]
        zln = len(zs)
        zl = [0] * zln
        zi = 1
        zj = 0
        while zi < zln:
            while zi + zj < zln and zs[zj] == zs[zi+zj]:
                zj += 1
            zl[zi] = zj
            if zj == 0:
                zi += 1
                continue
            zk = 1
            while zi + zk < zln and zk + zl[zk] < zj:
                zl[zi+zk] = zl[zk]
                zk += 1
            zi += zk
            zj -= zk
        for j in range(len(zl)):
            if zl[j] <= j:
                mt = max(mt, zl[j])
    print(mt)


if __name__ == '__main__':
    solve()

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

a = 0
i = 0
j = 1

while j<N:
    if S[i:j] in S[j:]:
        a = max(a, len(S[i:j]))
        j += 1
    else:
        i += 1
    if i==j:
        i += 1
        j += 2

print(a)

Solution (Python):

import sys














def main():
    n, s = sys.stdin.read().split()
    n = int(n)

    res = 0
    l, r = 0, 1
    while r <= l + (n - l) // 2:
        t = s[l:r]
        if t in s[r:]:
            res = max(res, r - l)
            r += 1
        else:
            l += 1
            if l == r:
                r += 1
    print(res)

if __name__ == "__main__":
    main()

Solution (Python):

import sys














def main():
    n, s = sys.stdin.read().split()
    n = int(n)

    ans = 0
    i, j = 0, 1
    while j <= i + (n - i) // 2:
        if j <= i:
            j += 1
            continue
        t = s[i:j]
        if t in s[j:]:
            ans = max(ans, j - i)
            j += 1
        else:
            i += 1
    print(ans)
    
if __name__ == "__main__":
    main()

Solution (Python):

import sys














def main():
    n, s = sys.stdin.read().split()
    n = int(n)

    ans = 0
    i, j = 0, 1
    while j <= i + (n - i) // 2:
        t = s[i:j]
        if t in s[j:]:
            ans = max(ans, j - i)
            j += 1
        else:
            i += 1
    print(ans)
    
if __name__ == "__main__":
    main()

Solution (Python):

import sys














def main():
    n, s = sys.stdin.read().split()
    n = int(n)

    ans = 0
    i, j = 0, 1
    while j < n:
        t = s[i:j]
        if t in s[j:]:
            ans = max(ans, j - i)
            j += 1
        else:
            i += 1
    print(ans)
    
if __name__ == "__main__":
    main()

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

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

s = input()

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

for i in reversed(range(n)):
    for j in reversed(range(n)):
        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):
n=int(input())
s=input()

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

print(m)

Solution (Python):
n=int(input())
s=input()
ans=0
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

for i in range(n):
    l=z_algo(s[i:])
    m=len(l)
    for j in range(m):
        ans=max(ans,min(j,l[j]))
print(ans)

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

def z_advanced(s):
    
    """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
    return Z

best = 0
for i in range(N):
    lst = z_advanced(S[i:])
    for j, longest in enumerate(lst):
        best = max(best, min(j, longest))
print(best)

Solution (Python):
n = int(input())
s = input().rstrip()
 
 
def check(length):
    d = set()
    for i in range(n - 2 * length + 1):
        d.add(s[i:i + length])
        if s[i + length:i + 2 * length] in d:
            return True
    return False
 
 
lo = 0
hi = n // 2 + 1
while lo + 1 < hi:
    mid = (lo + hi) // 2
    if check(mid):
        lo = mid
    else:
        hi = mid
print(lo)

Solution (Python):
n = int(input())
s = input().rstrip()
 
 
def check(length):
    d = set()
    for i in range(n - 2 * length + 1):
        d.add(s[i:i + length])
        if s[i + length:i + 2 * length] in d:
            return True
    return False
 
 
lo = 0
hi = n // 2 + 1
while lo + 1 < hi:
    mid = (lo + hi) // 2
    if check(mid):
        lo = mid
    else:
        hi = mid
print(lo)

Solution (Python):
import sys
read = sys.stdin.buffer.read
input=lambda :sys.stdin.readline().rstrip()

INF=float("inf")
MOD=10**9+7

























def Z(s):
    n=len(s)
    z=[0]*n
    z[0]=n
    L,R=0,0
    for i in range(1,n):
        if(i>=R): 
            L=R=i
            while(R<n and s[R-L]==s[R]): R+=1
            z[i]=R-L
        elif(z[i-L]<R-i): 
            z[i]=z[i-L]
        else: 
            L=i
            while(R<n and s[R-L]==s[R]): R+=1
            z[i]=R-L
    return z





def main():
	n=int(input())
	s=input()
	ans=0
	for i in range(n-1):
		z=Z(s[i:])
		k=len(z)
		for j in range(k):
			ans=max(ans,min(j,z[j]))
	print(ans)
	
if __name__ == '__main__':
	main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
input=lambda :sys.stdin.readline().rstrip()

INF=float("inf")
MOD=10**9+7



























def main():
	n=int(input())
	s=input()
	
	ans=0
	cnt=0
	
	
	for d in range(1,n):
		cnt=0
		for i in range(n-d):
			if s[i]==s[i+d]:
				cnt+=1
				ans = max(ans, min(cnt, d))
			else:
				cnt=0
	print(ans)
	
	
	
	
	

if __name__ == '__main__':
	main()

Solution (Python):


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

if __name__ == '__main__':
    main()

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):
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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


def solve():
    dp = [[0]*(N+1) for _ in range(N+1)]
    for i, c in enumerate(S, 1):
        for j, k in enumerate(S, 1):
            if c == k:
                dp[i][j] = max(dp[i][j], dp[i-1][j-1]+1 if i +
                               dp[i-1][j-1] < j else 0)
    print(max([max(v) for v in dp]))


solve()

Solution (Python):

import sys

def z_algo(S):
    N = len(S)
    LCPs = [0]*N
    i = 1 
    j = 0
    LCPs[0] = N
    while i < N:
        while i+j < N and S[j] == S[i+j]:
            j += 1
        if j == 0:
            i += 1
            continue
        LCPs[i] = j
        k = 1
        while k+i < N and k+LCPs[k] < j:
            LCPs[i+k] = LCPs[k]
            k += 1
        i += k
        j -= k
    return LCPs

def solve(N: int, S: str):
    answer = 0
    for i in range(N):
        LCP = z_algo(S[i:])
        for j in range(len(LCP)):
            
            a = min(j,LCP[j])
            answer = max(answer,a)
    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    S = next(tokens)  
    solve(N, S)

if __name__ == '__main__':
    main()

Solution (Python):

import sys

def solve(N: int, S: str):

    a = ""
    ans = 0
    for i in range(N):
        a += S[i]
        while(len(a) > 0):
            if a in S[i+1:]:    
                ans = max(ans,len(a))
                break
            else:               
                a = a[1:]
    print(ans)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    S = next(tokens)  
    solve(N, S)

if __name__ == '__main__':
    main()

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


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

    dp = [0] * N
    for i, s in enumerate(S):
        if i == 0:
            continue
        before_ans = dp[i-1]
        now_S = S[:i+1]
        tmp_ans = now_S[-(before_ans+1):i+1]
        
        if tmp_ans in now_S[:-(before_ans+1)]:
            dp[i] = before_ans + 1
        else:
            dp[i] = before_ans
    print(dp[-1])


if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
S = input()
 
res = 0;
dp = [[0]*(N+1) for _ in range(N+1)]
 
for i in range(N-1, -1, -1):
  for j in range(N-1, i, -1):
    if S[i] == S[j]:
      dp[i][j] = max(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()

def z_algo(n,s):
    x=[0]*n
    j=0
    for i in range(1,n):
        if i+x[i-j]<j+x[j]:
            x[i]=x[i-j]
        else:
            k=max(0,j+x[j]-i)
            while i+k<n and s[k]==s[i+k]:
                k+=1
            x[i]=k
            j=i
    ans=0
    for i in range(n):
        if x[i]>i:
            continue
        else:
            ans=max(ans,x[i])
    return ans

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

print(ans if ans<=n//2 else n//2)

Solution (Python):
MOD = 10 ** 9 + 7

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):
        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
        hash1 = (self.__H1[r] - self.__P1[r - l] * self.__H1[l] % m1) % m1
        hash2 = (self.__H2[r] - self.__P2[r - l] * self.__H2[l] % m2) % m2
        return hash1, hash2

    @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

if __name__ == '__main__':
    
    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))

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

ans = 0
right = 1

for left in range(n):
    while s[left:right] in s[right:]:
        ans = max(ans,right-left)
        right += 1
        
print(ans)

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

ans = 0
right = 1

for left in range(n):
    while s[left:right] in s[right:]:
        ans = max(ans,right-left)
        right += 1
        
print(ans)