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


def z_algo(N, S):
    end = 1
    start = 0
    max_length = 0

    while start < N:
        while end-start > N-end:
            break
        subword = S[start:end]
        if subword in S[end:]:
            max_length = max(max_length, len(subword))
            end += 1
        else:
            start += 1
            if start == end:
                end += 1
    return max_length


def solve(N: int, S: str):
    print(z_algo(N, S))
    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):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    d = {"Sunny":1 , "Cloudy":2, "Rainy":0}
    a = ["Sunny", "Cloudy", "Rainy"]
    print(a[d[input().rstrip()]])
    return


def B():
    s = S()
    for i, si in enumerate(s):
        if i % 2:
            if si == "R":
                print("No")
                return
        else:
            if si == "L":
                print("No")
                return
    print("Yes")
    return


def C():
    n, k, q = LI()
    d = [0] * n
    for _ in range(q):
        a = II() - 1
        d[a] += 1
    for a in d:
        if k - (q - a) > 0:
            print("Yes")
        else:
            print("No")
    return


def D():
    n,m = LI()
    a = LI()
    q = []
    for ai in a:
        heappush(q, -ai)
    for _ in range(m):
        heappush(q, heappop(q) / 2)
    ans = 0
    while q:
        ans += int(-heappop(q))
    print(ans)
    return





def E():
    n = II()
    s = S()
    dp = [[0] * (n + 1) for i in range(n + 1)]
    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] = max(dp[i][j], dp[i + 1][j + 1] + 1)
            ans = max(ans, min(dp[i][j], j - i))
    print(ans)

    return


def F():
    return


if __name__ == '__main__':
    E()

Solution (Python):
import sys

def input(): return sys.stdin.readline()[:-1]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def MATINT(h): return [list(map(int, input().split())) for _ in range(h)]
def MATSTR(h): return [input() for _ in range(h)]
sys.setrecursionlimit(10 ** 9)
inf = float('inf')
mod = 10 ** 9 + 7

N = INT()
S = input()

dp = [[0] * (N + 1) for _ in range(N + 1)]
maxv = 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] + 1
        maxv = max(maxv, min(dp[i][j], j-i))
print(maxv)

Solution (Python):
def z_algolithm(S, x):
    length = len(S) - x
    A = [0]*length
    B = [0]
    i = 1; j = 0
    while i < length:
        while i+j < length and S[x+j] == S[x+i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        B.append(min(j, i))
        k = 1
        while k < length - i  and k + A[k] < j :
            A[i+k] = A[k]
            k += 1
        i += k
        j -= k
    ans = max(B)
    return ans

N = int(input())
S = input()
ans = max([z_algolithm(S, x) for x in range(N)])
print(ans)

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

ans = 0
for i in range(N-1):
    for j in range(i+1, N):
        if S[i] == S[j]:
            if i != 0:
                if S[i-1] == S[j-1]:
                    continue
            equal = 1
            for k in range(1, min(j-i, N-j)):
                if S[i+k] == S[j+k]:
                    equal += 1
                else:
                    break
            ans = max(ans, equal)

print(ans)

Solution (Python):
N = int(input())
S = input()
 
def z_algo(s):
    s_length = len(s)
    l, r = 0, 0
    Z = [0]*s_length
    Z[0] = s_length
    for i in range(1, s_length):
        if r<i:
            l, r = i, i
            while r<s_length and s[r]==s[r-l]:
                r += 1
            Z[i] = r-i
            r -= 1
        else:
            k = i-l
            if i+Z[k]-1<r:
                Z[i] = Z[k]
            else:
                l = i
                while r<s_length and s[r]==s[r-l]:
                    r += 1
                Z[i] = r-i
                r -= 1
    return Z

ans = 0
for i in range(N):
    z = z_algo(S[i:])
    for j in range(i, N):
        ans = max(ans, min(j-i, z[j-i]))
print(ans)

Solution (Python):
N = int(input())
S = input()
 
def z_algo(s):
    s_length = len(s)
    l, r = 0, 1
    Z = [0]*s_length
    Z[0] = s_length
    for i in range(1, s_length):
        if r<i:
            l, r = i, i
            while r<s_length and s[r]==s[r-l]:
                r += 1
            Z[i] = r-i
            r -= 1
        else:
            k = i-l
            if i+Z[k]-1<r:
                Z[i] = Z[k]
            else:
                l = i
                while r<s_length and s[r]==s[r-l]:
                    r += 1
                Z[i] = r-i
                r -= 1
    return Z

ans = 0
for i in range(N):
    z = z_algo(S[i:])
    for j in range(i, N):
        ans = max(ans, min(j-i, z[j-i]))
print(ans)

Solution (Python):
N = int(input())
S = input()
 
left = 0
right = 1
max_length = 0
 
while left < N:
    if right - left > N - right:
        break
    serch_str = S[left:right]
    if serch_str in S[right:]:
        max_length = max(max_length, len(serch_str))
        right += 1
    else:
        left += 1
 
print(max_length)

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

left = 0
right = 1
max_length = 0

while left < N:
    if right - left > N - right:
        break
    serch_str = S[left:right]
    if serch_str in S[right:]:
        max_length = max(max_length, len(serch_str))
        right += 1
    else:
        left += 1

print(max_length)

Solution (Python):
N=int(input())
S=input()
maxLen=i=j=0
while j<N:
  if j-i > N-j:
      break  

  t=S[i:j]
  if t in S[j:]:
    maxLen=max(maxLen,len(t))
    j+=1
  else:
    i+=1
print(maxLen)

Solution (Python):
from heapq import heappush, heappop
import queue
import re
import math
import functools

def s_raw():
    return input().rstrip("\r")

def int_raw():
    return int(input())


def ss_raw():
    return input().split()


def ints_raw():
    return list(map(int, ss_raw()))


INF = 1 << 29


def make1d_arr(n, val=INF):
    return [val for i in range(n)]


def make2d_arr(h, w, val=INF):
    return [[val for i in range(w)]for i in range(h)]


def gcd(a, b):
    if(b == 0):
        return a
    return gcd(b, a % b)


def BFord(n,es):
    v_cost = [INF]*n
    v_cost[0] = 0
    for v in range(n*2):
        for e in es:
            frm = e[0]
            to = e[1]
            if v_cost[to] > v_cost[frm]+e[2]:
                v_cost[to] = v_cost[frm]+e[2]
                if v >= n:
                    v_cost[to] = -INF
        if v == n-1:
            prev = v_cost[:]
    v_cost = [-INF if prev[idx]!=v_cost[idx] else v_cost[idx] for idx in range(n)]
    return v_cost
    
def ZAlgo(s):
    l = len(s)
    A = [0]*l
    i =1
    j =0
    A[0]=l
    while i<l:
        while i+j<l and s[j] == s[i+j]:
            j+=1
        if j==0:
            i+=1
            continue
        A[i]=j
        k=1
        while (i+k<l) and (k+A[k]<j):
            A[i+k] =A[k]
            k+=1
        i+=k
        j-=k
    return A


def main():
    n = int_raw()
    S = s_raw()
    ans = 0
    for s_idx in range(len(S)):
        A = ZAlgo(S[s_idx:])
        ans = max([min(idx,a) for idx,a in enumerate(A)]+[ans])
    return ans


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

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

i = 0
j = 1
res = 0
while j < N:
    sub = S[i:j]
    main = S[j:]
    if sub in main:
        j += 1
        res = max(res, len(sub))
    else:
        i += 1
    if i == j:
        i += 1
        j += 2
print(res)

Solution (Python):
N=int(input())
S=input()
a=i=j=0
while j<N:
  if j-i > N-j:
      break  

  t=S[i:j]
  if t in S[j:]:
    a=max(a,len(t))
    j+=1
  else:
    i+=1
print(a)

Solution (Python):
def z_argorithm(s):
    s_len=len(s)
    a=[0]*s_len
    c=0
    for i in range(1,s_len):
        if i+a[i-c] < c+a[c]:
            a[i]=a[i-c]
        else:
            j=max(0,c+a[c]-i)
            while i+j<s_len and s[j]==s[j+i]:
                j += 1
            a[i]=j
            c=i
    return a
def main():
    n=int(input())
    s=input()
    ans = 0
    for i in range(n-1):
        a = z_argorithm(s[i:])
        A=len(a)
        for i in range(A):
            ans=max(ans,min(i,a[i]))
    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()
def Z(s):
    """
    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
        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 resolve():
    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):
class RollingHash():
    def __init__(self, s):
        self.length = len(s)
        self.base = 1009
        self.mod = (1 << 127) - 1
        self.hash = [0] * (self.length + 1)
        self.pow = [1] * (self.length + 1)
 
        for i in range(self.length):
            self.hash[i+1] = (self.hash[i] + ord(s[i])) * self.base % self.mod
            self.pow[i+1] = self.pow[i] * self.base % self.mod
 
    def get(self, l, r):
        t = self.hash[r] - self.hash[l] * self.pow[r-l] % self.mod
        t = (t + self.mod) % self.mod
        return t
 
n = int(input())
s = input()
RH = RollingHash(s)
 
def check(l):
    place = {}
    for i in range(n - l + 1):
        hs = RH.get(i, i + l)
        if hs in place:
            if i - place[hs] >= l:
                return True
        else:
            place[hs] = i
    return False

l = 0; r = n // 2 + 1
while r - l > 1:
    m = (l + r) // 2
    if check(m):
        l = m
    else:
        r = m

print(l)

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

Solution (Python):
class RollingHash():
    def __init__(self, s):
        self.mask30 = (1 << 30) - 1
        self.mask31 = (1 << 31) - 1
        self.length = len(s)
        self.base = 1009
        self.mod = (1 << 61) - 1
        self.hash = [0] * (self.length + 1)
        self.pow = [1] * (self.length + 1)

        for i in range(self.length):
            self.hash[i+1] = self.calcmod(self.mul(self.hash[i], self.base) + ord(s[i]))
            self.pow[i+1] = self.calcmod(self.mul(self.pow[i], self.base))
    
    def mul(self, l, r):
        lu = l >> 31
        ld = l & self.mask31
        ru = r >> 31
        rd = r & self.mask31
        middle = ld * ru + lu * rd
        return ((lu * ru) << 1) + ld * rd + ((middle & self.mask30) << 31) + (middle >> 30)
    
    def calcmod(self, val):
        val = (val & self.mod) + (val >> 61)
        if val > self.mod:
            val -= self.mod
        return val

    def get(self, l, r):
        t = self.calcmod(self.hash[r] - self.mul(self.hash[l], self.pow[r-l]) + self.mod)
        return t

n = int(input())
s = input()
RH = RollingHash(s)

def check(l):
    place = {}
    for i in range(n - l + 1):
        hs = RH.get(i, i + l)
        if hs in place:
            if i - place[hs] >= l:
                return True
        else:
            place[hs] = i
    return False

l = 0; r = n // 2 + 1
while r - l > 1:
    m = (l + r) // 2
    if check(m):
        l = m
    else:
        r = m

print(l)

Solution (Python):
class RollingHash():
    def __init__(self, s):
        self.mask30 = (1 << 30) - 1
        self.mask31 = (1 << 31) - 1
        self.length = len(s)
        self.base = 1009
        self.mod = (1 << 61) - 1
        self.hash = [0] * (self.length + 1)
        self.pow = [1] * (self.length + 1)

        for i in range(self.length):
            self.hash[i+1] = self.calcmod(self.mul(self.hash[i], self.base) + ord(s[i]))
            self.pow[i+1] = self.calcmod(self.mul(self.pow[i], self.base))
    
    def mul(self, l, r):
        lu = l >> 31
        ld = l & self.mask31
        ru = r >> 31
        rd = r & self.mask31
        middle = ld * ru + lu * rd
        return ((lu * ru) << 1) + ld * rd + ((middle & self.mask30) << 31) + (middle >> 30)
    
    def calcmod(self, val):
        val = (val & self.mod) + (val >> 61)
        if val > self.mod:
            val -= self.mod
        return val

    def get(self, l, r):
        t = self.hash[r] - self.hash[l] * self.pow[r-l] % self.mod
        t = (t + self.mod) % self.mod
        return t

n = int(input())
s = input()
RH = RollingHash(s)

def check(l):
    place = {}
    for i in range(n - l + 1):
        hs = RH.get(i, i + l)
        if hs in place:
            if i - place[hs] >= l:
                return True
        else:
            place[hs] = i
    return False

l = 0; r = n // 2 + 1
while r - l > 1:
    m = (l + r) // 2
    if check(m):
        l = m
    else:
        r = m

print(l)

Solution (Python):
class RollingHash():
    def __init__(self, s):
        self.length = len(s)
        self.base1 = 1009
        self.base2 = 1007
        self.mod1 = 10**9 + 7
        self.mod2 = 10**9 + 9
        self.hash1 = [0] * (self.length + 1)
        self.hash2 = [0] * (self.length + 1)
        self.pow1 = [1] * (self.length + 1)
        self.pow2 = [1] * (self.length + 1)

        for i in range(self.length):
            self.hash1[i+1] = (self.hash1[i] + ord(s[i])) * self.base1 % self.mod1
            self.hash2[i+1] = (self.hash2[i] + ord(s[i])) * self.base2 % self.mod2
            self.pow1[i+1] = self.pow1[i] * self.base1 % self.mod1
            self.pow2[i+1] = self.pow2[i] * self.base2 % self.mod2
        
    def get(self, l, r):
        t1 = self.hash1[r] - self.hash1[l] * self.pow1[r-l] % self.mod1
        t1 = (t1 + self.mod1) % self.mod1
        t2 = self.hash2[r] - self.hash2[l] * self.pow2[r-l] % self.mod2
        t2 = (t2 + self.mod2) % self.mod2
        return (t1, t2)

class FastRollingHash():
    def __init__(self, s):
        self.length = len(s)
        self.base = 1009
        self.mod = (1 << 61) - 1
        self.hash = [0] * (self.length + 1)
        self.pow = [1] * (self.length + 1)

        for i in range(self.length):
            self.hash[i+1] = (self.hash[i] + ord(s[i])) * self.base % self.mod
            self.pow[i+1] = self.pow[i] * self.base % self.mod

    def get(self, l, r):
        t = self.hash[r] - self.hash[l] * self.pow[r-l] % self.mod
        t = (t + self.mod) % self.mod
        return t

n = int(input())
s = input()
RH = RollingHash(s)

def check(l):
    place = {}
    for i in range(n - l + 1):
        hs = RH.get(i, i + l)
        if hs in place:
            if i - place[hs] >= l:
                return True
        else:
            place[hs] = i
    return False

l = 0; r = n // 2 + 1
while r - l > 1:
    m = (l + r) // 2
    if check(m):
        l = m
    else:
        r = m

print(l)

Solution (Python):
class RollingHash():
    def __init__(self, s):
        self.length = len(s)
        self.base1 = 1009
        self.base2 = 1007
        self.mod1 = 10**9 + 7
        self.mod2 = 10**9 + 9
        self.hash1 = [0] * (self.length + 1)
        self.hash2 = [0] * (self.length + 1)
        self.pow1 = [1] * (self.length + 1)
        self.pow2 = [1] * (self.length + 1)

        for i in range(self.length):
            self.hash1[i+1] = (self.hash1[i] + ord(s[i])) * self.base1 % self.mod1
            self.hash2[i+1] = (self.hash2[i] + ord(s[i])) * self.base2 % self.mod2
            self.pow1[i+1] = self.pow1[i] * self.base1 % self.mod1
            self.pow2[i+1] = self.pow2[i] * self.base2 % self.mod2
        
    def get(self, l, r):
        t1 = self.hash1[r] - self.hash1[l] * self.pow1[r-l] % self.mod1
        t1 = (t1 + self.mod1) % self.mod1
        t2 = self.hash2[r] - self.hash2[l] * self.pow2[r-l] % self.mod2
        t2 = (t2 + self.mod2) % self.mod2
        return (t1, t2)

class FastRollingHash():
    def __init__(self, s):
        self.length = len(s)
        self.base = 1009
        self.mod = (1 << 61) - 1
        self.hash = [0] * (self.length + 1)
        self.pow = [1] * (self.length + 1)

        for i in range(self.length):
            self.hash[i+1] = (self.hash[i] + ord(s[i])) * self.base % self.mod
            self.pow[i+1] = self.pow[i] * self.base % self.mod

    def get(self, l, r):
        t = self.hash[r] - self.hash[l] * self.pow[r-l] % self.mod
        t = (t + self.mod) % self.mod
        return t

n = int(input())
s = input()
RH = FastRollingHash(s)

def check(l):
    place = {}
    for i in range(n - l + 1):
        hs = RH.get(i, i + l)
        if hs in place:
            if i - place[hs] >= l:
                return True
        else:
            place[hs] = i
    return False

l = 0; r = n // 2 + 1
while r - l > 1:
    m = (l + r) // 2
    if check(m):
        l = m
    else:
        r = m

print(l)

Solution (Python):
n = int(input())
s = input()
l = [[0] * n for _ in range(n)]
ans = 0

for i in range(n)[::-1]:
    for j in range(n)[::-1]:
        if i >= j and s[i] == s[j]:
            l[i][j] += 1
            
            if i < n-1 and j < n-1 and l[i+1][j+1] > 0:
                l[i][j] += l[i+1][j+1]
                
        now = min(l[i][j], i - j)
        ans = max(ans, now)

print(ans)

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

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

Solution (Python):
N = int(input())
S = list(input()) + ["!"]
dp = [[0] * N for _ in range(N)]
for j in range(1, N):
  if S[0] == S[j]:
    dp[0][j] = 1
res = 0
for i in range(N):
  for j in range(i, N):
    res = max(dp[i][j], res)
    if i == N - 1 or j == N - 1:
      continue
    if S[i + 1] == S[j + 1] and j - i > dp[i][j]:
      dp[i + 1][j + 1] = dp[i][j] + 1
    else:
      dp[i + 1][j + 1] = 0
print(res)

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

print(ans)

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

result=0
for i in range(1,n):
    ml=min(i,n-i)
    count=0
    for j in range(n-i):
        if s[j]==s[j+i]:
            count+=1
        else:
            result=max(count,result)
            count=0
        if count==ml:
            result=max(result,count)
            break
        result=max(result,count)
print(result)

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

result = 0
for i in range(1, n):
    maxLen = min(i, n-i)
    tmp = 0
    for j in range(n-i):
        if s[j] == s[j+i]:
            tmp += 1
        else:
            if result < tmp:
                result = tmp
            tmp = 0
        if tmp == maxLen:
            break
    if result < tmp:
        result = tmp
print(result)

Solution (Python):
N = int(input())
S = input()
B = 127
MOD = 10 ** 11 + 7

H = [0] * (len(S) + 1)
P = [1] * (len(S) + 1)
b = pow(B, N-1)
for i in range(len(S)):
    H[i+1] = (H[i] + ord(S[i]) * b) % MOD
    P[i+1] = (P[i] * B) % MOD
    b //= B

l = 0
r = N
ans = 0
while r - l > 1:
    mid = (l + r) // 2
    tmp = {}
    for i in range(N - mid + 1):
        h = ((H[mid+i] - H[i]) * P[mid+i-1]) % MOD
        if h in tmp and i - tmp[h] >= mid:
            l = mid
            ans = mid
            break
        else:
            if not h in tmp:
                tmp[h] = i
    else:
        r = mid
        
print(ans)

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

Solution (Python):

class RollingHash:
    def __init__(self, source: str, base=1007, mod=10 ** 9 + 7):
        self.source = source
        self.length = len(source)
        self.base = base
        self.mod = mod
        self.hash = self._get_hash_from_zero()
        self.power = self._get_base_pow()

    def _get_hash_from_zero(self):  
        cur, hash_from_zero = 0, [0]
        for e in self.source:
            cur = (cur * self.base + ord(e)) % self.mod
            hash_from_zero.append(cur)
        return hash_from_zero

    def _get_base_pow(self):  
        cur, power = 1, [1]
        for i in range(self.length):
            cur *= self.base % self.mod
            power.append(cur)
        return power

    def get_hash(self, l: int, r: int):  
        return (self.hash[r] - self.hash[l] * self.power[r - l]) % self.mod


def main():
    N = int(input())
    S = input().rstrip()
    rh, ok, ng = RollingHash(S), 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        flg, memo = 0, set()
        for i in range(N - 2 * mid + 1):
            memo.add(rh.get_hash(i, i + mid))
            if rh.get_hash(i + mid, i + 2 * mid) in memo:
                flg = 1
                break
        if flg:
            ok = mid  
        else:
            ng = mid  
    print(ok)  


if __name__ == "__main__":
    main()

Solution (Python):

class RollingHash:
    def __init__(self, source: str, base=1007, mod=10 ** 9 + 7):
        self.source = source
        self.length = len(source)
        self.base = base
        self.mod = mod
        self.hash = self._get_hash_from_zero()
        self.power = self._get_base_pow()

    def _get_hash_from_zero(self):  
        cur, hash_from_zero = 0, [0]
        for e in self.source:
            cur = (cur * self.base + ord(e)) % self.mod
            hash_from_zero.append(cur)
        return hash_from_zero

    def _get_base_pow(self):  
        cur, power = 1, [1]
        for i in range(self.length):
            cur *= self.base % self.mod
            power.append(cur)
        return power

    def get_hash(self, l: int, r: int):  
        return (self.hash[r] - self.hash[l] * self.power[r - l]) % self.mod


def main():
    N = int(input())
    S = input().rstrip()
    rh, ok, ng = RollingHash(S), 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        flg, memo = 0, set()
        for i in range(N - 2 * mid + 1):
            memo.add(rh.get_hash(i, i + mid))
            if rh.get_hash(i + mid, i + 2 * mid) in memo:
                flg = 1
                break
        if flg:
            ok = mid  
        else:
            ng = mid  
    print(ok)  


if __name__ == "__main__":
    main()

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

def main():
    N = int(input())
    S = input()
    left = 0
    right = 1
    ans = 0
    while left < N:
        S1 = S[left:right]
        S2 = S[right:]
        if S1 in S2:
            ans = max(ans, len(S1))
            right += 1
        else:
            left += 1
    print(ans)

if __name__ == '__main__': main()

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

left = 0
right = 1
ans = 0

while left < n:
    s1 = s[left:right]
    s2 = s[right:]
    if s1 in s2:
        ans = max(ans,len(s1))
        right += 1
    else:
        left += 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):
    T = S[i:]
    Ai = z_algo(T)
    for j in range(len(Ai)):
        if Ai[j] <= j:
            ans = max(ans, Ai[j])

print(ans)

Solution (Python):
import math
MOD = pow(2,61) - 1
def charToNum(char):
    return ord(char) - 96

def check(string,subLen):
    if subLen == 0: return True
    
    
    
    dictOfRollingHash = {}
    totalLen = len(string)
    h = 0
    b = 1
    for i in range(subLen):
        c = string[subLen - 1 - i]
        h += charToNum(c) * b
        b *= 27
        b %= MOD
    h %= MOD
    dictOfRollingHash[h] = 0
    maxBase = pow(27,subLen - 1,MOD) 
    for i in range(1,totalLen - subLen + 1):
        h -= maxBase * charToNum(string[i - 1])
        h *= 27
        h += charToNum(string[i + subLen - 1])
        h %= MOD
        if h in dictOfRollingHash:
            if i - dictOfRollingHash[h] >= subLen:
                return True
        else:
            dictOfRollingHash[h] = i
    return False

N = int(input())
S = input()
ok = 0
ng = N + 1
while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    if check(S,mid):
        ok = mid
    else:
        ng = mid
print(ok)

Solution (Python):
import sys

sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def fi(): return float(input())
def mfi(): return map(float, input().rstrip().split())
def lmfi(): return list(map(float, input().rstrip().split()))
def li(): return list(input().rstrip())
def si(): return input().rstrip()
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()



class RollingHash():
    """ロリハ。容易に衝突するので注意。"""
    BASE1 = 1007
    BASE2 = 2009
    MOD1 = 1000000007
    MOD2 = 1000000009

    def __init__(self, s, opt=2):
        self.n = len(s)
        self.opt = opt
        self.hash1 = [0] * (self.n + 1)
        self.power1 = [1] * (self.n + 1)
        if opt == 2:  
            self.hash2 = [0] * (self.n + 1)
            self.power2 = [1] * (self.n + 1)

        for i, e in enumerate(s):
            self.hash1[i + 1] = (self.hash1[i] * self.__class__.BASE1 + ord(e)) % self.__class__.MOD1
            self.power1[i + 1] = (self.power1[i] * self.__class__.BASE1) % self.__class__.MOD1
        if opt == 2:  
            for i, e in enumerate(s):
                self.hash2[i + 1] = (self.hash2[i] * self.__class__.BASE2 + ord(e)) % self.__class__.MOD2
                self.power2[i + 1] = (self.power2[i] * self.__class__.BASE2) % self.__class__.MOD2

    def get(self, l: int, r: int):
        res1 = self.hash1[r] - self.hash1[l] * self.power1[r - l] % self.__class__.MOD1
        if(res1 < 0):
            res1 += self.__class__.MOD1
        if self.opt == 2:
            res2 = self.hash2[r] - self.hash2[l] * self.power2[r - l] % self.__class__.MOD2
            if(res2 < 0):
                res2 += self.__class__.MOD2

        if self.opt == 2:
            return (res1, res2)
        else:
            return res1

if not __debug__:
    import io
    import random
    class MyStdin(io.TextIOWrapper):
        @classmethod
        def readline(cls):
            N = 1000000
            yield "{}\n".format(N)
            yield "{}\n".format(''.join([chr(random.randint(0, 25) + ord("a")) for i in range(N // 5)] * 5))
    input = MyStdin.readline().__next__

def ABC131E():
    N = ii()
    S = si()
    rh = RollingHash(S)
    def check(n: int):
        d = dict()
        for i in range(N - n + 1):
            p = rh.get(i, i + n)
            if p in d:
                if(i - d[p] >= n):
                    return True
            else:
                d[p] = i
        return False
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if check(mid):
            ok = mid
        else:
            ng = mid
    print(ok)



if __name__ == '__main__':
    if not __debug__:
        import cProfile
        cProfile.run('ABC131E()', sort=1)
    else:
        ABC131E()

Solution (Python):

import sys
import collections


def main():
    n = int(sys.stdin.readline().strip())
    s = sys.stdin.readline().strip()
    
    dp = [[0] * n for _ in range(n)]

    for i in range(n):
        dp[i][i] = 1

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


main()