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()
i = 0
j = 0
r = 0
while i < n:
    if s[i:j] in s[j:]:
        r = max(r, j - i)
        j += 1
    else:
        i += 1
print(r)

Solution (Python):
def Zalgorithm(s):
    z = [0 for _ in range(len(s))]
    z[0] = len(s)
    i, j = 1, 0
    while i < len(s):
        while i+j < len(s) and s[j] == s[i+j]:
            j += 1
        z[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < len(s) and k+z[k] < j:
            z[i+k] = z[k]
            k += 1
        i += k
        j -= k
    return z

n = int(input())
s = input().strip()
ans = 0
for i in range(len(s)):
    zarr = Zalgorithm(s[i:])
    for j in range(len(zarr)):
        ans = max(ans, min(j, zarr[j]))
print(ans)

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

    l, r, ans = 0, 0, 0

    while r < N:
        if S[l:r] in S[r:N]:
            ans = max(ans, r - l)
            r += 1
        else:
            l += 1

    print(ans)


if __name__ == '__main__':
    p_e()

Solution (Python):
n = int(input())
s = input()
D = [[0] * n for i in range(n)]
 
for i in range(n):
    D[0][i] = int(s[0]==s[i])
    D[i][0] = int(s[0]==s[i])
D[0][0] = 0

for i in range(1,n):
    for j in range(i+1,n):
        mae = D[i-1][j-1]
        if s[i] == s[j]:
            if j-i <= mae:
                D[i][j] = mae
            else:
                D[i][j] = mae + 1

print(max([max(D[i]) for i in range(n)]))

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    def Z(s):
        """
        param s:str
        return list of int with length len(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
                R-=1 
            elif z[i-L]<R-i+1:
                z[i]=z[i-L]
            else:
                L=i
                R+=1 
                while(R<n and s[R-L]==s[R]): R+=1
                z[i]=R-L
                R-=1
        return z

    
    n=int(input())
    s=input()
    ans=0
    for i in range(n):
        z=Z(s[i:])
        k=len(z) 
        for j in range(k):
            ans=max(ans,min(j,z[j]))
    print(ans)
resolve()

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

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

for i in range(N-1, -1, -1):
    for j in range(N-1, -1, -1):
        if S[i] == S[j]:
            dp[i][j] = dp[i+1][j+1] + 1

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):
def solve(n, s):
    l, r = 0, n // 2 + 1
    while l < r:
        m = (l + r + 1) // 2
        if search(m, s):
            l = m
        else:
            r = m - 1
    return l


def search(w, s):
    w2 = w * 2
    appeared = [hash(s[i - w:i]) for i in range(w, w2)]
    comparing = set()

    for i in range(w2, n + 1):
        t = hash(s[i - w:i])
        comparing.add(appeared[i - w2])
        if t in comparing:
            return True
        appeared.append(t)

    return False


n = int(input())
s = input()
print(solve(n, s))

Solution (Python):
def solve(n, s):
    l, r = 0, n // 2 + 1
    while l < r:
        m = (l + r + 1) // 2
        if search(m, s):
            l = m
        else:
            r = m - 1
    return l


def search(w, s):
    appeared = []
    comparing = set()
    w2 = w * 2

    for i in range(w, n + 1):
        t = hash(s[i - w:i])
        if i >= w2:
            comparing.add(appeared[i - w2])
            if t in comparing:
                return True
        appeared.append(t)

    return False


n = int(input())
s = input()
print(solve(n, s))

Solution (Python):
def solve(n, s, d, MOD):
    ttt = [ord(c) - 97 for c in s]

    ttx = []
    c = 1
    for t in ttt[::-1]:
        ttx.append(t * c % MOD)
        c = c * d % MOD
    ttx.reverse()
    ttc = [0]
    for t in ttx:
        ttc.append((ttc[-1] + t) % MOD)

    l, r = 0, n // 2 + 1
    while l < r:
        m = (l + r + 1) // 2
        if search(m, d, ttc, MOD):
            l = m
        else:
            r = m - 1

    return l


def search(w, d, ttc, MOD):
    appeared = []
    comparing = set()
    w2 = w * 2
    p = 1

    for i in range(w, n + 1):
        t = (ttc[i] - ttc[i - w]) * p % MOD
        if i >= w2:
            comparing.add(appeared[i - w2])
            if t in comparing:
                return True
        appeared.append(t)
        p = p * d % MOD

    return False


n = int(input())
s = input()
MOD = 10 ** 9 + 7
print(min(solve(n, s, d, MOD) for d in (29, 31)))

Solution (Python):
def solve(n, s, d, MOD):
    ttt = [ord(c) - 97 for c in s]

    ttx = []
    c = 1
    for t in ttt[::-1]:
        ttx.append(t * c % MOD)
        c = c * d % MOD
    ttx.reverse()
    ttc = [0]
    for t in ttx:
        ttc.append((ttc[-1] + t) % MOD)

    l, r = 0, n
    while l < r:
        m = (l + r + 1) // 2
        if search(m, d, ttc, MOD):
            l = m
        else:
            r = m - 1

    return l


def search(w, d, ttc, MOD):
    appeared = []
    comparing = set()
    w2 = w * 2
    p = 1

    for i in range(w, n + 1):
        t = (ttc[i] - ttc[i - w]) * p % MOD
        if i >= w2:
            comparing.add(appeared[i - w2])
            if t in comparing:
                return True
        appeared.append(t)
        p = p * d % MOD

    return False


n = int(input())
s = input()
MOD = 10 ** 9 + 7
print(min(solve(n, s, d, MOD) for d in (26, 29, 31)))

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]:
        j += 1
    dp[i] = j-i-1
print(max(dp))

Solution (Python):
N = int(input())
S = input()
St = []
for i in range(N):
  St += [ord(S[i])-97]
  
St.reverse()
ans = 0

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


for i in range(N):
  for j in range(i):
    if (St[i] == St[j]): 
      dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1)
      ans = max(ans, min(dp[i+1][j+1], i-j))
    if i-j <= dp[i+1][j+1]:
      break
      
print(ans)

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

  if i == j:
    i += 1
    j += 2
print(ans)

Solution (Python):
n = int(input())
s = input().strip()
assert n == len(s)

maxlen = 0
for offset in range(1, n):
  t = s[offset:]
  d = 0
  for (a, b) in zip(s, t):
    if a == b:
      d += 1
    else:
      d = 0
    if maxlen < d and d <= offset:  
      maxlen = d

print(maxlen)

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

Solution (Python):
n=int(input())
s=input()
l=0
r=n//2
while r-l>=1:
    m=(r+l+1)//2
    d={}
    flg=False
    for i in range(n-m+1):
        t=s[i:i+m]
        if t in d:
            if d[t]+m-1<i:
                flg=True
                break
        else:
            d[t]=i
    if flg:
        l=m
    else:
        r=m-1
print(l)

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

ans = 0
lenS = 1
for i in range(n):
	tempS = s[i:i+lenS]
	while (tempS in s[i+lenS:]):
		lenS += 1
		tempS = s[i:i+lenS]
		ans += 1
	if (i + 2*lenS>= n):
		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 = 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()



def LCP(S, N):
    A = [N] + [0] * (N - 1)
    max_length = 0
    i, j = 1, 0
    while i < N:
        while i + j < N and S[j] == S[i + j]:
            j += 1
        A[i] = j
        max_length = min(max(max_length, j), i)
        if j == 0:
            i += 1
            continue
        else:
            k = 1
            while i + k < N and k + A[k] < j:
                A[i + k] = A[k]
                max_length = min(max(max_length, A[k]), i + k)
                k += 1
            i += k
            j -= k
    return max_length

ans = 0
for i in range(N):
    cand = LCP(S[i:], N - i)
    ans = max(ans, cand)

print(ans)

Solution (Python):
n,s=open(0);a=i=j=0
while s[j:]:f=s[i:j]in s[j:];a=max(a,j*f-i);j+=f;i+=f^1
print(a)

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

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

for i in range(N - 1, -1, -1):
    for j in range(N - 1, -1, -1):
        if S[i] != S[j]:
            dp[i][j] = 0
        else:
            dp[i][j] = dp[i + 1][j + 1] + 1

max_length = 0
for i in range(N):
    for j in range(N):
        if i < j:
            length = min(j - i, dp[i][j])
            max_length = max(length, max_length)

print(max_length)

Solution (Python):
import math
import collections
import itertools
import sys
import bisect
from heapq import heappop,heappush
sys.setrecursionlimit(10**6)
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

n = INT()
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):
n,s=open(0);a=i=j=0
while j<int(n):f=s[i:j]in s[j:];a=max(a,j*f-i);j+=f;i+=f^1
print(a)

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

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

for i in range(N - 1, -1, -1):
    for j in range(N - 1, -1, -1):
        if i >= j: break
        if S[i] == S[j]:
            dp[i][j] = min(1 + dp[i + 1][j + 1], j - i)
            if dp[i][j] > ans:
                ans = dp[i][j]
print(ans)

Solution (Python):
n,s=open(0);a=i=j=0
while j<int(n):f=s[i:j]in s[j:];a=max(a,(j-i)*f);j+=f;i+=f^1
print(a)

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

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

Solution (Python):
def z_algorithm(s):
    N = len(s)
    A = [0]*N
    A[0] = N
    i,j = 1,0
    while i < N:
        while i+j < N and s[j] == s[i+j]:
            j += 1
        if j == 0:
            i += 1
            continue
        A[i] = j
        k = 1
        while i+k < N and k+A[k] < j:
            A[i+k] = A[k]
            k += 1
        i += k
        j -= k
    return A

N = int(raw_input())
S = raw_input()

ans = 0
for i in range(N):
    s = S[i:]
    lcp = z_algorithm(s)
    for j,p in enumerate(lcp):
        t = min(j, p)
        ans = max(ans, t)

print ans

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

dp = [[0] * N for i in range(N)]
max_leng2 = 0 
for i in range(0, N):
    leng2 = 0

    j = i - 1
    while j > -1:
        if S[i] == S[j]:
            sta_j = j
            if j != 0:
                leng2 = dp[i-1][sta_j-1] + 1
            else: 
                leng2 = 1
            
            if i - sta_j < leng2:
                leng2 = i - sta_j
                
            dp[i][sta_j] = leng2
            max_leng2 = max(max_leng2, leng2)
        j -= 1
print(max_leng2)

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

ans = 0
lenS = 1
for i in range(n):
	tempS = s[i:i+lenS]
	while (tempS in s[i+lenS:]):
		lenS += 1
		tempS = s[i:i+lenS]
		ans += 1

print(ans)

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

ans = 0
left, right = 0, 1
while right < N:
    s = S[left:right]
    if s in S[right:]:
        right += 1
        ans = max(ans, len(s))
    else:
        left += 1

print(ans)

Solution (Python):
n,s=open(0)
n=int(n)
a=0
for i in range(n):
  t=0
  for v,w in zip(s,s[i:n]):
    t=-~t*(v==w)
    a=max(a,min(t,i))
print(a)

Solution (Python):





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

r,i,j = 0,0,0
while j < N:
  t = S[i:j]
  if t in S[j:]:
    r = max(r,j-i)
    j += 1
  else:
    i += 1
print(r)

Solution (Python):
def main():
  n=int(input())
  s=t=input()
  a=0
  for i in range(n):
    c=0
    for v,w in zip(s,t):
      if v==w:c+=1
      else:c=0
      if c>i:break
      if c>a:a=c
    t=t[1:]
  print(a)
main()

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

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

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

print(ans)

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




def longestRepeatedSubstring(s): 
  n = len(s) 
  LCSRe = [[0 for _ in range(n + 1)] for _ 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 s[i - 1] == s[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 + s[i - 1] 
  return res_length
print(longestRepeatedSubstring(S))

Solution (Python):
def main():
  n=int(input())
  s=t=input()
  a=0
  for i in range(n):
    c=0
    for v,w in zip(s,t):
      if v==w:c+=1
      else:c=0
      if c>i:break
      if c>a:a=c
    t=t[1:]
  print(a)
main()

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

ans = 0
left, right = 0, 1
while right < N:
    s = S[left:right]
    if s in S[right:]:
        ans = max(ans, len(s))
        right += 1
    else:
        left += 1

print(ans)

Solution (Python):
def z_algorithm(s):
    n = len(s)
    prefix = [0] * n
    j = 0
    ret = 0
    for i in range(1, n):
        if i + prefix[i - j] < j + prefix[j]:
            prefix[i] = prefix[i - j]
        else:
            k = max(0, j + prefix[j] - i)
            while i + k < n and s[k] == s[i + k]:
                k += 1
            prefix[i] = k
            ret = max(ret, min(i, k))
            j = i
    return ret


n = int(input())
s = input()
print(max(z_algorithm(s[i:]) for i in range(n - 1)))

Solution (Python):
from subprocess import*
with open('e.cpp','w')as f:f.write(r"""

using namespace std;
main(){
  int n;
  string s;
  cin>>n>>s;
  int a=0;
  for(int i=0;i<n;++i){
    int t=0;
    for(int j=0;j<n-i;++j){
      t=(t+1)*(s[j]==s[j+i]);
      a=max(a,min(t,i));
    }
  }
  cout<<a;
}""")
call(('g++','e.cpp'))
call('./a.out')

Solution (Python):
from subprocess import*
with open('e.cpp','w')as f:f.write(r"""

using namespace std;
main(){
  int n;
  string s;
  cin>>n>>s;
  int a=0;
  for(int i=0;i<n;++i){
    int t=0;
    for(int j=0;j<n-i;++j){
      t=(t+1)*(s[j]==s[j+i]);
      a=max(a,min(t,i));
    }
  }
  cout<<a;
}""")
call(('g++','e.cpp'))
call('./a.out')

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

ok, ng = 0, n//2+1
while ng-ok > 1:
	x = (ok+ng)//2
	possible = False
	d = set()
	for i in range(n-2*x+1):
		d.add(hash(s[i:i+x]))
		if hash(s[i+x:i+2*x]) in d:
			possible = True
			break
	if possible:
		ok = x
	else:
		ng = x
print(ok)

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

def resolve():
    n=int(input())
    s=input()
    dp=[[0]*(n+1) for _ in range(n+1)]
    from itertools import product
    for i,j in product(reversed(range(n)),repeat=2):
        if i>=j: continue 
        if s[i]==s[j]:
            dp[i][j]=dp[i+1][j+1]+1
        else:
            dp[i][j]=0
    ans=0
    for i,j in product(reversed(range(n)),repeat=2):
        if i>=j: continue
        ans=max(ans,min(j-i,dp[i][j]))
    print(ans)


resolve()

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

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

dp[-1] = [1 if s == S[-1] else 0 for s in S]
for i in range(N-2, -1, -1):
    dp[i][-1] = 1 if S[i] == S[-1] else 0
    for j in range(N-2, -1, -1):
        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(i+1, N):
        if dp[i][j] > 0:
            ans = max(ans, min(dp[i][j], j-i))

print(ans)

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

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

OK = 0
NG = N // 2 + 1

while abs(OK - NG) > 1:
    mid = (OK + NG) // 2
    if check(mid):
        OK = mid
    else:
        NG = mid

print(OK)

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

F = [1] * (N//2 + 2)
for i in range(1, len(F)):
    F[i] = F[i] * 26

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

OK = 0
NG = N // 2 + 1

while abs(OK - NG) > 1:
    mid = (OK + NG) // 2
    if check(mid):
        OK = mid
    else:
        NG = mid

print(OK)

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

F = [1] * (N//2 + 2)
for i in range(1, len(F)):
    F[i] = F[i] * 26

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

OK = 0
NG = N // 2 + 1

while abs(OK - NG) > 1:
    mid = (OK + NG) // 2
    if check(mid):
        OK = mid
    else:
        NG = mid

print(OK)

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

Solution (Python):
N = int(input())
S = input()
def check(l):
  D = {}
  for i in range(N-l+1):
    s = S[i:i+l]
    if s not in D:
      D[s] = i
      continue
    if D[s]+l <= i:
      return True
  return False
a = 1
b = N
while a < b:
  i = (a + b)//2
  if not check(i):
    b = i
  else:
    if a == i:
      break
    a = i
r = b-1
print(r)

Solution (Python):
N = int(input())
S = str(input())
dp = [[0 for i in range(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):
    for j in range(N):
        if j > i:
            tmp = min(j-i,dp[i][j])
            ans = max(tmp,ans)
print(ans)

Solution (Python):
import sys
import heapq
import bisect

mod = 10**9+7
dd = ((-1,0),(1,0),(0,-1),(0,1))

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def S(): return(list(sys.stdin.readline())[:-1])

def main():
    N = I()
    s = S()
    dp = [[0 for _ in range(N)] for _ in range(N)]

    for i in range(N-1,-1,-1):
        for j in range(N-1,-1,-1):
            if s[i] == s[j]:
                if i+1<=N-1 and j+1<=N-1:
                    dp[i][j] = dp[i+1][j+1]+1
                else:
                    dp[i][j] = 1

    ans = 0
    for i in range(N):
        for j in range(N):
            if dp[i][j] > ans and i + dp[i][j] <= j:
                ans = dp[i][j]
    return(ans)

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

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

l = 0
r = 1
ans = 0


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

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

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

def main():
    N = int(input())
    S = input()
    
    
    import time
    star = time.time()
    A = [[] for i in range(N)]
    for i in range(N):
        A[i] = [0]*i + z_algo(S[i:])
    ans = 0
    for i in range(N):
        for j in range(N):
            if i + A[i][j] <= j and ans < A[i][j]:
                ans = A[i][j]
    
    g = time.time()
    
    print(ans)
    
main()

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

Solution (Python):
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()

n = ni()
s = input()
dp = [[0] * 5005 for _ in range(5005)]
for i in range(n)[::-1]:
    for j in range(n)[::-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):
N = int(input())
S = input()

r=0
i=j=0
while j < N:
    t = S[i:j]
    if t in S[j:]:
        r = max(r, j-i)
        j += 1
    else:
        i += 1
print(r)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

N = int(input())
S = np.array([ord(x) for x in input().rstrip()],dtype=np.int64)

MOD = 10**9 + 7
base = 1234

def cumprod(arr):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr,Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    return arr.ravel()[:L]

x = np.full(N,base,np.int64); x[0] = 1
power = cumprod(x)
x = np.full(N,pow(base,MOD-2,MOD),np.int64); x[0] = 1
power_inv = cumprod(x)


H = S * power % MOD
Hcum = H.cumsum() % MOD

def test(n):
    
    x = (Hcum[n-1:N] - Hcum[:N-n+1] + H[:N-n+1]) % MOD
    x *= power_inv[:N-n+1]
    x %= MOD
    
    ind = np.lexsort((np.arange(N-n+1),x))
    x = x[ind]
    is_left_end = np.zeros(N-n+1,np.bool)
    is_left_end[1:] = (x[1:] != x[:-1])
    is_left_end[0] = 1
    is_right_end = np.zeros(N-n+1,np.bool)
    is_right_end[:-1] = (x[:-1] != x[1:])
    is_right_end[-1] = 1
    gap = ind[is_right_end] - ind[is_left_end]
    return gap.max() >= n

left = 0 
right = N+1 
while left + 1 < right:
    mid = (left + right)//2
    if test(mid):
        left = mid
    else:
        right = mid

answer = left
print(answer)

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

def check(L):
  a = set()
  for i in range(N - (L * 2) + 1):
    a.add(S[i:i+L])
    if S[i+L:i+L+L] in a:
      return True
  return False

left = 0
right = N // 2 + 1
while right - left > 1:
  mid = left + (right - left) // 2
  if check(mid):
    left = mid
  else:
    right = mid
print(left)

Solution (Python):

import sys
import collections
import itertools


def solve(N: int, S: str):
    dp = [[0 for _ in range(N)] for _ in range(N)]

    for i in range(N):
        if S[i] == S[-1]:
            dp[i][N-1] = 1

    res = 0
    for i in range(N-2,-1,-1):
        for j in range(N-2,i,-1):
            if S[i] == S[j]:
                dp[i][j] = dp[i+1][j+1] + 1
                l = dp[i][j]
                if j >= i+l:
                    res = max(res,l)

    print(res)




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()
N = [0]*n
j = 0

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

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]

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

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

print(ans)

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]

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

n = 1
ans = 0
for i in range(N):
    s = S[i:i + n]
    while s in S[i + n:]:
        n += 1
        s = S[i:i + n]
        ans += 1

print(ans)

Solution (Python):
n=int(input())
s=input()
l=0;r=0;ans=0
while r<n:
  t=s[l:r]
  if t in s[r:n]:
    ans=max(ans,len(t))
    r+=1
  else:
    l+=1
print(ans)

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

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

@mt
def slv(N, S):
    dp = [[0] * (N+1) for _ in range(N+1)]

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

    return ans


def main():
    N = read_int()
    S = read_str()
    print(slv(N, S))


if __name__ == '__main__':
    main()

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

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

ans = 0
for j in range(N):
    prefix = lcp(S[j:])
    for i, p in enumerate(prefix):
        if p <= i:
            ans = max(ans, p)
print(ans)

Solution (Python):



import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
s = input()
dp = [[0]*(n+1) for _ in range(n+1)]
dp[-1][-1] = 1
for i in range(n)[::-1]:
    for j in range(n)[::-1]:
        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(i-j,dp[i][j]))
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

N = int(input())
S = np.array([ord(x) for x in input().rstrip()],dtype=np.int64)

MOD = 10**9 + 7
base = 1234

def cumprod(arr):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr,Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    return arr.ravel()[:L]

x = np.full(N,base,np.int64); x[0] = 1
power = cumprod(x)
x = np.full(N,pow(base,MOD-2,MOD),np.int64); x[0] = 1
power_inv = cumprod(x)


H = S * power % MOD
Hcum = H.cumsum() % MOD

def test(n):
    
    x = (Hcum[n-1:N] - Hcum[:N-n+1] + H[:N-n+1]) % MOD
    x *= power_inv[:N-n+1]
    x %= MOD
    for i,a in np.ndenumerate(x):
        if (x[i[0]+n:] == a).any():
            return True
    return False

left = 0 
right = N+1 
while left + 1 < right:
    mid = (left + right)//2
    if test(mid):
        left = mid
    else:
        right = mid

answer = left
print(answer)

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

ok, ng = 0, n//2+1
while ng-ok > 1:
	x = (ok+ng)//2
	possible = False
	d = set()
	for i in range(n-2*x+1):
		d.add(s[i:i+x])
		if s[i+x:i+2*x] in d:
			possible = True
			break
	if possible:
		ok = x
	else:
		ng = x
print(ok)

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

Solution (Python):
tmp = input()
my_str = input()
 
start = 0
end = 1
max_len = 0
 
while (end < len(my_str)):
    if my_str[start:end] in my_str[end:]:
        if end - start > max_len:
            max_len = end - start
        end += 1
    else:
        start += 1
print(max_len)

Solution (Python):
P = 123456789012419
x = 31
ix = pow(x, P-2, P)
N = int(input())
A = [ord(s)-95 for s in input()]

def chk(k):
    D = {}
    s = 0
    for i in range(k):
        s = (s * x) % P
        s += A[i]
    X = [s]
    D[s] = k-1
    for i in range(k, N):
        s = ((s - pow(x, k-1, P) * A[i-k]) * x + A[i]) % P
        X.append(s)
        if s in D:
            if i - D[s] >= k:
                return 1
        else:
            D[s] = i
    return 0

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