Problem:
 Score : 500 points    Problem Statement Given is a string S of length N .  Find the maximum length of a non-empty string that occurs twice or more in S as contiguous substrings without overlapping.  More formally, find the maximum positive integer len such that there exist integers l_1 and l_2 ( 1 \leq l_1, l_2 \leq N - len + 1 ) that satisfy the following:    l_1 + len \leq l_2    S[l_1+i] = S[l_2+i] (i = 0, 1, ..., len - 1)    If there is no such integer len , print 0 .      Constraints  2 \leq N \leq 5 \times 10^3  |S| = N  S consists of lowercase English letters.         Input Input is given from Standard Input in the following format:  N  S       Output Print the maximum length of a non-empty string that occurs twice or more in S as contiguous substrings without overlapping. If there is no such non-empty string, print 0 instead.        Sample Input 1 5
ababa      Sample Output 1 2  The strings satisfying the conditions are: a , b , ab , and ba . The maximum length among them is 2 , which is the answer.
Note that aba occurs twice in S as contiguous substrings, but there is no pair of integers l_1 and l_2 mentioned in the statement such that l_1 + len \leq l_2 .       Sample Input 2 2
xy      Sample Output 2 0  No non-empty string satisfies the conditions.       Sample Input 3 13
strangeorange      Sample Output 3 5

Solution (Python):
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)

from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque


def check(num, s, left, right):

    if right - left <= 1:
        print(left)
        sys.exit()

    half = (left + right) // 2

    data_set = set()

    for i in range(num -2 * half  + 1):
        now_str = s[i:i + half]
        data_set.add(now_str)
        if s[i + half : i + 2 * half] in data_set:
            check(num, s, half, right)
    check(num, s, left, half)

def main():
    num = int(input())
    s = input()

    left, right = 0, num // 2 + 1

    check(num, s, left, right)




if __name__ == '__main__':
    main()

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

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

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

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

r = 0
ans = 0

for l in range(N):

    while True:
        
        if S.rfind(S[l:r+1]) >= r+1:
            r += 1
            ans = max(ans, r-l)
        else:
            break

print(ans)

Solution (Python):
def longestRepeatedSubstring(str): 
  
    n = len(str) 
    LCSRe = [[0 for x in range(n + 1)]  
                for y in range(n + 1)] 
  
    res = "" 
    res_length = 0 
  
    
    index = 0
    for i in range(1, n + 1): 
        for j in range(i + 1, n + 1): 
              
            
            
            if (str[i - 1] == str[j - 1] and
                LCSRe[i - 1][j - 1] < (j - i)): 
                LCSRe[i][j] = LCSRe[i - 1][j - 1] + 1
  
                
                
                
                if (LCSRe[i][j] > res_length): 
                    res_length = LCSRe[i][j] 
                    index = max(i, index) 
                  
            else: 
                LCSRe[i][j] = 0
  
    
    
    
    if (res_length > 0): 
        for i in range(index - res_length + 1, 
                                    index + 1): 
            res = res + str[i - 1] 
  
    return res 
  

if __name__ == "__main__": 
  n=int(input())
  str=input()
  print(len(longestRepeatedSubstring(str)))

Solution (Python):
N=int(input())
S=input()
a=i=j=0
while j<N:
  t=S[i:j]
  if t in S[j:]:
    a=max(a,len(t))
    j+=1
  else:
    i+=1
print(a)

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


r = 0
ans = 0
for l in range(N):

    while True:
        
        
        if S.rfind(S[l:r+1]) >= r+1:
            r += 1
            ans = max(ans, r-l)
        else:
            break

print(ans)

Solution (Python):
n=int(input())
s=input()
m=0
for i in range(1,n):
    d,c=0,0
    for j in range(i,n):
        if s[j-i]==s[j]:c+=1
        else:
            d=max(c,d)
            c=0
    m=min(max(c,d,m),i)
print(m)

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

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

print(ans)

Solution (Python):
if __name__ == '__main__':
    N = int(input())
    S = input()
    dp = [0] * N
    j = 1
    for i in range(N):
        while S[i:j] in S[j:N]:
            dp[i] = j-i
            j += 1
    print(max(dp))

Solution (Python):
n,s=open(0);n=int(n);a=i=j=0
while j<n:
	t=s[i:j]
	if t in s[j:]:a=max(a,len(t));j+=1
	else:i+=1
print(a)

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

res = 0

for k in range(1,n):
    d = [0]*n
    for i in range(n-k):
        if i+k <= n-1 and s[i] == s[i+k]:
            d[i] = min(k,d[i-1]+1)
            res = max(res,d[i])
print(res)

Solution (Python):
n,s=open(0);n=int(n)
a=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
print(a)

Solution (Python):
n=int(input())
s=input()
l,r=n//2+1,0
while l-r>1:
    t=(l+r)//2
    g=s[:t]
    q={}
    q[s[t:2*t]]=1
    d=s[t:2*t]
    for i in range(2*t,n):
        d=d[1:]+s[i]
        if d in q:
            q[d]+=1
        else:
            q[d]=1
    if g in q:
        r=t
    else:
        d=s[t:2*t]
        for i in range(t,n-t):
            q[d]-=1
            if q[d]==0:
                del q[d]
            d=d[1:]+s[i+t]
            g=g[1:]+s[i]
            if g in q:
                r=t
                break
        else:
            l=t
print(r)

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

Solution (Python):
N = int(input())
S = input()
from collections import deque

def is_ok(l):
    hs = set()
    q = deque()
    for i in range(N-l+1):
        h = hash(S[i:i+l])
        if h in hs:
            return True
        q.append(h)
        if len(q) >= l:
            hs.add(q.popleft())
    return False

ok = 0
ng = N//2+1
while ng-ok > 1:
    m = (ng+ok)//2
    if is_ok(m):
        ok = m
    else:
        ng = m
print(ok)

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


r = 0
ans = 0
for l in range(N):

    while True:
        
        
        if S.rfind(S[l:r+1]) >= r+1:
            r += 1
            ans = max(ans, r-l)
        else:
            break

print(ans)

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

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


LEN=len(S)

p=26
mod=(1<<50)+1

TABLE=[0]

for i in range(LEN):
    TABLE.append((p*TABLE[-1]%mod+ord(S[i])-97)%mod)

def hash_ij(i,j): 
    return (TABLE[j]-TABLE[i]*pow(p,j-i,mod))%mod


MIN=0
MAX=LEN//2

from collections import defaultdict

while MIN!=MAX:
    x=(MIN+MAX+1)//2
    DICT=defaultdict(list)

    for i in range(LEN-x+1):
        DICT[hash_ij(i,i+x)].append(i)

    

    for l in DICT:
        if max(DICT[l])-min(DICT[l])>=x:
            MIN=x
            break
    else:
        MAX=x-1

print(MIN)

Solution (Python):
n,s=open(0);n=int(n)
a=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):
N = int(input())
S = input()
ans = 0
right = 0
for left in range(N):
    while S[left:right + 1] in S[right + 1:]:
        ans = max(ans, right + 1 - left)
        right += 1
print(ans)

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

Solution (Python):
def main():
    n=int(input())
    s=input()
    m=0
    for i in range(1,n):
        cnt_m=0
        cnt=0
        for j in range(i,n):
            if s[j-i]==s[j]:
                cnt=min(cnt+1,i)
            else:
                cnt_m=max(cnt,cnt_m)
                cnt=0
        m=max(cnt,cnt_m,m)
    print(m)

if __name__ == '__main__':
    main()

Solution (Python):
import sys,collections as cl,bisect as bs , heapq as hq
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k][0] ==  x:
        return True
    else:
        return False

def search(a,n):
    se = dict()
    for i in range(0,len(a)-n+1):
        kkk = a[i:i+n]
        kkk = "".join(kkk)
        if kkk in se:
            if se[kkk] <= i-n:
                    return True
        else:
            se[kkk] = i
    return False


n = onem()

s = list(input())
l = 0
r = n//2
while True:
    mid = -(-(l+r)//2)
    ans = search(s,mid)
    if l == mid:
        break
    if ans:
        l = mid
    else:
        r = mid-1
print(l)

Solution (Python):
"""
N = int(input())
A, B = map(int,input().split())
A = list(map(int,input().split())) 
A = [int(input()) for _ in range(N)] 
lst = [list(map(int,input().split())) for i in range(M)] 
"""

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




ans = 0
for circ in range(1, N):
  cnt = 0
  solver = [0]
  for i in range(N-circ):
    if S[i] == S[i+circ]:
      cnt += 1
    else:
      solver.append(cnt)
      cnt = 0
  else:
    solver.append(cnt)
  ans = max(ans, min(circ, max(solver)))

print(ans)




"""
ans = 0
for i in range(N-1):
  if i+1+ans >= N:
    break
  lst = [0]
  for j in range(i+1+ans,N):
    cnt = 0
    if S[i] == S[j]:
      cnt += 1
      for k in range(1,min(j-i, N-j)):
        if S[i+k] == S[j+k]:
          cnt += 1
        else:
          break
    lst.append(cnt)
    
  ans = max(ans, max(lst))
  
print(ans)
"""

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


r = 1
ans = 0
for l in range(N):

    while True:
        

        if S.rfind(S[l:r+1]) >= r+1:
            r += 1
            ans = max(ans, r-l)
        else:
            break

print(ans)

Solution (Python):
import sys

def main():
    _,S = open(0).read().split()
    s1 = S[:int(len(S)*3/4)+1]

    maxLen = 0
    lenS1 = len(s1)
    for i in range(lenS1):
        for j in range(i+1+maxLen,lenS1):
            
            if len(s1[i:j]) > len(S[j:]):
                break
            if s1[i:j] in S[j:]:
                maxLen = j-i
            else:
                break

    print(maxLen)

if __name__ == '__main__':
    main()

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


r = 1
ans = 0
for l in range(N):

    while True:
        

        if S.rfind(S[l:r+1]) >= r+1:
            r += 1
            ans = max(ans, r-l)
        else:
            break

print(ans)

Solution (Python):

import re
import sys


def solve(N: int, S: str):
    max_length = 1
    found = False
    for i in range(N):
        is_break = False
        if i + max_length > N:
            break
        while not is_break:
            org = S[i:i + max_length]
            rest = S[i + max_length:N]
            
            if org in rest:
                max_length += 1
            else:
                is_break = True
    print(max_length - 1)
    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):
N = int(input())
S = input()
ans = 0
for i in range(1, N):
    cnt = 0
    for j in range(N-i):
        if S[j] == S[i+j]:
            cnt += 1
            if cnt == i:
                ans = max(ans, i)
                break
        else:
            ans = max(ans, cnt)
            cnt = 0
    ans = max(ans, cnt)
print(ans)

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

Solution (Python):
import sys,collections as cl,bisect as bs,heapq as hq
input = sys.stdin.readline
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def jo(x): 
    return " ".join(map(str,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def search(a,n):
    se = dict()
    data = []
    for i in range(0,len(a)-n+1):
        kkk = a[i:i+n]
        kkk = "".join(kkk)
        if In(kkk,data):
            if se[kkk] <= i-n:
                    return True
        else:
            bs.insort(data,kkk)
            se[kkk] = i
    return False
def solver():
    n = onem()

    s = list(input())
    l = 0
    r = n//2
    for i in range(n):
        mid = -(-(l+r)//2)
        ans = search(s,mid)
        if l == mid:
            break
        if ans:
            l = mid
        else:
            r = mid-1
    print(l)



if __name__ == '__main__':
    solver()

Solution (Python):
n=int(input())
s=input()
ans=0
tmp=0
for i in range(n-1):
  for j in range(i+2,n+1):
    if j-i>ans:
      if s[i:j] in s[j:]:
        tmp=j-i
      else:
        ans=max(tmp,ans)
        break
ans=max(tmp,ans)
print(ans)

Solution (Python):

import re
import sys


def solve(N: int, S: str):
    max_length = 1
    found = False
    for i in range(N):
        is_break = False
        if i + max_length > N:
            break
        while not is_break:
            org = S[i:i + max_length]
            rest = S[i + max_length:N]
            
            if org in rest:
                max_length += 1
            else:
                is_break = True
    print(max_length - 1)
    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):
N = int(input())
S = input()

ans = 0
for i,s in enumerate(S):
    T = S[i:]
    d = [0]*(N-i)
    d[0] = -1
    k,j = 0,1
    while j< (N-i-1):
        matched = T[k] == T[j]
        if not matched and k>0:
            k = d[k]
        else:
            if matched:
                k += 1
            j += 1
            d[j] = k
    j,p = 1,0
    while j< (N-i) and p< (N-i):
        if (T[j] == T[p]) and (p*2 < j):
            j += 1
            p += 1
            ans = max(ans,p)
        elif p == 0:
            j += 1
        else:
            p = d[p]
print(ans)

Solution (Python):
n=int(input())
s=list(input())
f=0
b=-1
for d in range(1,n):
  c=0
  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)
    else:
      c=0
      b=-1
print(f)

Solution (Python):
N = int(input())
S = input()
from collections import deque

def is_ok(l):
    hs = set()
    q = deque()
    for i in range(N-l+1):
        h = hash(S[i:i+l])
        if h in hs:
            return True
        q.append(h)
        if len(q) >= l:
            hs.add(q.popleft())
    return False

ok = 0
ng = N//2+1
while ng-ok > 1:
    m = (ng+ok)//2
    if is_ok(m):
        ok = m
    else:
        ng = m
print(ok)

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

ans = 0
index = 0
length = 1
while index < N-ans*2:
    while S[index:index+length] in S[index+length:]:
        length += 1
    if ans < length-1:
        ans = length-1
    index += 1
print(ans)

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

check_list = [ [ 0 for i in range(n) ] for i in range(n) ]


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

print(ans)

Solution (Python):
import sys,collections as cl,bisect as bs,heapq as hq
input = sys.stdin.readline
sys.setrecursionlimit(100000)
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def jo(x): 
    return " ".join(map(str,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def search(a,n):
    se = dict()
    data = []
    for i in range(0,len(a)-n+1):
        kkk = a[i:i+n]
        kkk = "".join(kkk)
        if In(kkk,data):
            if se[kkk] <= i-n:
                    return True
        else:
            bs.insort(data,kkk)
            se[kkk] = i
    return False
def solver():
    n = onem()

    s = list(input())
    l = 0
    r = n//2
    for i in range(n):
        mid = -(-(l+r)//2)
        ans = search(s,mid)
        if l == mid:
            break
        if ans:
            l = mid
        else:
            r = mid-1
    print(l)



if __name__ == '__main__':
    solver()

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

Solution (Python):
n=int(input())
s=list(input())
f=0
b=-1
for d in range(1,n):
    c=0
    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)
        else:
            c=0
            b=-1
print(f)

Solution (Python):
import numpy as np
import math
import sys
sys.setrecursionlimit(10000000)

def is_match(string, pattern):
    if pattern in string:
        return True
    else:
        return False

def main():
    N = int(input())
    S = input()
    dp = [0] * N
    for i in range(1, N):
        length = dp[i - 1] + 1
        match_string = S[i - length + 1: i + 1]
        matched_string = S[:i+1-length]
        if is_match(matched_string, match_string):
            dp[i] = dp[i - 1] + 1
        else:
            dp[i] = dp[i - 1]
    print(dp[-1])
    
if __name__ == '__main__':
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
debug = True

debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()

INF = 10 ** 18
MOD = 10 ** 9 + 7

def main():
    N = II()
    S = SI()

    
    ans = -1

    from collections import defaultdict
    posd = defaultdict(list)

    for i, c in enumerate(S):
        posd[c].append(i)

    for i in range(N):
        si = S[i]

        
        pos_list = posd[si]

        for pos in pos_list:
            if pos >= i:
                
                continue

            
            if pos > 0 and S[pos - 1] == S[i - 1]:
                continue

            
            for j in range(N):
                
                
                if pos+j == i:
                    break
                
                if i+j == N:
                    break

                you = pos + j
                me = i + j

                
                if S[you] != S[me]:
                    break

                
                ans = max(ans, j)
                

    
    
    print(ans + 1)

main()

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

from collections import defaultdict
N = int(input())
S = input()
ans = 0
for i in range(N):
    s = S[i:]
    z = Z(s)
    for j in range(len(z)):
        z[j] = min(j,z[j])
    ans = max(ans,max(z))

print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
debug = True

debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()

INF = 10 ** 18
MOD = 10 ** 9 + 7

def main():
    N = II()
    S = SI()

    mark = [-1 for i in range(N)]

    from collections import defaultdict
    posd = defaultdict(list)

    for i, c in enumerate(S):
        posd[c].append(i)

    for i in range(N):
        si = S[i]

        
        pos_list = posd[si]

        for pos in pos_list:
            if pos >= i:
                
                continue

            
            if pos > 0 and S[pos - 1] == S[i - 1]:
                continue

            
            for j in range(N):
                
                
                if pos+j == i:
                    break
                
                if i+j == N:
                    break

                you = pos + j
                me = i + j

                
                if S[you] != S[me]:
                    break

                
                mark[you] = max(mark[you], j)

    dprint(mark)
    print(max(mark)+1)



main()

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

ans = 0

while ans <= len(s)//2:
    prev_s = ''
    for i in range(ans+1, len(s)//2+1):
        if s[:i] in s[i:]:
            prev_s = s[:i]
        else:
            ans = max(ans, len(prev_s))
            break
    else:
        ans = max(ans, len(prev_s))
    s = s[1:]
    if len(s) == 1:
        break

print(ans)

Solution (Python):
N = int(input())
S = [ord(s) for s in input()]



c = 0
for i in range(1, N):
    d = 0
    for s_j, t_j in zip(S, S[i:]):
        if s_j == t_j:
            d += 1
        else:
            c = max(c, min(d, i))
            d = 0
    c = max(c, min(d, i))


print(c)

Solution (Python):
def main():

    N = int(input())
    S = input()
    dp = [[0 for _ in range(N+1)] for _ in range(N+1)]
    ans = 0

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

if __name__ == '__main__':
    print(main())

Solution (Python):


n=int(input())
s=list(input())
a=list(map(ord,s))
m=0
for i in range(1,n):
    cnt=0
    flg=0
    tmp=0
    for j in range(n-i):
        if a[j]==a[j+i] and flg==0:
            
            flg=1
            tmp=j+i
            cnt+=1
        elif a[j]==a[j+i] and flg==1:
            
            cnt+=1
            if tmp>j:
                m=max(m,cnt)
        else:
            
            cnt=0
            flg=0
print(m)

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

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

ans = 0

for i in range(n):
    a = Z(s[i:])
    b = [a[j] if j - a[j] >= 0 else 0 for j in range(len(s[i:]))]
    ans = max(ans,max(b))

print(ans)


'''
    if len(a) > 1:
        ind = a.index(max(a[1:]))
        if a[ind-1] > 0:
            ans = max(ans,a[ind-1] // 2)
        elif a[ind] - ind - 1 < 0:
            continue
        else:
            ans = max(ans,a[ind])
'''

Solution (Python):
n = int(input())
s = input()
dp = [[0]*n for i in range(n)]
for i in range(n):
    dp[0][i] = 1 if s[0] == s[i] else 0
ans = 0
for i in range(1,n):
    for j in range(i,n):
        if s[i] == s[j]:
            if dp[i-1][j-1] > 0:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = 1
for i in range(n):
    for j in range(i + 1,n):
        if ans < dp[i][j] and i + dp[i][j] <= j:
            ans = dp[i][j]
print(ans)

Solution (Python):
n = int(input())
s = input()
_max = 0
for i in range(n):
    for j in range(i+1, n):
        if _max >= j-i:
            continue
        part = s[i:j]
        if part in s[j:]:
            _max = j-i
        else:
            break
print(_max)

Solution (Python):
import sys
input = sys.stdin.readline
def main():
    N = int( input())
    S = input()
    dp = [[0]*(N+1) for _ in range(N+1)]
    for i in range(N-1):
        for j in range(i+1, N):
            if S[i] == S[j]:
                dp[i+1][j+1] = min(dp[i][j] + 1, j-i)
    print( max( [ max(dp[i]) for i in range(N+1)]))
if __name__ == '__main__':
    main()

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

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

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

print(ans)

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

Solution (Python):
N = int(input())
S = input()
dp = [0]*N
j = 1

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

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

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)

Solution (Python):
inpl = lambda: list(map(int,input().split()))
N = int(input())
S = input()

character_pos = [ set() for _ in range(26) ]
for i in range(N):
    character_pos[ord(S[i])-ord('a')].add(i)

ans = 0
continue_list = dict()
for i in range(N):
    s = S[i]
    new_continue_list = dict()
    for p in character_pos[ord(s)-ord('a')]:
        if p < i:
            new_continue_list[p] = 1
    for k, v in continue_list.items():
        if s == S[k+1]  and v + 1 <= i - k - 1:
            new_continue_list[k+1] = v+1
        elif v > ans:
            ans = v
    continue_list = new_continue_list

if len(continue_list.values()) > 0:
    ans = max(ans, max(continue_list.values()))
print(ans)

Solution (Python):
import numpy as np
import math
import sys
sys.setrecursionlimit(10000000)

def max(a, b):
    return a if a > b else b
 
def is_match(string, pattern):
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    if pattern in string:
        return True
    else:
        return False


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

    dp = [0] * N

    for i in range(1, N):
        length = dp[i - 1] + 1
        match_string = S[i - length + 1: i + 1]
        matched_string = S[:i+1-length]
        
        if is_match(matched_string, match_string):
            dp[i] = dp[i - 1] + 1
        else:
            dp[i] = dp[i - 1]
        
    
    
    print(dp[-1])



if __name__ == '__main__':
    main()

Solution (Python):
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
ts=time.time()
sys.setrecursionlimit(10**6)

show_flg=False


ans=0
an=[]
n=I()
st=-1
s=list(input())
can=[]
for d in range(1,n):
    cnt=0
    for i in range(n-d):
        if s[i]==s[i+d] and st+cnt+1<=st+d:
            if st==-1:
                st=i
            
            cnt+=1
            
            ans=max(ans,cnt)
        else:
            
            cnt=0
            
            
            st=-1
    cnt=0
print(ans)

Solution (Python):
n = int(input())
s = '^' + input().strip() + '$'

dp = [[0 for _ in range(n + 2)] for _ in range(n + 2)]
longest = 0
for i in range(1, n + 2):
    for j in range(i + 1, n + 2):
        if s[i] == s[j]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            val = dp[i - 1][j - 1]
            if j - i < val:
                val = j - i
            if val > longest:
                longest = val

print(longest)

Solution (Python):
n=int(input())
s=input()
l,r=n//2+1,0
while l-r>1:
    t=(l+r)//2
    g=s[:t]
    q={}
    q[s[t:2*t]]=1
    d=s[t:2*t]
    for i in range(2*t,n):
        d=d[1:]+s[i]
        if d in q:
            q[d]+=1
        else:
            q[d]=1
    if g in q:
        r=t
    else:
        d=s[t:2*t]
        for i in range(t,n-t):
            q[d]-=1
            if q[d]==0:
                del q[d]
            d=d[1:]+s[i+t]
            g=g[1:]+s[i]
            if g in q:
                r=t
                break
        else:
            l=t
print(r)

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




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

mx = 0

for i in range(N):

  for k in range(N):
    if i<k and S[i] == S[k]:
      dp[i+1][k+1] = 1
    c_before = dp[i][k]
    if k<N and i+c_before<k and S[k]==S[i]:
      dp[i+1][k+1] = c_before+1
      mx = max(mx,c_before+1)


print(mx)