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

def Z_algo(string):
    n = len(string)
    A = [0] * n
    A[0] = n
    i = 1
    j = 0
    while i < n:
        while i+j < n and string[j] == string[i+j]:
            j += 1
        A[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < n and k+A[k] < j:
            A[i+k] = A[k]
            k += 1
        i += k
        j -= k
    return A

ans = 0

for i in range(N):
    A = Z_algo(S[i:])
    res = 0
    for j, a in enumerate(A):
        res = max(res, min(a, j))
    ans = max(ans, res)
    
print(ans)

Solution (Python):

N = int(input())

S = input()
CS = S

ans = 0

for i in range(N):

    now = 0
    for j in range(N):

        if S[j] == CS[j]:
            now += 1
        else:
            ans = max(ans, min(i,now) )
            now = 0

    ans = max( ans , min(i,now) )

    CS = " "+CS

print (ans)

Solution (Python):

def main():
    n=int(input())
    s=str(input())
    
    dp=[[0]*n for _ in range(n)]
    
    for i in range(n):
        for j in range(i,n):
            if i==j:
                dp[i][j]==i
                
            elif i==0:
                if s[i]==s[j]:
                    dp[i][j]=1
            
            else:
                 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,n):
            ans=max(ans,min(j-i,dp[i][j]))
            
    print(ans)
    
main()

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    s = input()
    if s == "Sunny":
        print("Cloudy")
    elif s == "Cloudy":
        print("Rainy")
    else:
        print("Sunny")
    return


def B():
    s = S()
    for i in range(len(s)):
        if i%2:
            if s[i] not in ["L","U","D"]:
                print("No")
                return
        else:
            if s[i] not in ["R","U","D"]:
                print("No")
                return
    print("Yes")
    return


def C():
    n,k,q = LI()
    a = IR(q)
    f = [k-q]*(n)
    for i in range(q):
        ai = a[i]-1
        f[ai] += 1
    for i in f:
        if i <= 0:
            print("No")
        else:
            print("Yes")
    return


def D():
    n,m = LI()
    a = LI()
    q = []
    for i in range(n):
        heappush(q,-a[i])
    for i in range(m):
        x = heappop(q)
        x *= -1
        x >>= 1
        heappush(q,-x)
    print(-sum(q))
    return


def E():
    n = I()
    s = S()
    l = 0
    r = n
    M = 10**640+1
    b = 26
    alp = list("abcdefghijklmnopqrstuvwxyz")
    f = {}
    for i in alp:
        f[i] = ord(i)-ord("a")
    pb = [pow(b,i,M) for i in range(n+1)]
    while r-l > 1:
        m = (l+r)>>1
        d = defaultdict(lambda : float("inf"))
        hash = 0
        for i in s[:m]:
            hash *= b
            hash += f[i]
            hash %= M
        d[hash] = 0
        t = pb[m]
        for i in range(n-m):
            si = s[i]
            hash *= b
            hash -= t*f[si]
            hash += f[s[i+m]]
            hash %= M
            if d[hash]+m <= i+1:
                l = m
                break
            if i+1 < d[hash]:
                d[hash] = i+1
        else:
            r = m
    print(l)
    return


def F():

    return


if __name__ == "__main__":
    E()

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

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

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

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

print(ans)

Solution (Python):
import sys

input = sys.stdin.readline

def LcpByZ(target):
    len_t = len(target)
    lcp = [-1] * len_t
    top = 1  
    right = 0  
    lcp[0] = 0
    while top < len_t:
        
        while top + right < len_t and target[right] == target[top + right]:
            right += 1
        
        lcp[top] = right
        left = 1
        
        if right == 0:
            top += 1
            continue
        
        while left + lcp[left] < right and left < right:
            lcp[top + left] = lcp[left]
            left += 1
        
        top += left
        right -= left
    return max(min(i,x) for i,x in enumerate(lcp))

def main():
    n = int(input())
    s = input()[:-1]
    ans = 0
    for i in range(n):
        ans = max(ans, LcpByZ(s[i:]))
    print(ans)

main()

Solution (Python):
import sys

input = sys.stdin.readline

def main():
    def hash_ini(t):
        h = 0
        p = 1
        for i in range(1, len(t) + 1):
            h = hash_table[i] = (h * base + t[i - 1]) % hash_md
            p = pw[i] = p * base % hash_md

    
    def hash_ij(i, j):
        return (hash_table[j] - hash_table[i] * pw[j - i]) % hash_md

    n = int(input())
    s = input()[:-1]

    
    base = 31
    hash_md = pow(3, 19)
    ord_a = ord('a')
    t = [ord(c) - ord_a for c in s]
    hash_table = [0] * (len(t) + 1)
    pw = [1] * (len(t) + 1)
    hash_ini(t)

    
    ok = 0
    ng = n // 2 + 1
    while ok + 1 < ng:
        w = (ok + ng) // 2
        hashes = []
        for i in range(w):
            hashes.append(hash_ij(i, i + w))
        passed = set()
        for i in range(w, n - w + 1):
            passed.add(hashes[i - w])
            cur = hash_ij(i, i + w)
            if cur in passed:
                ok = w
                break
            hashes.append(cur)
        else:
            ng = w

    print(ok)

main()

Solution (Python):
N = int(input())
S = input()
dp = [[0]*(N+1) for _ 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(i, N):
        ans = max(min(dp[i][j], j-i), ans)
print(ans)

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

def z_algorithm(str):
    len_str = len(str)
    p = [0] * len_str
    j = 0
    for i in range(1, len_str):
        if i + p[i-j] < j + p[j]:
            p[i] = p[i-j]
        else:
            k = max(0, j+p[j]-i)
            while i + k < len_str and str[k] == str[i+k]:
                k += 1
            p[i] = k
            j = i
    p[0] = len_str
    return p

ans = 0
for x in range(n):
    temp = [] + z_algorithm(s[x:])
    for y in range(n - x):
        z = min(temp[y], y)
        ans = max(ans, z)

print(ans)

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

length = 0 

for i in range(N):
    l1 = i
    l2 = i + length
    _word = S[l1:l2]
    _S = S[l2:]
    while _word in _S:
        l2 += 1
        _word = S[l1:l2]
        _S = S[l2:]
    length = max(len(_word)-1, length)

print(length)

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

length = 0 

for i in range(N):
    l1 = i
    l2 = i + length
    _word = S[l1:l2]
    _S = S[l2:]
    while _word in _S and l1 + len(_word) <= l2:
        l2 += 1
        _word = S[l1:l2]
        _S = S[l2:]
    length = max(len(_word)-1, length)

print(length)

Solution (Python):
class Rori:
  B1 = 1009
  B2 = 1007
  MOD1 = 10 ** 9 + 7
  MOD2 = 10 ** 9 + 9
  H1, H2 = None, None
  P1, P2 = None, None
  def __init__(s, L):
    n = len(L) + 1
    s.H1 = [0] * n
    s.H2 = [0] * n
    s.P1 = [1] * n
    s.P2 = [1] * n
    for i in range(n - 1):
      S = ord(L[i]) - ord('a') + 1
      s.H1[i + 1] = (s.H1[i] * s.B1 + S) % s.MOD1
      s.H2[i + 1] = (s.H2[i] * s.B2 + S) % s.MOD2
      s.P1[i + 1] = s.P1[i] * s.B1 % s.MOD1
      s.P2[i + 1] = s.P2[i] * s.B2 % s.MOD2
  def hashLR(s, l, r):
    t = ((s.H1[r] - s.H1[l] * s.P1[r - l]) % s.MOD1 + s.MOD1) % s.MOD1
    k = ((s.H2[r] - s.H2[l] * s.P2[r - l]) % s.MOD2 + s.MOD2) % s.MOD2
    return (t, k)


class AVL:
  import sys
  sys.setrecursionlimit(1000000)
  class Node:
    def __init__(s, k):
      s.k = k
      s.l = None
      s.r = None
      s.d = 1
  def __init__(s):
    s.x = None
  def l_rot(s, z):
    y = z.r
    t = y.l
    y.l, z.r = z, t
    z.d = s.get_depth(z)
    y.d = s.get_depth(y)
    return y
  def r_rot(s, z):
    y = z.l
    t = y.r
    y.r, z.l = z, t
    z.d = s.get_depth(z)
    y.d = s.get_depth(y)
    return y
  def depth(s, node):
    if not node:
      return 0
    else:
      return node.d
  def get_depth(s, node):
    return 1 + max(s.depth(node.l), s.depth(node.r))
  def add(s, k):
    s.x = s.add_sub(s.x, k)
  def add_sub(s, node, k):
    if not node:
      return s.Node(k)
    elif node.k == k:
      return node
    elif node.k > k:
      node.l = s.add_sub(node.l, k)
    else:
      node.r = s.add_sub(node.r, k)
    node.d = s.get_depth(node)
    bal = s.depth(node.l) - s.depth(node.r)
    if bal > 1:
      if node.l.k > k:
        return s.r_rot(node)
      else:
        node.l = s.l_rot(node.l)
        return s.r_rot(node)
    elif bal < -1:
      if node.r.k < k:
        return s.l_rot(node)
      else:
        node.r = s.r_rot(node.r)
        return s.l_rot(node)
    return node
  def check(s, k):
    return s.check_sub(k, s.x)
  def check_sub(s, k, node):
    if node == None:
      return False
    if node.k == k:
      return True
    if node.k > k:
      return s.check_sub(k, node.l)
    else:
      return s.check_sub(k, node.r)

def hersCode(n):
  ok = 0
  ng = n
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if nasu(mid):
      ok = mid
    else:
      ng = mid
  return ok

def nasu(n):
  L = [None] * (N - n + 1)
  for i in range(len(L)):
    L[i] = R.hashLR(i, i + n)
  T = AVL()
  T.add(L[0])
  for i in range(n, len(L)):
    if T.check(L[i]):
      return True
    T.add(L[i - n + 1])
  return False

def honya(x, y, n):
  for i in range(n):
    if S[x + i] != S[y + i]:
      return i
  return n

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

R = Rori(S)
print(hersCode(N))

Solution (Python):
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):
N=int(input())
S=list(input())

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


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

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

A=[]
for i in range(N):
  for j in range(i):
    A.append(dp[i][j])

print(max(A))

Solution (Python):
import sys

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 = list(input())
ans = 0

for t in range(N):
    L = z_algo(S[t:])
    for u in range(len(L)):
        if L[u] <= u:
            ans = max(ans,L[u])

print(ans)

Solution (Python):

class RollingHash:
    def __init__(self, source: str, base=1000000007, mod=9007199254740997):
        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, 27, 10 ** 9 + 7), 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=1000000007, mod=9007199254740997):
        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, 1007, 10 ** 9 + 7), 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=1000000007, mod=9007199254740997):
        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):
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):
N=int(input())
S=input()

max = 0
index = 0
for i in range(1,len(S)-1):
    s1=S[index:i]
    s2=S[i:]
    if s1 in s2:
        max=len(s1)
    else:
        index+=1
        
print(max)

Solution (Python):
N = int(input())
S = input()
l1 = length = 0
l2 = 1

while (l2 + length < N):
    if S[l1:l2] in S[l2:]:
        length = l2 - l1
        l2 += 1
    else:
        l1 += 1
        l2 = l1 + length + 1
print(length)

Solution (Python):
def main():
    N = int(input())
    S = input()
    l1 = length = 0
    l2 = 1

    while (l2 + length < N):
        if S[l1:l2] in S[l2:]:
            length = l2 - l1
            l2 += 1
        else:
            l1 += 1
            l2 = l1 + length + 1
    print(length)

main()

Solution (Python):
def main():
    N = int(input())
    S = input()
    l1 = length = 0
    l2 = 1

    while (l2 + length < N):
        if S[l1:l2] in S[l2:]:
            length = l2 - l1
            l2 += 1
        else:
            l1 += 1
            l2 = l1 + length + 1
    print(length)

main()

Solution (Python):
N=int(input())
S=input()
l,u=0,N
while l+1<u:
    m=(l+u)//2
    s=set()
    for i in range(N-m*2+1):
        s.add(S[i:i+m])
        if S[i+m:i+m*2] in s:
            l=m
            break
    if l!=m:
        u=m
print(l)

Solution (Python):
N = int(input())
S = input()
sride = 1
count = 0
max_num = 0
for i in range(N-1):
  for j in range(N-sride):
    if S[j] == S[j+sride]:
      count += 1
      max_num = max(max_num, count)
    else:
      count = 0
    if count == sride:
      break
  sride += 1
  count = 0
print(max_num)

Solution (Python):
import sys

def solve():
    N = int(input())
    S = input()
    sdict = dict()
    lens = len(S)
    for i in range(lens): sdict[i] = S[i]
    
    DP = [[0 for j in range(lens)] for i in range(lens - 1)]
    maxlength = 0
    for i in reversed(range(lens - 1)):
        for j in reversed(range(i + 1, lens)):
            if sdict[i] == sdict[j]:
                if j == lens - 1: DP[i][j] = 1
                else: DP[i][j] = DP[i+1][j+1] + 1
                maxlength = max(maxlength, min(DP[i][j], j - i))

    print(maxlength)
    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
import sys

def solve():
    N = int(input())
    S = input()
    lens = len(S)
    alp = ["a", "b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u",\
        "v","w","x","y","z"]
    
    DP = [[0 for j in range(lens)] for i in range(lens)]
    DP[lens - 2][lens - 1] = (1 if S[lens-2] == S[lens - 1] else 0)
    for i in reversed(range(lens - 1)):
        for j in reversed(range(i + 1, lens)):
            if S[i] == S[j]:
                if j == lens - 1: DP[i][j] = 1
                else: DP[i][j] = DP[i+1][j+1] + 1

    maxlength = 0
    for i in range(lens):
        for j in range(i+1, lens):
            maxlength = max(maxlength, min(DP[i][j], j - i))

    print(maxlength)
    return 0

if __name__ == "__main__":
    solve()

Solution (Python):


class RollingHash:

    PS1 = 1009
    PS2 = 1007
    PL1 = 100000007
    PL2 = 100000009

    def __init__(self, s: str):
        self._n = len(s) + 1
        self._pow1, self._pow2, self._hash1, self._hash2 = self._initialize(s, self._n)

    def _initialize(self, s: str, n: int):
        pow1 = [1 for _ in range(n)]
        pow2 = [1 for _ in range(n)]
        hash1 = [0 for _ in range(n)]
        hash2 = [0 for _ in range(n)]

        idx = 1
        for c in s:
            pow1[idx] = pow1[idx - 1] * self.PS1 % self.PL1
            pow2[idx] = pow2[idx - 1] * self.PS2 % self.PL2
            hash1[idx] = (hash1[idx - 1] * self.PS1 + ord(c) - ord('a') + 1) % self.PL1
            hash2[idx] = (hash2[idx - 1] * self.PS2 + ord(c) - ord('a') + 1) % self.PL2
            idx += 1

        return pow1, pow2, hash1, hash2

    def get(self, l: int, r: int):
        p1 = ((self._hash1[r] - self._hash1[l] * self._pow1[r - l]) % self.PL1 + self.PL1) % self.PL1
        p2 = ((self._hash2[r] - self._hash2[l] * self._pow2[r - l]) % self.PL2 + self.PL2) % self.PL2
        return p1, p2


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

rh = RollingHash(S)

MAGIC_NUMBER = 261

ans = 0
end = False
for l in range((N + 1) // 2, 1, -1):
    d = {}
    for idx in range(N - l + 1):
        p1, p2 = rh.get(idx, idx + l)
        lv, rv = d.get((p1, p2), (N, 0))
        lv = min(lv, idx)
        rv = max(rv, idx)
        d[(p1, p2)] = (lv, rv)

    for _, (lv, rv) in d.items():
        if rv - lv >= l:
            print(l)
            end = True
            break

    if end:
        break

if not end:
    print(0)

Solution (Python):
N = int(input())
S = input()
sride = 1
count = 0
max_num = 0
for i in range(N-1):
  for j in range(N-sride):
    if S[j] == S[j+sride]:
      count += 1
      max_num = max(max_num, count)
    else:
      count = 0
    if count == sride:
      max_num = max(max_num, count)
      break
  sride += 1
  count = 0
print(max_num)

Solution (Python):
n = int(input())
s = list(map(str, input().strip()))
seed = 131
mod1 = 10 ** 9 + 7
mod2 = 10 ** 9 + 7
lsd = [1] * 6000
lsd2 = [1] * 6000
hs = [1] * 6000
hs2 = [1] * 6000
hs[0] = ord(s[0]) - ord('a')
hs2[0] = ord(s[0]) - ord('a')
for i in range(1, n):
    lsd[i] = lsd[i - 1] * seed % mod1
    lsd2[i] = lsd2[i - 1] * seed % mod2
    hs[i] = (hs[i - 1] * seed + ord(s[i]) - ord('a')) % mod1
    hs2[i] = (hs2[i - 1] * seed + ord(s[i]) - ord('a')) % mod2


def check(x):
    from collections import defaultdict
    g = defaultdict(int)
    for i in range(n - x + 1):
        if i:
            t = (hs[i + x - 1] - hs[i - 1] * lsd[x]) % mod1
        else:
            t = hs[i + x - 1]
        
        if not g[t]:
            g[t] = i + 1
        elif g[t] + x - 1 <= i:
            return True
    return False


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

if check(r):
    print(r)
else:
    print(l)

Solution (Python):
n = int(input())
s = list(map(str, input().strip()))
seed = 131
mod1 = 10 ** 9 + 9
mod2 = 10 ** 9 + 7
lsd = [1] * 6000
lsd2 = [1] * 6000
hs = [1] * 6000
hs2 = [1] * 6000
hs[0] = ord(s[0]) - ord('a')
hs2[0] = ord(s[0]) - ord('a')
for i in range(1, n):
    lsd[i] = lsd[i - 1] * seed % mod1
    lsd2[i] = lsd2[i - 1] * seed % mod2
    hs[i] = (hs[i - 1] * seed + ord(s[i]) - ord('a')) % mod1
    hs2[i] = (hs2[i - 1] * seed + ord(s[i]) - ord('a')) % mod2


def check(x):
    from collections import defaultdict
    g = defaultdict(int)
    for i in range(n - x + 1):
        if i:
            t = (hs[i + x - 1] - hs[i - 1] * lsd[x]) % mod1
        else:
            t = hs[i + x - 1]
        
        if not g[t]:
            g[t] = i + 1
        elif g[t] + x - 1 <= i:
            return True
    return False


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

if check(r):
    print(r)
else:
    print(l)

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

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

maxL = 0

for i in range(1, N-1):
    cnt = 0
    left = 0
    for j in range(0, N-i):
        if S[j]==S[j+i]:
            cnt+=1
            if maxL < cnt:
                maxL = cnt
            if cnt == i:
                break
        else:
            cnt = 0
            left = j + 1

print(maxL)

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from itertools import *
INF = 10**10

CHRtoINT = defaultdict(int)
atoz = [chr(i) for i in range(97,97+26)]
for i, c in enumerate(atoz):
    CHRtoINT[c] = i

N, S = int(input()), input()
b = 26
m = 67280421310721
l, r = 0, N//2+1
while l+1 < r:
    x = (l+r)//2
    OK = 0
    dic = defaultdict(int)
    B, hash, b_inv = pow(b, x-1, m), 0, pow(b, m-2, m)
    t = B
    for c in S[:x]:
        hash = (hash + CHRtoINT[c] * t) % m
        t = t * b_inv % m
    dic[hash] = 0
    B *= b
    for i, c in enumerate(S[:-x]):
        hash = (hash * b - CHRtoINT[c] * B + CHRtoINT[S[i+x]]) % m
        if hash in dic:
            if i+1-dic[hash] >= x:
                OK = 1
                break
        else:
            dic[hash] = i+1
    if OK:
        l = x
    else:
        r = x
print(l)

Solution (Python):
from collections import deque

base = 10007
mod1 = int(1e9 + 7)
mod2 = int(1e9 + 9)


class RollingHash:
    def __init__(self, s):
        self.s = s
        self.len = len(s)
        self.mod1_table = [pow(base, i, mod1) for i in range(self.len + 2)]
        self.mod2_table = [pow(base, i, mod2) for i in range(self.len + 2)]
        self.inv1_table = [pow(self.mod1_table[i], mod1 - 2, mod1) for i in range(self.len + 2)]
        self.inv2_table = [pow(self.mod2_table[i], mod2 - 2, mod2) for i in range(self.len + 2)]
        self.elm_1 = [0]
        self.elm_2 = [0]
        for i in range(self.len):
            val_1 = self.elm_1[-1] + self.mod1_table[len(self.elm_1)] * ord(s[i])
            val_2 = self.elm_2[-1] + self.mod2_table[len(self.elm_2)] * ord(s[i])
            self.elm_1.append(val_1 % mod1)
            self.elm_2.append(val_2 % mod2)
    
    def get(self, l, r):
        val_1 = (self.elm_1[r] - self.elm_1[l]) * self.inv1_table[l] % mod1
        val_2 = (self.elm_2[r] - self.elm_2[l]) * self.inv2_table[l] % mod2
        return val_1, val_2


def check(s, val):
    que = deque()
    se = set()
    for i in range(s.len - val + 1):
        res = s.get(i, i + val)
        if res in se:
            return True
        que.append(res)
        if len(que) == val:
            se.add(que.popleft())
    
    return False


def main():
    n = int(input())
    s = input()
    rh = RollingHash(s)
    
    
    ok = 0
    ng = n
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if check(rh, mid):
            ok = mid
        else:
            ng = mid
    
    print(ok)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

N = int(sys.stdin.readline())
S = sys.stdin.readline().strip()

ans = 0
for L in range(1, N):
	dp = [0]*N 
	for x in range(N - L):
		if S[x] == S[x+L]:
			if x==0: dp[x] += 1
			else: dp[x] = min(dp[x-1]+1, L)
			ans = max(ans, dp[x])
print(ans)

Solution (Python):
def z_alg(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):
    data = z_alg(s[i:])
    for j,x in enumerate(data[1:]):
        ans = max(ans,min(x,j+1))

print(ans)

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

l1 = l2 = length = 0

while l2 + length < n:
    
    
    if s[l1:l2] in s[l2:]:
        length = l2 - l1
        l2 += 1 
    else:
        l1 += 1
        l2 = l1 + length + 1
print(length)

Solution (Python):
def main():
    N = int(input())
    S = input()
    ans = 0
    index = 0

    for i in range(N):
        s1 = S[index:i+1]
        s2 = S[i+1:]
        if s1 in s2:
            ans = len(s1)
        else:
            index += 1

    print(ans)

if __name__ == '__main__':
    main()

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

r = 0
answer = 0

for l in range(N):
  while True:
    if S.rfind(S[l:r+1]) >= r+1:
      r += 1
      answer = max(answer, r-l)
    else:
      break
  
print(answer)

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

max_cnt = 0
for i in range(1, n):
    cnt = 0
    for j in range(n - i):
        if ss[j] == ss[j + i]:
            cnt += 1
            max_cnt = max(cnt, max_cnt)
            if cnt == i:
                break
        else:
            cnt = 0

print(max_cnt)

Solution (Python):

N = int(input())
S = input()
ans = 0

for L in range(1,N): 
    dp = [0] * (N+5)
    for x in range(N-L): 
        if S[x] == S[x+L]:
            if x == 0:
                dp[x] += 1
            else:
                dp[x] = min(dp[x-1]+1,L)
            ans = max(ans,dp[x])
        else:
            dp[x] = 0
            
print(ans)

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

l1 = l2 = length = 0

while l2 + length < N:
    if S[l1:l2] in S[l2:]:
        length = l2 - l1
        l2 += 1
    else:
        l1 += 1
        l2 = l1 + length + 1
        
print(length)