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
from io import StringIO
import unittest
import os
import random


sys.setrecursionlimit(999999999)


class RollingHash:
    
    BASE1 = 1007
    BASE2 = 2009
    MOD1 = 1000000007
    MOD2 = 1000000009

    def __init__(self, s: str):
        """
        コンストラクタ
        :s 検索の実施対象となる文字列
        """
        self.n = len(s)
        self.hash1 = [0] * (self.n + 1)
        self.hash2 = [0] * (self.n + 1)
        self.power1 = [1] * (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.hash2[i + 1] = (self.hash2[i] * self.__class__.BASE2 + ord(e)) % self.__class__.MOD2
            self.power1[i + 1] = (self.power1[i] * self.__class__.BASE1) % self.__class__.MOD1
            self.power2[i + 1] = (self.power2[i] * self.__class__.BASE2) % self.__class__.MOD2

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

    def __func(self, mid, can_duplicate: bool) -> bool:
        """
        2分探索の内部処理(クラスメソッド)
        """
        dic1 = dict()
        
        for i in range(self.n - mid + 1):
            
            res = self.get(i, i + mid)
            
            if res in dic1:
                
                if can_duplicate or i - dic1[res] >= mid:
                    return True
                
                else:
                    continue
            
            dic1[res] = i
        return False

    def binary_search(self, can_duplicate: bool) -> int:
        """
        2分探索にて、自分の文字列内のLCPを求める例：文字が「ABCABCABCCCC」なら3(ABC)を返す
        :canDuplicate 文字列が重なることを許容するか(部分重複を許容するか)
        """
        ok = 0
        ng = self.n // 2 + 1
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            if self.__func(mid, can_duplicate):
                ok = mid
            else:
                ng = mid
        return ok



def resolve(test_def_name=""):
    n = int(input())
    s = input()
    rh = RollingHash(s)
    print(rh.binary_search(False))


class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """5
ababa"""
        output = """2"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """2
xy"""
        output = """0"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """13
strangeorange"""
        output = """5"""
        self.assertIO(test_input, output)

    
    def test_1original_1(self):
        test_input = """100
aaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaab"""
        output = """50"""
        self.assertIO(test_input, output)
        test_input = """10000
aaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaab"""
        output = """5000"""
        self.assertIO(test_input, output)



if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        
        resolve()

    else:
        
        unittest.main()

Solution (Python):
from itertools import accumulate
max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

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

res = 0
for i in range(1,N):
    m = 0
    r = 0
    for a,b in zip(S,S[i:]):
        if a == b:
            r += 1
        else:
            r = 0
        m = max2(m,r)
    m = min2(m,i)
    res = max2(res, m)

print(res)

Solution (Python):
n = int(input())
s = list(input())
b = 27
mod = 67280421310721
m = n // 2
x = [1] * (m + 1)
for i in range(1, m + 1):
    x[i] = (x[i - 1] * b) % mod
h0 = [0] * m
h0[0] = ord(s[0]) - 96
d = [{} for _ in range(m + 1)]
for i in range(1, m):
    h0[i] = (h0[i - 1] * b + (ord(s[i]) - 96)) % mod
for i in range(m, 0, -1):
    h = h0[i - 1]
    d[i][h] = 0
    for j in range(i, n):
        h *= b
        h %= mod
        h -= (x[i] * (ord(s[j - i]) - 96) % mod)
        h += (ord(s[j]) - 96)
        h %= mod
        if h in d[i]:
            if (j - i + 1 - d[i][h]) >= i:
                print(i)
                exit()
        else:
            d[i][h] = j - i + 1
print(0)

Solution (Python):
n,s = int(input()), list(input())
def z_algo(s):
    n = len(s)
    a = [0]*n
    i,j,l = 1,0,n
    a[0] = n
    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

ans = 0
for i in range(n-1):
    a = z_algo(s[i:])
    len_a = len(a)
    for j in range(len_a):
        ans = max(ans, min(j,a[j]))
print(ans)

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




ans = 0
l,r = 0,1
while l<N and r<N:
  findf = False
  target = S[l:r]
  L = r-l
  for k in range(l+L,N-1):
    compare = S[k:k+L]
    
    if target == S[k:k+L]:
      ans = max(ans,L)
      findf = True
      break
  if findf and r < N-1:
    r += 1
  else:
    l += 1
    r = min(r+1,N-1)
    
print(ans)

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

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

        if s[i] == s[j]:
            dp[i][j] = dp[i+1][j+1] + 1        

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

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()


def is_ok(arg, S):
    
    dic = {}
    ans = False
    for i in range(len(S)-arg+1):
        c = S[i:i+arg]
        if c in dic:
            if i-dic[c] >= arg:
                ans = True
                break
        else:
            dic[c] = i
    return ans


def meguru_bisect(ng, ok, S):
    '''
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng ok は  とり得る最小の値-1 とり得る最大の値+1
    最大最小が逆の場合はよしなにひっくり返す
    '''
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid, S):
            ok = mid
        else:
            ng = mid
    return ok


def main():
    N = int(input())
    S = input()
    print(meguru_bisect((N//2)+1, -1, S))


if __name__ == '__main__':
    main()

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

l = 0 
r = N 
while l + 1 < r:
  x = (l + r) // 2
  first_loc = {}
  possible = False
  for i in range(N-x+1):
    
    sub = S[i:i+x]
    
    if sub in first_loc:
      if first_loc[sub] <= i - x:
        
        possible = True
        break
    else:
      first_loc[sub] = i
  if possible:
    l = x
  else:
    r = x
print(l)

Solution (Python):
class DisjointSparseTable:
    def __init__(self, a, op=lambda a, b: max(a, b), e=0):
        
        self.op = op
        
        self.e = e
        self.n = len(a)
        self.level = (self.n - 1).bit_length()
        self.size = 2 ** self.level
        self.table = [[self.e] * self.size for _ in range(self.level)]
        
        for i, item in enumerate(a):
            self.table[-1][i] = item
        self.build()

    def build(self):
        for i in range(1, self.level):
            step = 2 ** i
            lv = self.level - 1 - i
            for mid in range(step, self.n + step, step * 2):
                
                val = self.e
                for j in range(step):
                    val = self.op(val, self.table[-1][mid + j])
                    self.table[lv][mid + j] = val
                
                val = self.e
                for j in range(step):
                    val = self.op(self.table[-1][mid - 1 - j], val)
                    self.table[lv][mid - 1 - j] = val

    
    def fold(self, l, r):
        if l == r:
            return self.e
        elif l == r - 1:
            return self.table[-1][l]
        lv = self.level - (l ^ r - 1).bit_length()
        return self.op(self.table[lv][l], self.table[lv][r - 1])


class SuffixArray:
    def __init__(self, S):
        ord_base = ord("a") - 1
        a = [ord(ch) - ord_base for ch in S]
        self.a = a + [0]
        self.k = max(self.a) + 1
        self.n = len(self.a)
        self.sa = self.SA_IS(self.a, self.n, self.k)
        
        self.rank = [0] * self.n
        for i, item in enumerate(self.sa):
            self.rank[item] = i
        self.lcp = self.build_LCP(self.a, self.sa, self.rank)
        self.lcp_dst = DisjointSparseTable(self.lcp, op=lambda a, b: min(a, b), e=10 ** 9)

    
    def get_buckets(self, a, k, end=True):
        bucket = [0] * k
        for item in a:
            bucket[item] += 1
        sumation = 0
        for i in range(k):
            sumation += bucket[i]
            if end:
                bucket[i] = sumation
            else:
                bucket[i] = sumation - bucket[i]
        return bucket

    def induce_SAl(self, a, sa, n, k, lstype):
        bucket = self.get_buckets(a, k, end=False)
        for i in range(n):
            j = sa[i] - 1
            if j >= 0 and (not lstype & (1 << j + 1)):
                sa[bucket[a[j]]] = j
                bucket[a[j]] += 1

    def induce_SAs(self, a, sa, n, k, lstype):
        bucket = self.get_buckets(a, k, end=True)
        for i in range(n - 1, -1, -1):
            j = sa[i] - 1
            if j >= 0 and lstype & (1 << j + 1):
                bucket[a[j]] -= 1
                sa[bucket[a[j]]] = j

    def is_LMS(self, index, lstype):
        return lstype >> (index + 1) & 1 and not (lstype >> index & 1)

    def is_stype(self, index, lstype):
        return lstype >> (index + 1) & 1

    def SA_IS(self, a, n, k):
        
        
        lstype = 1
        prev_type = 0
        prev_item = self.k
        for i, item in enumerate(a[::-1]):
            shift = n - i
            if item == prev_item:
                lstype |= prev_type << shift
            elif item < prev_item:
                lstype |= 1 << shift
                prev_type = 1
            else:
                prev_type = 0
            prev_item = item
        
        bucket = self.get_buckets(a, k)
        
        sa = [-1] * n
        for i in range(n - 1, 0, -1):
            if self.is_LMS(i, lstype):
                bucket[a[i]] -= 1
                sa[bucket[a[i]]] = i
        self.induce_SAl(a, sa, n, k, lstype)
        self.induce_SAs(a, sa, n, k, lstype)

        lcm_cnt = 0
        for i in range(n):
            if self.is_LMS(sa[i], lstype):
                sa[lcm_cnt] = sa[i]
                lcm_cnt += 1
        for i in range(lcm_cnt, n):
            sa[i] = -1

        
        name = 1;
        prev = sa[0]
        sa[lcm_cnt + sa[0] // 2] = 0
        for pos in sa[1: lcm_cnt]:
            diff = False
            for d in range(n):
                if a[pos + d] != a[prev + d] or (self.is_stype(pos + d, lstype) != self.is_stype(prev + d, lstype)):
                    diff = True
                    break
                elif d > 0 and (self.is_LMS(pos + d, lstype) or self.is_LMS(prev + d, lstype)):
                    break
            if diff:
                name += 1;
                prev = pos
            pos //= 2
            sa[lcm_cnt + pos] = name - 1
        sub_a = []
        for i in range(lcm_cnt, n):
            if sa[i] >= 0:
                sub_a.append(sa[i])

        
        if name < lcm_cnt:
            sub_sa = self.SA_IS(sub_a, len(sub_a), name + 1)
        else:
            sub_sa = sa[:lcm_cnt]
            for i in range(lcm_cnt):
                sub_sa[sub_a[i]] = i
        bucket = self.get_buckets(a, k, end=True)
        j = 0
        for i in range(1, n):
            if self.is_LMS(i, lstype):
                sub_a[j] = i
                j += 1
        
        for i in range(lcm_cnt):
            sa[i] = sub_a[sub_sa[i]]
        for i in range(lcm_cnt, n):
            sa[i] = -1
        for i in range(lcm_cnt - 1, -1, -1):
            j = sa[i];
            sa[i] = -1
            bucket[a[j]] -= 1
            sa[bucket[a[j]]] = j

        
        self.induce_SAl(a, sa, n, k, lstype)
        self.induce_SAs(a, sa, n, k, lstype)
        return sa

    def build_LCP(self, a, sa, rank):
        
        sa.append(-1)
        lcp = [0] * len(a)
        same_cnt = 0
        for index1 in range(len(a)):
            if same_cnt != 0:
                same_cnt -= 1
            index2 = sa[rank[index1] + 1]
            while a[index1 + same_cnt] == a[index2 + same_cnt]:
                same_cnt += 1
            lcp[rank[index1]] = same_cnt
        
        sa.pop()
        return lcp

    def get_lcp(self, l, r):
        rank_l = self.rank[l]
        rank_r = self.rank[r]
        if rank_l > rank_r:
            rank_l, rank_r = rank_r, rank_l
        return self.lcp_dst.fold(rank_l, rank_r)

    def search(self, b):
        m = len(b)
        l = 0;
        r = self.n + 1
        matched = 0
        while r - l > 1:
            mid = (l + r) // 2
            lm_lcp = self.get_lcp(l, mid)
            if matched < lm_lcp:
                l = mid
            elif matched > lm_lcp:
                r = mid
            else:
                a_itr = self.sa[mid] + matched;
                b_itr = matched
                diff = 0
                while b_itr < m and a_itr < self.n:
                    if b[b_itr] != self.a[a_itr]:
                        diff = b[b_itr] - self.a[a_itr]
                        break
                    a_itr += 1;
                    b_itr += 1
                if diff >= 0:
                    l = mid
                    matched = b_itr
                else:
                    r = mid
        return matched, l

def max2(x,y):
    return x if x > y else y

def min2(x,y):
    return x if x < y else y

res = 0
N = int(input())
S = input()
SA = SuffixArray(S)
for i in range(N + 1):
    for j in range(i + 1, N + 1):
        lcp = SA.get_lcp(i, j)
        temp = min2(lcp, j-i)
        res = max2(res, temp)
print(res)

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

def max2(x,y):
    return x if x > y else y

def min2(x,y):
    return x if x < y else y

res = 0
N = int(input())
S = input()
for i in range(N):
    lcp = Z_algo(S[i:])
    for j, s in enumerate(lcp):
        temp = min2(s, j)
        res = max2(res, temp)
print(res)

Solution (Python):
def z_al(s):
    le = len(s)
    res = [0 for i in range(le)]
    i, j = 1, 0
    while i < le:
        while i + j < le and s[i + j] == s[j]:
            j += 1
        res[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < le and res[k] + k < j:
            res[i + k] = res[k]
            k += 1
        i += k
        j -= k
    return res
n = int(input())
s = input()
ans = 0
for i in range(n):
    s2 = s[i:]
    res = z_al(s2)
    for j in range(len(s2)):
        ans = max(ans, min(res[j], j))
print(ans)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

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

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

print(ans)

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

lb=0
rb=N+1
while rb-lb>1:
    mid = (lb + rb) // 2
    x = 0
    for i, s in enumerate(S[:mid]):
        x += pow(26, i) * (ord(s) - ord('a'))
    m = pow(26, mid - 1)
    a = [x]
    for i, s in enumerate(S[mid:]):
        x -= ord(S[i]) - ord('a')
        x //= 26
        x += m * (ord(s) - ord('a'))
        a += [x]
    f = 0
    se = set([])
    for i, x in enumerate(a):
        if i >= mid:
            se.add(a[i - mid])
        if x in se:
            f = 1
            break
    if f:
        lb=mid
    else:
        rb=mid
print(lb)

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

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

Solution (Python):
import sys
import numpy as np
from numba import njit

def main(N, S):
    dp = np.zeros((N + 1, N + 1), dtype=np.int64)
    ans = 0
    for i in range(N - 1):
        for j in range(i + 1, N):
            dp[i,j] = min(j - i, dp[i - 1,j - 1] + 1) if S[i] == S[j] else 0
        ans = max(ans, np.max(dp[i]))
    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', 'i8(i8,i8[:])')(main)
    
    cc.compile()
else:
    from my_module import main
    N = int(input())
    S = np.array([ord(_) for _ in input()])
    print(main(N, S))

Solution (Python):
import sys
import numpy as np
from numba import njit

def main(N, S, dp):
    ans = 0
    for i in range(N - 1):
        for j in range(i + 1, N):
            dp[i,j] = min(j - i, dp[i - 1,j - 1] + 1) if S[i] == S[j] else 0
        ans = max(ans, np.max(dp[i]))
    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', 'i8(i8,i8[:],i8[:,:])')(main)
    
    cc.compile()
else:
    from my_module import main
    N = int(input())
    S = np.array([ord(_) for _ in input()])
    dp = np.zeros((N + 1, N + 1), dtype=int)
    print(main(N, S, dp))