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-----
5
ababa

-----Sample Output-----
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.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
s = input()
j = 1
result = []
for i in range(n):
    while (j < n-1) and (s[i:j] in s[j:]):
        j += 1
    result.append(j-i-1)
print(max(result))

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    s = input().rstrip()
    l, r = 0, 0
    res = 0
    while r < n:
        r += 1
        if not s[l:r] in s[r:]:
            l += 1
            res = max(res, r-l)
    print(res)

def __starting_point():
    main()
__starting_point()

from collections import defaultdict as dd
N = int(input())
s = str(input())
maxlen = N//2

def solve(tgt):
    dic = dd(int)
    st = s[tgt:2*tgt]
    dic[st] += 1
    ls = [st]
    for char in s[2*tgt:]:
        st = st[1:]+char
        dic[st] += 1
        ls.append(st)
    st = s[:tgt]
    if dic[st] > 0:
        return True
    dic[ls[0]] -= 1
    for i,char in enumerate(s[tgt:N-tgt]):
        st = st[1:]+char
        if dic[st] > 0:
            return True
        dic[ls[i+1]] -= 1
    return False

ng = maxlen + 1
ok = 0
while ng-ok > 1:
    tgt = (ok+ng)//2
    if solve(tgt):
        ok = tgt
    else:
        ng = tgt
print(ok)


n=int(input())
s=input()
l=0
r=n
while r-l!=1:
  mid=(r+l)//2
  dic={}
  flag=False
  for i in range(n-mid+1):
    tmp=s[i:i+mid]
    if tmp not in dic:
      dic[tmp]=i+mid
    else:
      if dic[tmp]<=i:
        flag=True
        break
  if flag==True:
    l=mid
  else:
    r=mid
print(l)

n = int(input())
s = input()
ret = 0
for l in range(n):
  while s[l:l+ret+1] in s[l+ret+1:]:
    ret += 1
print(ret)

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

def f(m):
    se = set()
    arr = [None]*N
    for i in range(0,N-m+1):
        if i >= m:
            se.add(arr[i-m])
        arr[i] = S[i:i+m]
        if arr[i] in se:
            return True
    return False

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


from typing import List, Tuple


class RollingHash:
    """Rolling Hash"""

    __slots__ = ["_base", "_mod", "_hash", "_power"]

    def __init__(self, source: str, base: int = 1007, mod: int = 10 ** 9 + 7):
        self._base = base
        self._mod = mod
        self._hash, self._power = self._build(source)

    def _build(self, source: str) -> Tuple[List[int], List[int]]:
        """Compute "hash" and "mod of power of base" of interval [0, right)."""
        length = len(source)
        hash_, power = [0] * (length + 1), [0] * (length + 1)
        power[0] = 1
        for i, c in enumerate(source, 1):
            hash_[i] = (hash_[i - 1] * self._base + ord(c)) % self._mod
            power[i] = power[i - 1] * self._base % self._mod
        return hash_, power

    def get_hash(self, left: int, right: int):
        """Return hash of interval [left, right)."""
        return (
            self._hash[right] - self._hash[left] * self._power[right - left]
        ) % self._mod


def abc141_e():
    # https://atcoder.jp/contests/abc141/tasks/abc141_e
    N = int(input())
    S = input().rstrip()

    rh = RollingHash(S)
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        flg = False
        memo = 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 = True
                break
        if flg:
            ok = mid  # next mid will be longer
        else:
            ng = mid  # next mid will be shorter

    print(ok)  # max length of substrings appeared twice or more


def __starting_point():
    abc141_e()

__starting_point()

import random
from collections import defaultdict


class RollingHash():

    def __init__(self, S, b=3491, m=999999937):
        """任意の基数と法でハッシュを生成する"""
        n = len(S)
        self.prefix = prefix = [0] * (n+1)
        self.power = power = [1] * (n+1)
        self.b = b
        self.m = m
        for i in range(n):
            c = ord(S[i])
            prefix[i+1] = (prefix[i] * b + c) % m
            power[i+1] = (power[i] * b) % m
    
    def get(self, l, r):
        """S[l, r) のハッシュを求める"""
        return (self.prefix[r] - self.power[r-l] * self.prefix[l]) % self.m
    
    def concat(self, h1, h2, l2):
        """S1+S2 のハッシュを、それぞれのハッシュから求める"""
        return (self.power[l2] * h1 + h2) % self.m
    
    def lcp(self, l1, r1, l2, r2):
        """S[l1, r1) とS[l2, r2) の最大共通接頭辞を求める"""
        low = 0
        high = min(r1-l1, r2-l2) + 1
        while high - low > 1:
            mid = (high + low) // 2
            if self.get(l1, l1 + mid) == self.get(l2, l2 + mid):
                low = mid
            else:
                high = mid
        return low


def read():
    N = int(input().strip())
    S = input().strip()
    return N, S


def solve(N, S):
    ans = []
    for m in [999999937, 10**9+7]:
        b = random.randint(10000, m-1)
        rh = RollingHash(S, b=b, m=m)
        low = 0
        high = (N+1) // 2 + 1
        dmax = defaultdict(int)
        dmin = defaultdict(int)
        while high - low > 1:
            dmax.clear()
            dmin.clear()
            mid = (high + low) // 2
            for i in range(0, N-mid+1):
                h = rh.get(i, i+mid)
                dmax[h] = max(dmax[h], i+1)
                dmin[h] = max(dmin[h], N+1-i)
            is_match = False
            for h in dmax.keys():
                if dmax[h] - (N+2 - dmin[h]) >= mid:
                    is_match = True
                    break
            if is_match:
                low = mid
            else:
                high = mid
        ans.append(low)
    return min(ans)


def __starting_point():
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))
__starting_point()

from collections import defaultdict

class RollingHash(object):
    def __init__(self, S: str, MOD: int = 10 ** 9 + 7, BASE: int = 10 ** 5 + 7):
        self.S = S
        self.N = N = len(S)
        self.MOD = MOD
        self.BASE = BASE
        self.S_arr = [ord(x) for x in S]

        self.POWER = [1] * (N + 1)
        self.HASH  = [0] * (N + 1)
        p, h = 1, 0
        for i in range(N):
            self.POWER[i + 1] = p = (p * BASE) % MOD
            self.HASH[i + 1] = h = (h * BASE + self.S_arr[i]) % MOD

    def hash(self, l: int, r: int):
        # get hash for S[l:r]
        _hash = (self.HASH[r] - self.HASH[l] * self.POWER[r - l]) % self.MOD
        return _hash

def main():
    N = int(input())
    S = input()
    MOD = 998244353
    rs = RollingHash(S, MOD=MOD, BASE=37)
    h, p = rs.HASH, rs.POWER

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

    while abs(right - left) > 1:
        mid = (left + right) // 2
        ok = False
        hash_to_left = defaultdict(list)
        L = mid
        for i in range(N - L + 1):
            _hash = (h[i+L] - h[i] * p[L]) % MOD
            # hashが衝突しても文字列が完全に一致するか分からないので、
            # 衝突した場合は文字列が完全に一致するか調べ、かつ
            # 文字列同士がSの中で重なるような範囲にない場合はOKとする
            for j in hash_to_left[_hash]:
                if j+L <= i and S[i:i+L] == S[j:j+L]:
                    ok = True
                    break
            if ok:
                break
            hash_to_left[_hash].append(i)

    
        if ok:
            left = mid
        else:
            right = mid

    print(left)
    # # 長さLの部分文字列同士が、範囲を重ねず同じ文字列となる場合はTrue,
    # # そうでない場合はFalseを返す関数
    # def isOK(L):
    #     if L == 0:
    #         return True
    #     hash_to_left = defaultdict(list)
    #     for i in range(N - L + 1):
    #         _hash = rs.hash(i, i + L)
    #         # hashが衝突しても文字列が完全に一致するか分からないので、
    #         # 衝突した場合は文字列が完全に一致するか調べ、かつ
    #         # 文字列同士がSの中で重なるような範囲にない場合はOKとする
    #         for j in hash_to_left[_hash]:
    #             if j+L <= i and S[i:i+L] == S[j:j+L]:
    #                 return True
    #         hash_to_left[_hash].append(i)

    #     return False
    # # 範囲が重ならないことが条件にあるので、答えは最大でもN // 2（文字列の長さの半分）となる。
    # # ただし、二分探索する上で絶対に答えとならない範囲を含めたいので、
    # # 探索範囲としてはN // 2 + 1 と、+1しておく。
    # ans = binary_search(0, N // 2 + 1, isOK, search_max=True)
    # print(ans)

def __starting_point():
    main()
__starting_point()

from collections import defaultdict

class RollingHash(object):
    def __init__(self, S: str, MOD: int = 10 ** 9 + 7, BASE: int = 10 ** 5 + 7):
        self.S = S
        self.N = N = len(S)
        self.MOD = MOD
        self.BASE = BASE
        self.S_arr = [ord(x) for x in S]

        self.POWER = [1] * (N + 1)
        self.HASH  = [0] * (N + 1)
        p, h = 1, 0
        for i in range(N):
            self.POWER[i + 1] = p = (p * BASE) % MOD
            self.HASH[i + 1] = h = (h * BASE + self.S_arr[i]) % MOD

    def hash(self, l: int, r: int):
        # get hash for S[l:r]
        _hash = (self.HASH[r] - self.HASH[l] * self.POWER[r - l]) % self.MOD
        # if _hash < 0:
        #     _hash += self.MOD
        return _hash

# 汎用的な二分探索のテンプレ
# check_func(x) = true となるxの最小値を探索する
# left : check_func(x) = falseとなるx
# right: check_func(x) = true となるx
# search_max: check_func(x) = true となるxの"最大値"を探索する場合はTrue
# check_func: answer <= x であればcheck_func(x) = true となるような関数
def binary_search(left: int, right: int, check_func, search_max:bool=False):
    # ok と ng のどちらが大きいかわからないことを考慮
    while abs(right - left) > 1:
        mid = (left + right) // 2
    
        if check_func(mid) ^ search_max:
            right = mid
            # print(left, right, mid, 't')
        else:
            left = mid
            # print(left, right, mid, 'f')

    return left if search_max else right

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

    rs = RollingHash(S, MOD=998244353, BASE=37)

    # 長さLの部分文字列同士が、範囲を重ねず同じ文字列となる場合はTrue,
    # そうでない場合はFalseを返す関数
    def isOK(L):
        if L == 0:
            return True
        hash_to_left = defaultdict(list)
        for i in range(N - L + 1):
            _hash = rs.hash(i, i + L)
            # hashが衝突しても文字列が完全に一致するか分からないので、
            # 衝突した場合は文字列が完全に一致するか調べ、かつ
            # 文字列同士がSの中で重なるような範囲にない場合はOKとする
            for j in hash_to_left[_hash]:
                if j+L <= i:
                    return True
            hash_to_left[_hash].append(i)

        return False
    # 範囲が重ならないことが条件にあるので、答えは最大でもN // 2（文字列の長さの半分）となる。
    # ただし、二分探索する上で絶対に答えとならない範囲を含めたいので、
    # 探索範囲としてはN // 2 + 1 と、+1しておく。
    ans = binary_search(0, N // 2 + 1, isOK, search_max=True)
    print(ans)

def __starting_point():
    main()
__starting_point()




"""
N <= 5 * 10**3　なので、２重ループぐらいなら間に合うか？

例３
strangeorange
**range*range

他に２回以上出てくるものとして
r,a, みたいな単体
ra, nge みたいな最長の部分文字列の一部
みたいな感じなので
l,r (r=l+1~N-1)を持っておいて、S[l:r+1] = S[r+1:XX]になるものがあればさらに右をみて～みたいな？

"""


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


l = 0
r = 1
ans = 0
while True:
    if l == N-1:
        break
    while S[l:r] in S[r:]:
        r += 1

    ans = max(ans, r - l - 1)
    #print(l,r, S[l:r], S[r:], ans)
    l += 1
    if l == r:
        r = l + 1

print(ans)




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)


import numpy as np

n = int(input())
s = np.array(list(input()))

l = s.size

dp = np.zeros(l, dtype=np.int16)
ans = 0
for i, e in enumerate(s, 1):
    dp_prev = dp[:]
    mx = np.arange(1, l + 1) - i
    idx = np.hstack([np.full(i, False), s[i:] == e]).astype(np.bool)
    idx_prev = np.hstack([np.full(i-1, False), s[i:] == e, False]).astype(np.bool)
    dp = np.zeros(l, dtype=np.int16)
    dp[idx] = np.minimum(dp_prev[idx_prev] + 1, mx[idx])
    ans = max(ans, dp.max())

print(ans)


n=int(input())
s=input()
l=0
r=n
while r-l!=1:
  mid=(r+l)//2
  dic={}
  flag=False
  for i in range(n-mid+1):
    tmp=s[i:i+mid]
    if tmp not in dic:
      dic[tmp]=i+mid
    else:
      if dic[tmp]<=i:
        flag=True
        break
  if flag==True:
    l=mid
  else:
    r=mid
print(l)

class RollingHash(object):
    def __init__(self, S, base, mod):
        self.mod = mod
        l = len(S)

        self.hash_lst = [0] * (l + 1)
        self.pow_lst = [1] * (l + 1)

        for i in range(l):
            self.hash_lst[i + 1] = (self.hash_lst[i] * base + ord(S[i])) % mod
            self.pow_lst[i + 1] = (self.pow_lst[i] * base) % mod

    def get_hash(self, left, right):
        return (self.hash_lst[right] - self.hash_lst[left] * self.pow_lst[right - left] % self.mod) % self.mod


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

base = 1007
mod = pow(10, 9) + 7
rh = RollingHash(S, base, mod)

left = 0
right = N // 2

while left <= right:
    mid = (left + right) // 2

    found_hash = {}
    found = False
    for i in range(N - mid + 1):
        h = rh.get_hash(i, i + mid)

        if h not in found_hash:
            found_hash[h] = i
        else:
            if found_hash[h] <= i - mid:
                found = True
                break

    if found:
        left = mid + 1
    else:
        right = mid - 1


print(right)


from collections import defaultdict

class RollingHash(object):
    def __init__(self, S: str, MOD: int = 10 ** 9 + 7, BASE: int = 10 ** 5 + 7):
        self.S = S
        self.N = N = len(S)
        self.MOD = MOD
        self.BASE = BASE
        
        S_arr = [ord(x) for x in S]
        POWER = [1] * (N + 1)
        HASH  = [0] * (N + 1)
        p, h = 1, 0
        for i in range(N):
            POWER[i + 1] = p = (p * BASE) % MOD
            HASH[i + 1] = h = (h * BASE + S_arr[i]) % MOD
        self.S_arr = S_arr
        self.POWER = POWER
        self.HASH = HASH

    def hash(self, l: int, r: int):
        # get hash for S[l:r]
        _hash = (self.HASH[r] - self.HASH[l] * self.POWER[r - l]) % self.MOD
        return _hash

def main():
    N = int(input())
    S = input()
    MOD = 998244353
    rs = RollingHash(S, MOD=MOD, BASE=37)
    h, p = rs.HASH, rs.POWER

    left, right = 0, N // 2 + 1
    D = [0] * N
    while abs(right - left) > 1:
        mid = (left + right) // 2
        # hash_to_left = defaultdict(list)
        hashes = set()
        L = mid
        P = p[L]
        for i in range(min(L, N-2*L+1)):
            D[i] = (h[L+i] - h[i]*P) % MOD
        hashes = set()
        ok = False
        for i in range(L, N-L+1):
            hashes.add(D[i-L])
            D[i] = v = (h[L+i] - h[i]*P) % MOD
            if v in hashes:
                ok = True
                break
        if ok:
            left = mid
        else:
            right = mid

    print(left)

def __starting_point():
    main()
__starting_point()

def ok(l):
    # 長さlの連続部分列で重ならずに2回以上現れるものがある
    D = {}
    for i in range(n-l+1):
        try:
            if D[S[i:i+l]]+l <= i:
                return True
        except:
            D[S[i:i+l]] = i
    return False


n = int(input())
S = input()
# 二分探索でTrueになる最大のkを求める
l, r = 0, n+1
while r-l > 1:
    c = (l+r)//2
    if ok(c):
        l = c
    else:
        r = c
print(l)


import random

class RollingHash(object):
    def __init__(self, S: str, MOD: int = 10 ** 9 + 7, BASE: int = 10 ** 5 + 7):
        self.S = S
        self.N = N = len(S)
        self.MOD = MOD
        self.BASE = BASE
        self.S_arr = [ord(x) for x in S]

        self.POWER = [1] * (N + 1)
        self.HASH  = [0] * (N + 1)
        p, h = 1, 0
        for i in range(N):
            self.POWER[i + 1] = p = (p * BASE) % MOD
            self.HASH[i + 1] = h = (h * BASE + self.S_arr[i]) % MOD

    def hash(self, l: int, r: int):
        # get hash for S[l:r]
        _hash = (self.HASH[r] - self.HASH[l] * self.POWER[r - l]) % self.MOD
        return _hash

# 汎用的な二分探索のテンプレ
# check_func(x) = true となるxの最小値を探索する
# left : check_func(x) = falseとなるx
# right: check_func(x) = true となるx
# search_max: check_func(x) = true となるxの"最大値"を探索する場合はTrue
# check_func: answer <= x であればcheck_func(x) = true となるような関数
def binary_search(left: int, right: int, check_func, search_max:bool=False):
    # ok と ng のどちらが大きいかわからないことを考慮
    while abs(right - left) > 1:
        mid = (left + right) // 2
    
        if check_func(mid) ^ search_max:
            right = mid
            # print(left, right, mid, 't')
        else:
            left = mid
            # print(left, right, mid, 'f')

    return left if search_max else right

def main():
    N = int(input())
    S = input()
    MOD = 998244353
    BASE = 37 # random.randint(2, MOD-1)
    rs = RollingHash(S, MOD=MOD, BASE=BASE)

    D = [0] * N
    # 長さLの部分文字列同士が、範囲を重ねず同じ文字列となる場合はTrue,
    # そうでない場合はFalseを返す関数
    def isOK(L):
        if L == 0:
            return True
        
        for i in range(min(L, N - 2 * L + 1)):
            D[i] = rs.hash(i, i + L)
        hashes = set()
        for i in range(L, N - L + 1):
            # 自分より開始点がL以上前の文字列のハッシュを検索対象に追加
            hashes.add(D[i - L])
            D[i] = v = rs.hash(i, i + L)
            # ハッシュが衝突したら、範囲を重ねず同じ文字列となる文字列が存在することになる
            if v in hashes:
                return True
        return False

    # 範囲が重ならないことが条件にあるので、答えは最大でもN // 2（文字列の長さの半分）となる。
    # ただし、二分探索する上で絶対に答えとならない範囲を含めたいので、
    # 探索範囲としてはN // 2 + 1 と、+1しておく。
    ans = binary_search(0, N // 2 + 1, isOK, search_max=True)
    print(ans)

def __starting_point():
    main()
__starting_point()

#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)

class DoubleRollingHash:
    def __init__(self, seq, f=ord):
        self.n = len(seq)
        self.base1, self.base2 = 1007, 2009
        self.mod1, self.mod2 = 1000000007, 1000000009
        self.f = f # set numerizing function

        self.hash1, self.hash2 = [0]*(self.n+1), [0]*(self.n+1)
        self.power1, self.power2 = [1]*(self.n+1), [1]*(self.n+1)

        for i, e in enumerate(seq):
            self.hash1[i+1] = (self.hash1[i] * self.base1 + self.f(e)) % self.mod1
            self.hash2[i+1] = (self.hash2[i] * self.base2 + self.f(e)) % self.mod2
            self.power1[i+1] = (self.power1[i] * self.base1) % self.mod1
            self.power2[i+1] = (self.power2[i] * self.base2) % self.mod2

    # get hash value of seq[left:right]
    def get(self, l, r):
        v1 = (self.hash1[r] - self.hash1[l] * self.power1[r-l]) % self.mod1
        v2 = (self.hash2[r] - self.hash2[l] * self.power2[r-l]) % self.mod2
        return v1, v2

    # get lcp of seq[a:] and seq[b:]
    def getLCP(self, a, b):
        l = self.n - max(a, b) + 1
        left, right = 0, l
        while right - left > 1:
            mid = (left + right) // 2
            if self.get(a, a+mid) == self.get(b, b+mid): left = mid
            else: right = mid
        return left

class RollingHash:
    def __init__(self, seq, f=ord):
        self.n = len(seq)
        self.base, self.mod = 1007, MOD
        self.f = f # set numerizing function
        self.hash, self.power = [0]*(self.n+1), [1]*(self.n+1)
        for i, e in enumerate(seq):
            self.hash[i+1] = (self.hash[i] * self.base + self.f(e)) % self.mod
            self.power[i+1] = (self.power[i] * self.base) % self.mod

    # get hash value of seq[left:right]
    def get(self, l, r): return (self.hash[r] - self.hash[l] * self.power[r-l]) % self.mod

    # get lcp of seq[a:] and seq[b:]
    def getLCP(self, a, b):
        l = self.n - max(a, b) + 1
        left, right = 0, l
        while right - left > 1:
            mid = (left + right) // 2
            if self.get(a, a+mid) == self.get(b, b+mid): left = mid
            else: right = mid
        return left


def main():
    N = I()
    S = SL()

    rh = RollingHash(S)
    ans = 0

    def check(m):
        d = defaultdict(lambda: -1)
        for i in range(N-m+1):
            v = rh.get(i, i+m)
            if d[v] != -1:
                if i >= d[v] + m:
                    return True
            else:
                d[v] = i
        return False

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

    print(left)


def __starting_point():
    main()
__starting_point()

from typing import List


class RollingHash:
    """Rolling Hash"""

    __slots__ = ["_source", "_length", "_base", "_mod", "_hash", "_power"]

    def __init__(self, source: str, base: int = 1007, mod: int = 10 ** 9 + 7):
        self._source = source
        self._length = len(source)
        self._base = base
        self._mod = mod
        self._hash = self._build_hash_from_zero()
        self._power = self._build_base_power()

    def _build_hash_from_zero(self) -> List[int]:
        """Compute hash of interval [0, right)."""
        res = [0] * (self._length + 1)
        for i, c in enumerate(self._source, 1):
            res[i] = (res[i - 1] * self._base + ord(c)) % self._mod
        return res

    def _build_base_power(self) -> List[int]:
        """Compute mod of power of base."""
        res = [1] * (self._length + 1)
        for i in range(1, self._length + 1):
            res[i] = res[i - 1] * self._base % self._mod
        return res

    def get_hash(self, left: int, right: int):
        """Return hash of interval [left, right)."""
        return (
            self._hash[right] - self._hash[left] * self._power[right - left]
        ) % self._mod


def abc141_e():
    # https://atcoder.jp/contests/abc141/tasks/abc141_e
    N = int(input())
    S = input().rstrip()
    rh = RollingHash(S)
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        flg = False
        memo = 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 = True
                break
        if flg:
            ok = mid  # next mid will be longer
        else:
            ng = mid  # next mid will be shorter
    print(ok)  # max length of substrings appeared twice or more


def __starting_point():
    abc141_e()

__starting_point()

import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


class RollingHash:
    def __init__(self, s: str, base=1007, mod=10 ** 9 + 7):
        self.mod = mod
        length = len(s)
        self.pw = [1] * (length + 1)
        self.h = [0] * (length + 1)
        
        v = 0
        for i in range(length):
            self.h[i + 1] = v = (v * base + ord(s[i])) % mod
        v = 1
        for i in range(length):
            self.pw[i + 1] = v = v * base % mod
    
    def query(self, left, right):
        return (self.h[right] - self.h[left] * self.pw[right - left]) % self.mod


def solve():
    N = int(rl())
    S = input()
    
    rh = RollingHash(S)
    
    def check(t):
        dist = dict()
        for i in range(N - t + 1):
            h = rh.query(i, i + t)
            if h in dist:
                if t <= i - dist[h]:
                    return True
            else:
                dist[h] = i
        return False
    
    ok, ng = 0, N // 2 + 1
    while 1 < ng - ok:
        mid = (ok + ng) // 2
        if check(mid):
            ok = mid
        else:
            ng = mid
    print(ok)


def __starting_point():
    solve()

__starting_point()

from typing import List, Tuple


class RollingHash:
    """Rolling Hash"""

    __slots__ = ["_base", "_mod", "_hash", "_power"]

    def __init__(self, source: str, base: int = 1007, mod: int = 10 ** 9 + 7):
        self._base = base
        self._mod = mod
        self._hash, self._power = self._build(source)

    def _build(self, source: str) -> Tuple[List[int], List[int]]:
        """Compute "hash" and "mod of power of base" of interval [0, right)."""
        hash_, power = [0] * (len(source) + 1), [0] * (len(source) + 1)
        power[0] = 1
        for i, c in enumerate(source, 1):
            hash_[i] = (hash_[i - 1] * self._base + ord(c)) % self._mod
            power[i] = power[i - 1] * self._base % self._mod
        return hash_, power

    def get_hash(self, left: int, right: int):
        """Return hash of interval [left, right)."""
        return (
            self._hash[right] - self._hash[left] * self._power[right - left]
        ) % self._mod


def abc141_e():
    # https://atcoder.jp/contests/abc141/tasks/abc141_e
    N = int(input())
    S = input().rstrip()

    rh = RollingHash(S)
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        flg = False
        memo = 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 = True
                break
        if flg:
            ok = mid  # next mid will be longer
        else:
            ng = mid  # next mid will be shorter

    print(ok)  # max length of substrings appeared twice or more


def __starting_point():
    abc141_e()

__starting_point()

from typing import List


class RollingHash:
    """Rolling Hash"""

    __slots__ = ["_source", "_length", "_base", "_mod", "_hash", "_power"]

    def __init__(self, source: str, base: int = 1007, mod: int = 10 ** 9 + 7):
        self._source = source
        self._length = len(source)
        self._base = base
        self._mod = mod
        self._hash = self._build_hash_from_zero()
        self._power = self._build_base_power()

    def _build_hash_from_zero(self) -> List[int]:
        """Compute hash of interval [0, right)."""
        res = [0] * (self._length + 1)
        prev = 0
        for i, c in enumerate(self._source, 1):
            res[i] = (prev * self._base + ord(c)) % self._mod
            prev = res[i]
        return res

    def _build_base_power(self) -> List[int]:
        """Compute mod of power of base."""
        res = [1] * (self._length + 1)
        prev = 1
        for i in range(1, self._length + 1):
            res[i] = prev * self._base % self._mod
            prev = res[i]
        return res

    def get_hash(self, left: int, right: int):
        """Return hash of interval [left, right)."""
        return (
            self._hash[right] - self._hash[left] * self._power[right - left]
        ) % self._mod


def abc141_e():
    # https://atcoder.jp/contests/abc141/tasks/abc141_e
    N = int(input())
    S = input().rstrip()
    rh = RollingHash(S)
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        flg = False
        memo = 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 = True
                break
        if flg:
            ok = mid  # next mid will be longer
        else:
            ng = mid  # next mid will be shorter
    print(ok)  # max length of substrings appeared twice or more


def __starting_point():
    abc141_e()

__starting_point()

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

#二分探索
N = ir()
S = sr()

def check(x):
    # x文字右側にずらした場所を調べる
    candidate = set()
    for i in range(N - 2*x + 1):
        candidate.add(S[i:i+x])
        if S[i+x:i+2*x] in candidate:
            return True
    return False

ok = 0; ng = N
while abs(ng-ok) > 1:
    mid = (ok+ng) // 2
    if check(mid):
        ok = mid
    else:
        ng = mid

print(ok)


from collections import deque

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

def exists(length):
    que = deque()
    V = set()
    for left in range(N - length + 1):
        if left > length - 1:
            V.add(que.popleft())
        T = S[left: left + length]
        if T in V:
            return True
        que.append(T)
    return False

ok = 0
ng = N
while ng - ok > 1:
    mid = (ok + ng) // 2

    if exists(mid):
        ok = mid
    else:
        ng = mid

print(ok)



N = int(input())
S = str(input())
ans = 0
j = 0
for i in range(N):
  while j < N and S[i:j] in S[j:]:
    ans = max(ans,j-i)
    j += 1

print(ans)

n=int(input())
s=input()

from collections import defaultdict

def check(l):
    d = defaultdict(lambda: -1)
    for i in range(n-l+1):
        if d[s[i:i+l]] != -1:
            if d[s[i:i+l]] + l <= i:
                return True
        else:
            d[s[i:i+l]]=i
    return False

ok=0
ng=len(s)

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

print(ok)

class RollingHash:
    """Rolling Hash"""

    __slots__ = ["_base", "_mod", "_hash", "_power"]

    def __init__(self, source: str, base: int = 1007, mod: int = 10 ** 9 + 7) -> None:
        self._base = base
        self._mod = mod
        self._hash = [0] * (len(source) + 1)
        self._power = [0] * (len(source) + 1)

        self._power[0] = 1
        for i, c in enumerate(source, 1):
            self._hash[i] = (self._hash[i - 1] * self._base + ord(c)) % self._mod
            self._power[i] = self._power[i - 1] * self._base % self._mod

    def get_hash(self, left: int, right: int) -> int:
        """Return hash of interval [left, right)."""
        return (
            self._hash[right] - self._hash[left] * self._power[right - left]
        ) % self._mod


def abc141_e():
    # https://atcoder.jp/contests/abc141/tasks/abc141_e
    N = int(input())
    S = input().rstrip()

    rh = RollingHash(S)
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        flg = False
        memo = 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 = True
                break
        if flg:
            ok = mid  # next mid will be longer
        else:
            ng = mid  # next mid will be shorter

    print(ok)  # max length of substrings appeared twice or more


def __starting_point():
    abc141_e()

__starting_point()

n = int(input())
s = input()
dp = [0 for i in range(n + 1)]
for i in range(n):
    if s[i - dp[i]:i + 1] in s[:i - dp[i]]:
        dp[i + 1] = dp[i] + 1
    else:
        dp[i + 1] = dp[i]
print(dp[n])

n=int(input());s=input()

a=0
i=0
j=1
while j<n:
    if s[i:j] in s[j:]:
        a=max(a,j-i)
        j+=1
    else:
        i+=1

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

from random import randint


class RollingHash:
    def __init__(self, s):
        self.base = [7073, 7577, 5445, 2742, 6972, 7547, 2267, 286, 6396, 7147,
                     3307, 188, 266, 8253, 2818, 9527, 5110, 1207, 4633, 6196,
                     309, 2646, 7533, 85, 9870, 4730, 6862, 9213, 7456, 7098,
                     6805, 674, 5821, 4864, 8061, 1826, 2219, 459, 5937, 5667,
                     9033, 5552, 7263, 2402, 9809, 3701, 7048, 2874, 8350, 6006,
                     973, 3317, 2522, 5546, 1669, 1545, 7972, 4979, 9905, 173,
                     6812, 7715, 5006, 6068, 6340, 4989, 5510, 6380, 1200, 6739,
                     5527, 4000, 6519, 3448, 2933, 6048, 3133, 1667, 9086, 8368,
                     4914, 7142, 2770, 7752, 391, 7052, 5476, 3105, 8322, 3501,
                     7454, 3167, 8730, 9002, 4564, 138, 2197, 7238, 3411, 7433][randint(0, 99)]
        self.mod = 4611686018427387903
        self.size = len(s)
        self.string = s

        self.hash = self.make_hashtable(s)
        self.pow = self.make_powtable()

    def make_hashtable(self, _s):
        hashtable = [0] * (self.size + 1)
        for i in range(self.size):
            hashtable[i + 1] = (hashtable[i] * self.base + ord(_s[i])) % self.mod
        return hashtable

    def make_powtable(self):
        power = [1] * (self.size + 1)
        for i in range(self.size):
            power[i + 1] = (self.base * power[i]) % self.mod
        return power

    def get_hash(self, left, right):
        """get hash of s[left:right]"""
        return (self.hash[right] - self.hash[left] * self.pow[right - left]) % self.mod

    def contain(self, a):
        """return a in s"""
        m = len(a)
        if m > self.size:
            return False
        hashs = self.get_hash(0, m)
        hasha = 0
        for i in range(m):
            hasha = (hasha * self.base + ord(a[i])) % self.mod
        for i in range(self.size - m + 1):
            if hasha == hashs:
                return True
            hashs = self.get_hash(i, m + i)
        return hasha == hashs


from collections import defaultdict
# d = defaultdict(int)で0で初期化
# d = defaultdict(lambda: 100)で100で初期化
n, s = int(input()), input()
rh = RollingHash(s)


def check(m):
    d = defaultdict(lambda: 10000000)
    for i in range(n - m + 1):
        h = rh.get_hash(i, i + m)
        d[h] = min(d[h], i)
        # m以上離れていて2回目
        if i - d[h] >= m:
            return True
    return False


l, r = 0, n // 2 + 1
while l + 1 < r:
    mid = (l + r) // 2
    if check(mid):
        l = mid
    else:
        r = mid
print(l)


import sys
#input = sys.stdin.buffer.readline

def main():
    N = int(input())
    s = input()
    a,i,j = 0,0,1
    
    while j < N:
        if s[i:j] in s[j:]:
            a = max(a,j-i)
            j += 1
        else:
            i += 1
        if i == j:
            j += 1
            
    print(a)

def __starting_point():
    main()

__starting_point()

n = int(input())
s = input()

A = 1234567
MOD = 10000000000000007

def ok(length):
    rolling_hash = 0
    head = pow(A, length, MOD)
    occurence = {}
    for i in range(n):
        rolling_hash = (rolling_hash * A + ord(s[i])) % MOD
        if i - length >= 0:
            rolling_hash = (rolling_hash - head * ord(s[i-length])) % MOD
        if rolling_hash not in occurence:
            occurence[rolling_hash] = []
        occurence[rolling_hash].append(i)

    for key in occurence:
        if occurence[key][-1] - occurence[key][0] >= length:
            return True
    return False

bottom, top = 0, n

while top - bottom > 1:
    mid = (top + bottom) // 2
    if ok(mid):bottom = mid
    else: top = mid

print(bottom)

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

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


N = int(input())
S = input()
ok, ng = 0, N + 1
while abs(ok - ng) > 1:
    x = (ok + ng) // 2
    check = set()
    for i in range(N - x + 1):
        check.add(S[i: i + x])
        if S[i + x: i + 2 * x] in check:
            ok = x
            break
    else:
        ng = x

print(ok)

I=input;n=int(I());s=I();j=1;r=[]
for i in range(n):
    while (j<n)and(s[i:j] in s[j:]):j+=1
    r.append(j-i-1)
print(max(r))

N = int(input())
S = input()
from collections import deque

def f(m):
    se = set()
    q = deque()
    for i in range(0,N-m+1):
        h = hash(S[i:i+m])
        q.append(h)
        if h in se:
            return True
        if len(q) >= m:
            se.add(q.popleft())
    return False

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

#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)

class DoubleRollingHash:
    def __init__(self, seq, f=ord):
        self.n = len(seq)
        self.base1, self.base2 = 1007, 2009
        self.mod1, self.mod2 = 1000000007, 1000000009
        self.f = f # set numerizing function

        self.hash1, self.hash2 = [0]*(self.n+1), [0]*(self.n+1)
        self.power1, self.power2 = [1]*(self.n+1), [1]*(self.n+1)

        for i, e in enumerate(seq):
            self.hash1[i+1] = (self.hash1[i] * self.base1 + self.f(e)) % self.mod1
            self.hash2[i+1] = (self.hash2[i] * self.base2 + self.f(e)) % self.mod2
            self.power1[i+1] = (self.power1[i] * self.base1) % self.mod1
            self.power2[i+1] = (self.power2[i] * self.base2) % self.mod2

    # get hash value of seq[left:right]
    def get(self, l, r):
        v1 = (self.hash1[r] - self.hash1[l] * self.power1[r-l]) % self.mod1
        v2 = (self.hash2[r] - self.hash2[l] * self.power2[r-l]) % self.mod2
        return v1, v2

    # get lcp of seq[a:] and seq[b:]
    def getLCP(self, a, b):
        l = self.n - max(a, b) + 1
        left, right = 0, l
        while right - left > 1:
            mid = (left + right) // 2
            if self.get(a, a+mid) == self.get(b, b+mid): left = mid
            else: right = mid
        return left

class RollingHash:
    def __init__(self, seq, f=ord):
        self.n = len(seq)
        self.base, self.mod = 1007, pow(2, 61) - 1
        self.f = f # set numerizing function
        self.hash, self.power = [0]*(self.n+1), [1]*(self.n+1)
        for i, e in enumerate(seq):
            self.hash[i+1] = (self.hash[i] * self.base + self.f(e)) % self.mod
            self.power[i+1] = (self.power[i] * self.base) % self.mod

    # get hash value of seq[left:right]
    def get(self, l, r): return (self.hash[r] - self.hash[l] * self.power[r-l]) % self.mod

    # get lcp of seq[a:] and seq[b:]
    def getLCP(self, a, b):
        l = self.n - max(a, b) + 1
        left, right = 0, l
        while right - left > 1:
            mid = (left + right) // 2
            if self.get(a, a+mid) == self.get(b, b+mid): left = mid
            else: right = mid
        return left


def main():
    N = I()
    S = SL()

    rh = RollingHash(S)
    ans = 0

    def check(m):
        d = defaultdict(lambda: -1)
        for i in range(N-m+1):
            v = rh.get(i, i+m)
            if d[v] != -1:
                if i >= d[v] + m:
                    return True
            else:
                d[v] = i
        return False

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

    print(left)


def __starting_point():
    main()
__starting_point()

import numpy as np
def main():
    n = int(input())
    s = list(input())
    for i in range(n):
        s[i] = ord(s[i]) - ord("a")
    s = np.array(s)
    dp = np.zeros((n+1, n+1), dtype=np.int64)
    tmp = np.arange(0, n+1)
    t = np.zeros((n+1, n+1))
    for i in range(n+1):
        t[i] += tmp
        tmp -= 1
#    for i in range(n+1):
#        print(t[i])
    for i in range(n):
        c = s[i]
        equal = (c == s)
#        print(equal)
        dp[i+1][1:] += equal
        dp[i+1][1:] += equal * dp[i][:-1]
#    for i in range(n+1):
#        print(dp[i])
    dp = np.minimum(dp, t)
#    for i in range(n+1):
#        print(dp[i])
    ans = 0
    for i in range(1, n):
        tmp = dp[i][i+1:]
        tmp = tmp[ans<tmp]
        if 0 < len(tmp):
            ans = max(ans, max(tmp))
    print((int(ans)))

def __starting_point():
    main()

__starting_point()

def ok(k):
    # 長さkの連続部分列で重ならずに2回以上現れるものがある
    D = {}
    for i in range(n-k+1):
        s = S[i:i+k]
        try:
            if D[s]+k <= i:
                return True
        except:
            D[s] = i
    return False


n = int(input())
S = input()
# 二分探索でTrueになる最大のkを求める
l, r = 0, n+1
while r-l > 1:
    c = (l+r)//2
    if ok(c):
        l = c
    else:
        r = c
print(l)


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

long=0
for i in range(N-1):
  for j in range(i+long+1,N):
    if not (S[i:j] in S[j:]):
      break
  long=max(long,j-i-1)
print(long)

n = int(input())
s = input()

def search(x):
    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:
            return True
    return False

l = 0
r = n//2+1
while r > l+1:
    mid = (r+l)//2
    if search(mid):
        l = mid
    else:
        r = mid
print(l)

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

def main():
    n = int(input())
    s = input().rstrip()
    l = 0
    r = n
    while l < r:
        mid = (l+r+1) // 2
        if check(mid, n, s):
            l = mid
        else:
            r = mid-1
    print((l+r+1)//2)

def __starting_point():
    main()
__starting_point()

N=int(input())
S=input()
ans = 0
j = 0
for i in range(N):
  while j < N and S[i:j] in S[j:]:
    j += 1
  ans = max(ans,j-i-1)
print(ans)



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

def f(m):
    se = set()
    arr = [None]*N
    for i in range(0,N-m+1):
        if i >= m:
            se.add(arr[i-m])
        arr[i] = hash(S[i:i+m])
        if arr[i] in se:
            return True
    return False

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

from collections import defaultdict


def read():
    N = int(input().strip())
    S = input().strip()
    return N, S


def solve(N, S):
    low = 0
    high = (N >> 1) + 1
    while high - low > 1:
        mid = (high + low) >> 1
        is_match = False
        m = N-mid+1
        d = defaultdict(list)
        for i in range(0, m):
            d[S[i:i+mid]].append(i)
        for v in d.values():
            if v[-1] - v[0] >= mid:
                is_match = True
                break
        if is_match:
            low = mid
        else:
            high = mid
    return low


def __starting_point():
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))
__starting_point()

n=int(input())
s=input()
r=n//2
l=-1
while r-l>1:
  mid=(r+l)//2
  d=dict()
  ok=False
  for i in range(n-mid):
    ss=s[i:i+mid+1]
    if ss not in d:
      d[ss]=i
    else:
      if d[ss]+mid<i:
        ok=True
  if ok:
    l=mid
  else:
    r=mid
print(r)

#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)

class RollingHash:
    def __init__(self, seq, f=ord):
        self.n = len(seq)
        self.base1, self.base2 = 1007, 2009
        self.mod1, self.mod2 = 1000000007, 1000000009
        self.f = f # set numerizing function

        self.hash1, self.hash2 = [0]*(self.n+1), [0]*(self.n+1)
        self.power1, self.power2 = [1]*(self.n+1), [1]*(self.n+1)

        for i, e in enumerate(seq):
            self.hash1[i+1] = (self.hash1[i] * self.base1 + self.f(e)) % self.mod1
            self.hash2[i+1] = (self.hash2[i] * self.base2 + self.f(e)) % self.mod2
            self.power1[i+1] = (self.power1[i] * self.base1) % self.mod1
            self.power2[i+1] = (self.power2[i] * self.base2) % self.mod2

    # get hash value of seq[left:right]
    def get(self, l, r):
        v1 = (self.hash1[r] - self.hash1[l] * self.power1[r-l]) % self.mod1
        v2 = (self.hash2[r] - self.hash2[l] * self.power2[r-l]) % self.mod2
        return v1, v2

    # get lcp of seq[a:] and seq[b:]
    def getLCP(self, a, b):
        l = self.n - max(a, b) + 1
        left, right = 0, l
        while right - left > 1:
            mid = (left + right) // 2
            if self.get(a, a+mid) == self.get(b, b+mid): left = mid
            else: right = mid
        return left


def main():
    N = I()
    S = SL()

    rh = RollingHash(S)
    ans = 0

    def check(m):
        d = defaultdict(lambda: -1)
        for i in range(N-m+1):
            v = rh.get(i, i+m)
            if d[v] != -1:
                if i >= d[v] + m:
                    return True
            else:
                d[v] = i
        return False

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

    print(left)


def __starting_point():
    main()
__starting_point()

import numpy as np

N = int(input())
S = np.array(list(input()))


def match_length(s1, s2, m):
    x = np.zeros(len(s1) + 2, dtype=bool)
    x[1:-1] = (s1 == s2)

    l = max(np.diff(np.nonzero(x == 0)[0]) - 1)
    return min(m, l)


ans = 0
for i in range(1, N - 1):
    ans = max(ans, match_length(S[i:], S[:-i], i))
print(ans)


import numpy as np

n = int(input())
s = np.array(list(input()))

l = s.size

dp = np.zeros(l, dtype=np.int16)
ans = 0
for i, e in enumerate(s, 1):
    dp_prev = dp.copy()
    mx = np.arange(1, l + 1) - i
    idx = np.hstack([np.full(i, False), s[i:] == e]).astype(np.bool)
    idx_prev = np.roll(idx, -1)
    dp = np.zeros(l, dtype=np.int16)
    dp[idx] = np.minimum(dp_prev[idx_prev] + 1, mx[idx])
    ans = max(ans, dp.max())

print(ans)


from collections import defaultdict

class RollingHash(object):
    def __init__(self, S: str, MOD: int = 10 ** 9 + 7, BASE: int = 10 ** 5 + 7):
        self.S = S
        self.N = N = len(S)
        self.MOD = MOD
        self.BASE = BASE
        self.S_arr = [ord(x) for x in S]

        self.POWER = [1] * (N + 1)
        self.HASH  = [0] * (N + 1)
        p, h = 1, 0
        for i in range(N):
            self.POWER[i + 1] = p = (p * BASE) % MOD
            self.HASH[i + 1] = h = (h * BASE + self.S_arr[i]) % MOD

    def hash(self, l: int, r: int):
        # get hash for S[l:r]
        _hash = self.HASH[r] - (self.HASH[l] * self.POWER[r - l] % self.MOD)
        if _hash < 0:
            _hash += self.MOD
        return _hash

# 汎用的な二分探索のテンプレ
# check_func(x) = true となるxの最小値を探索する
# left : check_func(x) = falseとなるx
# right: check_func(x) = true となるx
# search_max: check_func(x) = true となるxの"最大値"を探索する場合はTrue
# check_func: answer <= x であればcheck_func(x) = true となるような関数
def binary_search(left: int, right: int, check_func, search_max:bool=False):
    # ok と ng のどちらが大きいかわからないことを考慮
    while abs(right - left) > 1:
        mid = (left + right) // 2
    
        if check_func(mid) ^ search_max:
            right = mid
            # print(left, right, mid, 't')
        else:
            left = mid
            # print(left, right, mid, 'f')

    return left if search_max else right

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

    rs = RollingHash(S, MOD=998244353, BASE=37)

    # 長さLの部分文字列同士が、範囲を重ねず同じ文字列となる場合はTrue,
    # そうでない場合はFalseを返す関数
    def isOK(L):
        if L == 0:
            return True
        hash_to_left = defaultdict(list)
        for i in range(N - L + 1):
            _hash = rs.hash(i, i + L)
            # hashが衝突しても文字列が完全に一致するか分からないので、
            # 衝突した場合は文字列が完全に一致するか調べ、かつ
            # 文字列同士がSの中で重なるような範囲にない場合はOKとする
            for j in hash_to_left[_hash]:
                if j+L <= i and S[i:i+L] == S[j:j+L]:
                    return True
            hash_to_left[_hash].append(i)

        return False
    # 範囲が重ならないことが条件にあるので、答えは最大でもN // 2（文字列の長さの半分）となる。
    # ただし、二分探索する上で絶対に答えとならない範囲を含めたいので、
    # 探索範囲としてはN // 2 + 1 と、+1しておく。
    ans = binary_search(0, N // 2 + 1, isOK, search_max=True)
    print(ans)

def __starting_point():
    main()
__starting_point()

from typing import List


class RollingHash:
    __slots__ = ["source", "length", "base", "mod", "hash", "power"]

    def __init__(self, source: str, base: int = 1007, mod: int = 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) -> List[int]:
        """Compute hash of interval [0, right)."""
        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) -> List[int]:
        """Compute mod of power of base."""
        cur, power = 1, [1]
        for i in range(self.length):
            cur *= self.base % self.mod
            power.append(cur)
        return power

    def get_hash(self, left: int, right: int):
        """Compute hash of interval [left, right)."""
        return (
            self.hash[right] - self.hash[left] * self.power[right - left]
        ) % self.mod


def abc141_e():
    # https://atcoder.jp/contests/abc141/tasks/abc141_e
    N = int(input())
    S = input().rstrip()
    rh = RollingHash(S)
    ok, ng = 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  # next mid will be longer
        else:
            ng = mid  # next mid will be shorter
    print(ok)  # max length of substrings appeared twice or more


def __starting_point():
    abc141_e()

__starting_point()

n = int(input())
s = input()
 
max_len = 0
j = 0
 
for i in range(n):
    while j < n and s[i:j] in s[j:]:
        j += 1
    max_len = max(max_len,j-i-1)
 
print(max_len)

def ok(l):
    # 長さlの連続部分列で重ならずに2回以上現れるものがある
    D = {}
    for i in range(n-l+1):
        h = hash(S[i:i+l])
        try:
            if D[h] + l <= i:
                return True
        except:
            D[h] = i
    return False


n = int(input())
S = input()
# 二分探索でTrueになる最大のkを求める
l, r = 0, n+1
while r-l > 1:
    c = (l+r)//2
    if ok(c):
        l = c
    else:
        r = c
print(l)


n = int(input())
s = input()

max_len = 0
j = 0

for i in range(n):
    while j < n and s[i:j] in s[j:]:
        j += 1
    max_len = max(max_len,j-i-1)

print(max_len)

# ABC141E - Who Says a Pun?
def resolve():
    N = int(input())
    S = input().rstrip()
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        flg = False
        memo = set()
        for i in range(N - 2 * mid + 1):
            memo.add(hash(S[i : i + mid]))
            if hash(S[i + mid : i + 2 * mid]) in memo:
                flg = True
                break
        if flg:
            ok = mid  # next mid will be longer
        else:
            ng = mid  # next mid will be shorter
    print(ok)  # max length of substrings appeared twice or more


resolve()


from typing import List


class RollingHash:
    __slots__ = ["_source", "_length", "_base", "_mod", "_hash", "_power"]

    def __init__(self, source: str, base: int = 1007, mod: int = 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) -> List[int]:
        """Compute hash of interval [0, right)."""
        hash_from_zero = [0] * (self._length + 1)
        cur = 0
        for i, c in enumerate(self._source, 1):
            cur = (cur * self._base + ord(c)) % self._mod
            hash_from_zero[i] = cur
        return hash_from_zero

    def _get_base_pow(self) -> List[int]:
        """Compute mod of power of base."""
        power = [0] * (self._length + 1)
        power[0] = 1
        cur = 1
        for i in range(1, self._length + 1):
            cur *= self._base % self._mod
            power[i] = cur
        return power

    def get_hash(self, left: int, right: int):
        """Compute hash of interval [left, right)."""
        return (
            self._hash[right] - self._hash[left] * self._power[right - left]
        ) % self._mod


def abc141_e():
    # https://atcoder.jp/contests/abc141/tasks/abc141_e
    N = int(input())
    S = input().rstrip()
    rh = RollingHash(S)
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        flg = False
        memo = 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 = True
                break
        if flg:
            ok = mid  # next mid will be longer
        else:
            ng = mid  # next mid will be shorter
    print(ok)  # max length of substrings appeared twice or more


def __starting_point():
    abc141_e()

__starting_point()

import random

class RollingHash(object):
    def __init__(self, S: str, MOD: int = 998244353, BASE: int = 37):
        self.S = S
        self.N = N = len(S)
        self.MOD = MOD
        self.BASE = BASE
        self.S_arr = [ord(x) for x in S]

        self.POWER = [1] * (N + 1)
        self.HASH  = [0] * (N + 1)
        p, h = 1, 0
        for i in range(N):
            self.POWER[i + 1] = p = (p * BASE) % MOD
            self.HASH[i + 1] = h = (h * BASE + self.S_arr[i]) % MOD

    def hash(self, l: int, r: int):
        # get hash for S[l:r]
        _hash = (self.HASH[r] - self.HASH[l] * self.POWER[r - l]) % self.MOD
        return _hash

# 汎用的な二分探索のテンプレ
# check_func(x) = true となるxの最小値を探索する
# left : check_func(x) = falseとなるx
# right: check_func(x) = true となるx
# search_max: check_func(x) = true となるxの"最大値"を探索する場合はTrue
# check_func: search_max = False の場合、answer <= x であればcheck_func(x) = true となるような関数
#             search_max = True  の場合、x <= answer であればcheck_func(x) = true となるような関数
def binary_search(left: int, right: int, check_func, search_max:bool=False):
    # ok と ng のどちらが大きいかわからないことを考慮
    while abs(right - left) > 1:
        mid = (left + right) // 2
    
        if check_func(mid) ^ search_max:
            right = mid
        else:
            left = mid

    return left if search_max else right

def main():
    N = int(input())
    S = input()
    MOD = 10 ** 18 + 3
    # BASEはMOD未満で1でない奇数とする
    BASE = random.randint(2, MOD // 2 - 1) * 2 + 1
    rs = RollingHash(S, MOD=MOD, BASE=BASE)

    D = [0] * N
    # 長さLの部分文字列同士が、範囲を重ねず同じ文字列となる場合はTrue,
    # そうでない場合はFalseを返す関数
    def isOK(L):
        if L == 0:
            return True
        
        for i in range(min(L, N - 2 * L + 1)):
            D[i] = rs.hash(i, i + L)
        hashes = set()
        for i in range(L, N - L + 1):
            # 自分より開始点がL以上前の文字列のハッシュを検索対象に追加
            hashes.add(D[i - L])
            D[i] = v = rs.hash(i, i + L)
            # ハッシュが衝突したら、範囲を重ねず同じ文字列となる文字列が存在することになる
            if v in hashes:
                return True
        return False

    # 範囲が重ならないことが条件にあるので、答えは最大でもN // 2（文字列の長さの半分）となる。
    # ただし、二分探索する上で絶対に答えとならない範囲を含めたいので、
    # 探索範囲としてはN // 2 + 1 と、+1しておく。
    ans = binary_search(0, N // 2 + 1, isOK, search_max=True)
    print(ans)

def __starting_point():
    main()
__starting_point()

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

    def rolling_hash(s, mod, base = 37):
        l = len(s)
        h = [0]*(l + 1)
        v = 0
        for i in range(l):
            h[i+1] = v = (v * base + ord(s[i])) % mod
        pw = [1]*(l + 1)
        v = 1
        for i in range(l):
            pw[i+1] = v = v * base % mod
        return h, pw

    def chk(S, mod, D = [0]*N):
        h, pw = rolling_hash(S, mod)
        left = 0; right = N//2+1
        while left+1 < right:
            l = mid = (left + right) >> 1
            p = pw[l]
            for i in range(min(l, N-2*l+1)):
                D[i] = (h[l+i] - h[i]*p) % mod
            s = set()
            ok = 0
            for i in range(l, N-l+1):
                s.add(D[i-l])
                D[i] = v = (h[l+i] - h[i]*p) % mod
                if v in s:
                    ok = 1
                    break
            if ok:
                left = mid
            else:
                right = mid
        return left

    print((chk(S, 10**9 + 9)))
solve()


n = int(input())
s = input()
j = 1
result = [0]
end = n//2 + 1
for i in range(n):
    while (j < n-1) and (s[i:j] in s[:i]+"0"+s[j:]):
        j += 1
    result.append(j-i-1)
print(max(result))

class RollingHash():
    def __init__(self,s):
        self.n=n=len(s)
        self.b=b=129
        self.M=M=2**61-1
        x,y=1,0
        self.f=f=[x]*(n+1)
        self.h=h=[y]*(n+1)
        for i,c in enumerate(s.encode()):
            f[i+1]=x=x*b%M
            h[i+1]=y=(y*b+c)%M
    def get(self,l,r):
        return(self.h[r]-self.h[l]*self.f[r-l])%self.M
def check(x):
    d={}
    for i in range(0,n-x+1):
        k=s.get(i,i+x)
        if k in d:
            if d[k]+x<=i:
                return True
        else:
            d[k]=i
    return False
n=int(input())
s=RollingHash(input())
ok,ng=0,n
while ng-ok>1:
    mid=ok+ng>>1
    if check(mid):
        ok=mid
    else:
        ng=mid
print(ok)

import sys
sys.setrecursionlimit(10**9)
from collections import defaultdict
N = int(input())
S = input()
if N==2:
  if S[1] == S[0]:
    print((1))
  else:
    print((0))
  return
def hantei(mid):
  flag = False
  string = S[:mid]
  dic = defaultdict(int)
  dic[string] = -1
  for k in range(mid, N):
    string += S[k]
    string = string[1:]
    if dic[string] < 0:
      if k -mid+2+ dic[string] >= mid:
        flag = True
        break
    else:
      dic[string] = -k+mid-2
  if flag:
    return True
  else: 
    return False
ok = N//2+1 #False
ng = 0 #True
while ok - ng > 1:
  mid = (ok + ng) // 2
  if hantei(mid):
    ng = mid
  else:
    ok = mid
if hantei(mid):
  print((min(mid, N//2)))
else:
  print((min(ng, N//2)))


n = int(input())
s = input() #sys.stdin.readlineは最後が改行

right=0
ans = 0
for left in range(n):
    while right<n:
        word = s[left:right+1]
        if word in s[right+1:]:
            ans = max(ans, len(word))
        else:
            break
        right+=1

print(ans)


# -*- coding: utf-8 -*-
# E
# 文字列比較をローリングハッシュを用いると高速

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

n = int(input())
s = input()[:-1]
# s = list(map(ord, list(input()[:-1])))
# print(s)

lb = 0
ub = n//2 + 1


def check(len):
    for l1 in range(n-len):
        for l2 in range(l1+len, n-len+1):
            if s[l1:l1+len] == s[l2:l2+len]:
                return True
    return False


mod = 10**9+7
base = 1234
power = [1]*(n+1)
for i in range(1, n+1):
    power[i] = power[i-1]*base%mod


def check2(m):
    res = 0
    for i in range(m):
        res+=s[i]*power[m-i-1]
        res%=mod

    dic = {res: 0}
    # defaultdictが早い
    # dic = defaultdict(int)
    # dic[res] = 0

    for i in range(n-m):
        res = ((res-s[i]*power[m-1])*base
                             +s[i+m])%mod
        if res in dic.keys():
            index = dic[res]
            if index +m<=i+1:
                return True
        else:
            dic[res] = i+1
    return False


def check3(m):
    dic = {}
    for i in range(n-m+1):
        s_ = s[i:i+m]
        if s_ in dic.keys():
            if dic[s_]+m<=i:
                return True
        else:
            dic[s_] = i
    return False


while ub > lb+1:
    x = (lb + ub)//2
    if check3(x):
        lb = x
    else:
        ub = x
    # print(lb, ub)


'''
print(3, check(3))
print(4, check(4))
print(5, check(5))
'''

print(lb)

class RollingHash():
    def __init__(self,s):
        self.n=n=len(s)
        self.b=b=129
        self.M=M=2**61-1
        x,y=1,0
        self.f=f=[x]*(n+1)
        self.h=h=[y]*(n+1)
        for i,c in enumerate(s.encode()):
            f[i+1]=x=x*b%M
            h[i+1]=y=(y*b+c)%M
    def get(self,l,r):
        return(self.h[r]-self.h[l]*self.f[r-l])%self.M
def main():
    n=int(input())
    s=RollingHash(input())
    ok,ng=0,n
    while ng-ok>1:
        mid=ok+ng>>1
        d={}
        for i in range(0,n-mid+1):
            k=s.get(i,i+mid)
            if k in d:
                if d[k]+mid<=i:
                    ok=mid
                    break
            else:
                d[k]=i
        else:
            ng=mid
    print(ok)
main()

n = int(input())
s = input()
j = 1
result = []
for i in range(n):
    while (j < n-1) and (s[i:j] in s[:i]+"0"+s[j:]):
        j += 1
    result.append(j-i-1)
print(max(result))

n = int(input())
s = input()

MOD = 10 ** 18 + 7
A = 123456

def ok(l):
    rolling_hash = 0
    strings = {}
    for i in range(n):
        rolling_hash *= A
        rolling_hash += ord(s[i])
        if i - l >= 0: rolling_hash -= ord(s[i-l]) * pow(A, l, MOD)
        rolling_hash %= MOD
        if i < l-1:continue
        if rolling_hash not in strings:
            strings[rolling_hash] = []
        strings[rolling_hash].append(i)

    for string in strings:
        if strings[string][-1] - strings[string][0] >= l:
            return True
    return False
    

bottom, top = 0, n

while top - bottom > 1:
    mid = (top + bottom) // 2
    if ok(mid): bottom = mid
    else: top = mid

print(bottom)

#141_E
n = int(input())
s = input()

x = 0
for i in range(n):
    s_ = s[:i+1]
    if s_[i - x:] in s_[: i - x]:
        x += 1

print(x)

import random
from collections import defaultdict


def atoi(s):
    return ord(s) - ord("a") + 1


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

mod = (1 << 61) - 1
b = random.randint(10000, mod - 1)


l = 0
r = (N + 1) // 2 + 1
while r - l > 1:
    d = (r + l) // 2
    memo = defaultdict(int)
    isok = False
    h = 0
    t = pow(b, d, mod)
    for i in range(d):
        h = (h * b + atoi(S[i])) % mod
    memo[h] = 1
    for i in range(1, N - d + 1):
        h = (h*b + atoi(S[i+d-1]) - t * atoi(S[i-1])) % mod
        if not memo[h]:
            memo[h] = i + 1
        elif memo[h] and i - memo[h] + 1 >= d:
            isok = True
    if isok:
        l = d
    else:
        r = d

print(l)

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


def __starting_point():
    main()

__starting_point()

# 32bitのMod一つでRollingHashを行った場合、
# 10**5個程度のHashを生成するだけでも
# 半分以上の確率でどこかのHashが衝突していることが分かります


# 小文字アルファベットの時のbese
base = 27  # alphabet


def getnum(x):
    return ord(x) - ord("a") + 1


# rolling hash実装

# 必要な定数
# mod = 1<<61-1としたときの高速余り計算
m30 = (1 << 30) - 1
m31 = (1 << 31) - 1
m61 = (1 << 61) - 1
mod = m61
positive_delta = m61 ** 4

# 高速化された計算
def mul(a, b):
    au = a >> 31
    ad = a & m31  # 余りを取ることが&演算でできる
    bu = b >> 31
    bd = b & m31
    mid = ad * bu + au * bd
    midu = mid >> 30
    midd = mid & m30
    return calcmod(au * bu * 2 + midu + (midd << 31) + ad * bd)


def calcmod(a):
    au = a >> 61
    ad = a & m61
    res = au + ad
    if res >= m61:
        res -= m61
    return res


# s:string
def rollinghash(s):
    num = len(s)
    res = [0] * (num + 1)
    pow_base = [1] * (num + 1)
    for i in range(num):
        res[i + 1] = calcmod(mul(res[i], base) + getnum(s[i]))
        pow_base[i + 1] = calcmod(mul(pow_base[i], base))
    return res, pow_base


def search(left, right, rh):
    return calcmod(rh[right] - mul(rh[left], pow_base[right - left]) + positive_delta)


n = int(input())
s = input()
rh, pow_base = rollinghash(s)

ng = n
ok = 0


def hantei(x, rh):
    kumi = {}
    for i in range(n - x + 1):
        temp = search(i, i + x, rh)
        if temp in kumi:
            pre_idx = kumi[temp]
            if i - pre_idx >= x:
                # print("pair", i, pre_idx, "delta", x)
                return True
        else:
            kumi[temp] = i
    # print(x, kumi)
    return False


while ng - ok > 1:
    mid = (ng + ok) // 2
    if hantei(mid, rh):
        ok = mid
    else:
        ng = mid
    # print(ok, ng)

print(ok)


def solve():
    N = int(input())
    Ss = input().rstrip()

    def isOK(L):
        setCand = set()
        RHs = []
        for i in range(N-L+1):
            RH = hash(Ss[i:i+L])
            RHs.append(RH)
            if i-L >= 0:
                setCand.add(RHs[i-L])
            if RH in setCand:
                return True
        return False

    ng, ok = N//2+1, 0
    while abs(ok-ng) > 1:
        mid = (ng+ok) // 2
        if isOK(mid):
            ok = mid
        else:
            ng = mid

    print(ok)


solve()


class RollingHash():
    def __init__(self, s, base, mod):
        self.mod = mod
        self.pw = pw = [1]*(len(s)+1)

        l = len(s)
        self.h = h = [0]*(l+1)

        v = 0
        for i in range(l):
            h[i+1] = v = (v * base + ord(s[i])) % mod
        v = 1
        for i in range(l):
            pw[i+1] = v = v * base % mod
    def get(self, l, r): #S[l:r]indexでいうl文字目からr-l文字目。r-l文字。
        return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod

    def check(self, d):
        ma = {}
        for i in range(N-d+1): #0からN-dまで
            p = self.get(i,i+d)
            if p in ma:
                if i - ma[p] >= d: #d文字以上離れているか
                  return True
            else:
                ma[p] = i
        return False
            
              
N =int(input())
S = str(input())

base1 = 1007
mod1 = 10**9+7

RH = RollingHash(S,base1,mod1)

left = 0
right = N//2+1
while right - left >1:
  mid = (left+right)//2
  if RH.check(mid): #こちらがokの方
    left = mid
  else:
    right = mid

print(left)      


from collections import defaultdict

class RollingHash(object):
    def __init__(self, S: str, MOD: int = 10 ** 9 + 7, BASE: int = 10 ** 5 + 7):
        self.S = S
        self.N = N = len(S)
        self.MOD = MOD
        self.BASE = BASE
        self.S_arr = [ord(x) for x in S]

        self.POWER = [1] * (N + 1)
        self.HASH  = [0] * (N + 1)
        p, h = 1, 0
        for i in range(N):
            self.POWER[i + 1] = p = (p * BASE) % MOD
            self.HASH[i + 1] = h = (h * BASE + self.S_arr[i]) % MOD

    def hash(self, l: int, r: int):
        # get hash for S[l:r]
        _hash = self.HASH[r] - (self.HASH[l] * self.POWER[r - l] % self.MOD)
        if _hash < 0:
            _hash += self.MOD
        return _hash

# 汎用的な二分探索のテンプレ
# check_func(x) = true となるxの最小値を探索する
# left : check_func(x) = falseとなるx
# right: check_func(x) = true となるx
# search_max: check_func(x) = true となるxの"最大値"を探索する場合はTrue
# check_func: answer <= x であればcheck_func(x) = true となるような関数
def binary_search(left: int, right: int, check_func, search_max:bool=False):
    # ok と ng のどちらが大きいかわからないことを考慮
    while abs(right - left) > 1:
        mid = (left + right) // 2
    
        if check_func(mid) ^ search_max:
            right = mid
            # print(left, right, mid, 't')
        else:
            left = mid
            # print(left, right, mid, 'f')

    return left if search_max else right

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

    rs = RollingHash(S)

    # 長さLの部分文字列同士が、範囲を重ねず同じ文字列となる場合はTrue,
    # そうでない場合はFalseを返す関数
    def isOK(L):
        if L == 0:
            return True
        hash_to_left = defaultdict(list)
        for i in range(N - L + 1):
            _hash = rs.hash(i, i + L)
            # hashが衝突しても文字列が完全に一致するか分からないので、
            # 衝突した場合は文字列が完全に一致するか調べ、かつ
            # 文字列同士がSの中で重なるような範囲にない場合はOKとする
            for j in hash_to_left[_hash]:
                if j+L <= i and S[i:i+L] == S[j:j+L]:
                    return True
            hash_to_left[_hash].append(i)

        return False
    # 範囲が重ならないことが条件にあるので、答えは最大でもN // 2（文字列の長さの半分）となる。
    # ただし、二分探索する上で絶対に答えとならない範囲を含めたいので、
    # 探索範囲としてはN // 2 + 1 と、+1しておく。
    ans = binary_search(0, N // 2 + 1, isOK, search_max=True)
    print(ans)

def __starting_point():
    main()
__starting_point()

import random
from collections import defaultdict
from itertools import accumulate
import sys
input = sys.stdin.readline
n = int(input())
s = input().rstrip()
mod = (1<<61)-1
base = 1000+random.randint(0,100)
power = [1]
for i in range(1,n):
  power.append((power[-1]*base)%mod)
hvalue = [0]
for i in range(n):
  hvalue.append((hvalue[-1]+(ord(s[i])*power[i]))%mod)
def rollinghash(l,r):
  return ((hvalue[r]-hvalue[l])*power[n-r])%mod
def pun(i):
  dc = defaultdict(int)
  if i>n//2:
    return False
  for j in range(n-i+1):
    x = rollinghash(j,i+j)
    if dc[x]:
      rg =dc[x]
      if rg<=j:
        return True
    else:
      dc[x] = i+j
  return False
l=0
r=n//2+1
while l+1<r:
  mi=(l+r)//2
  if pun(mi):
    l=mi
  else:
    r=mi
print(l)


n,s=open(0);j=r=0
for i in range(int(n)):
    while (j<int(n))and(s[i:j] in s[j:]):j+=1
    r=max(r,j-i-1)
print(r)

n=int(input())
s=input()
l=0
r=n
while r-l>1:
  mid=(r+l)//2
  dic={}
  flag=False
  for i in range(n-mid+1):
    tmp=s[i:i+mid]
    if tmp not in dic:
      dic[tmp]=i+mid
    else:
      if dic[tmp]<=i:
        flag=True
        break
  if flag:
    l=mid
  else:
    r=mid
print(l)

# -*- coding: utf-8 -*-
# E
# 文字列比較をローリングハッシュを用いると高速
# 用いなくてもpypy使わなくえれば通る

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

n = int(input())
s = input()[:-1]
# s = list(map(ord, list(input()[:-1])))
# print(s)

lb = 0
ub = n//2 + 1


def check(len):
    # これはTLE
    for l1 in range(n-len):
        for l2 in range(l1+len, n-len+1):
            if s[l1:l1+len] == s[l2:l2+len]:
                return True
    return False


def check3(m):
    # これはOK(pypyではなくpython3）
    dic = defaultdict(str)
    # dic = {}
    for i in range(n-m+1):
        s_ = s[i:i+m]
        if s_ in dic.keys():
            if dic[s_]+m<=i:
                return True
        else:
            dic[s_] = i
    return False


mod = 10**9+7
base = 1234
power = [1]*(n+1)
for i in range(1, n+1):
    power[i] = power[i-1]*base%mod

def check2(m):
    res = 0
    for i in range(m):
        res+=s[i]*power[m-i-1]
        res%=mod

    dic = {res: 0}
    # defaultdictが早い
    # dic = defaultdict(int)
    # dic[res] = 0

    for i in range(n-m):
        res = ((res-s[i]*power[m-1])*base
                             +s[i+m])%mod
        if res in dic.keys():
            index = dic[res]
            if index +m<=i+1:
                return True
        else:
            dic[res] = i+1
    return False


while ub > lb+1:
    x = (lb + ub)//2
    if check3(x):
        lb = x
    else:
        ub = x
    # print(lb, ub)


'''
print(3, check(3))
print(4, check(4))
print(5, check(5))
'''

print(lb)

from typing import List


class RollingHash:
    """Rolling Hash"""

    __slots__ = ["_length", "_base", "_mod", "_hash", "_power"]

    def __init__(self, source: str, base: int = 1007, mod: int = 10 ** 9 + 7):
        self._length = len(source)
        self._base = base
        self._mod = mod
        self._hash = self._build_hash_from_zero(source)
        self._power = self._build_base_power()

    def _build_hash_from_zero(self, source: str) -> List[int]:
        """Compute hash of interval [0, right)."""
        res = [0] * (self._length + 1)
        for i, c in enumerate(source, 1):
            res[i] = (res[i - 1] * self._base + ord(c)) % self._mod
        return res

    def _build_base_power(self) -> List[int]:
        """Compute mod of power of base."""
        res = [1] * (self._length + 1)
        for i in range(1, self._length + 1):
            res[i] = res[i - 1] * self._base % self._mod
        return res

    def get_hash(self, left: int, right: int):
        """Return hash of interval [left, right)."""
        return (
            self._hash[right] - self._hash[left] * self._power[right - left]
        ) % self._mod


def abc141_e():
    # https://atcoder.jp/contests/abc141/tasks/abc141_e
    N = int(input())
    S = input().rstrip()

    rh = RollingHash(S)
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        flg = False
        memo = 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 = True
                break
        if flg:
            ok = mid  # next mid will be longer
        else:
            ng = mid  # next mid will be shorter

    print(ok)  # max length of substrings appeared twice or more


def __starting_point():
    abc141_e()

__starting_point()

n=int(input())
s=list(map(ord,list(input())))
for i in range(n):s[i]-=97

from random import randint
roli_mod=1370757747362922367
roli_r=randint(2,roli_mod-2)
roli=[0]
roli_rr=1
for i in range(n):
  roli.append((roli[-1]+roli_rr*s[i])%roli_mod)
  roli_rr*=roli_r
  roli_rr%=roli_mod
def roli_hash(i,j):return ((roli[j+1]-roli[i]+roli_mod)%roli_mod)*pow(roli_r,roli_mod-1-i,roli_mod)%roli_mod
def roli_check(i1,j1,i2,j2):return roli_hash(i1,j1)==roli_hash(i2,j2)

ok=0
ng=(n+1)//2+1
while ok+1!=ng:
  i=(ok+ng)//2
  d={}
  f=False
  for j in range(n-i+1):
    h=roli_hash(j,j+i-1)
    if h in d:
      if j-d[h]>=i:
        f=True
        break
    else:d[h]=j
  if f:ok=i
  else:ng=i
print(ok)

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

MOD = 2 ** 61 - 1
root = 10000

rhs = [0]
for h in map(ord, S):
    rhs.append((root * rhs[-1] + h) % MOD)

pws = [1]
for i in range(N):
    pws.append(pws[-1] * root % MOD)

ok = 0
ng = N
while ng - ok > 1:
    mid = (ok + ng) // 2
    hashes = dict()
    flg = False
    for i in range(N - mid + 1):
        hashofsub = (rhs[i+mid] - rhs[i] * pws[mid]) % MOD
        if hashofsub in hashes:
            if i >= hashes[hashofsub] + mid:
                flg = True
                break
        else:
            hashes[hashofsub] = i
    
    if flg:
        ok = mid
    else:
        ng = mid

print(ok)

from typing import List


class RollingHash:
    """Rolling Hash"""

    __slots__ = ["_base", "_mod", "_hash", "_power"]

    def __init__(self, source: str, base: int = 1007, mod: int = 10 ** 9 + 7):
        self._base = base
        self._mod = mod
        self._hash = self._build_hash_from_zero(source)
        self._power = self._build_base_power(len(source))

    def _build_hash_from_zero(self, source: str) -> List[int]:
        """Compute hash of interval [0, right)."""
        res = [0] * (len(source) + 1)
        for i, c in enumerate(source, 1):
            res[i] = (res[i - 1] * self._base + ord(c)) % self._mod
        return res

    def _build_base_power(self, length: int) -> List[int]:
        """Compute mod of power of base."""
        res = [1] * (length + 1)
        for i in range(1, length + 1):
            res[i] = res[i - 1] * self._base % self._mod
        return res

    def get_hash(self, left: int, right: int):
        """Return hash of interval [left, right)."""
        return (
            self._hash[right] - self._hash[left] * self._power[right - left]
        ) % self._mod


def abc141_e():
    # https://atcoder.jp/contests/abc141/tasks/abc141_e
    N = int(input())
    S = input().rstrip()

    rh = RollingHash(S)
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        flg = False
        memo = 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 = True
                break
        if flg:
            ok = mid  # next mid will be longer
        else:
            ng = mid  # next mid will be shorter

    print(ok)  # max length of substrings appeared twice or more


def __starting_point():
    abc141_e()

__starting_point()

from typing import List


class RollingHash:
    __slots__ = ["source", "length", "base", "mod", "hash", "power"]

    def __init__(self, source: str, base: int = 1007, mod: int = 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) -> List[int]:
        """Compute hash of interval [0, right)."""
        hash_from_zero = [0] * (self.length + 1)
        cur = 0
        for i, c in enumerate(self.source, 1):
            cur = (cur * self.base + ord(c)) % self.mod
            hash_from_zero[i] = cur
        return hash_from_zero

    def _get_base_pow(self) -> List[int]:
        """Compute mod of power of base."""
        power = [1] * (self.length + 1)
        cur = 1
        for i in range(1, self.length + 1):
            cur *= self.base % self.mod
            power[i] = cur
        return power

    def get_hash(self, left: int, right: int):
        """Compute hash of interval [left, right)."""
        return (
            self.hash[right] - self.hash[left] * self.power[right - left]
        ) % self.mod


def abc141_e():
    # https://atcoder.jp/contests/abc141/tasks/abc141_e
    N = int(input())
    S = input().rstrip()
    rh = RollingHash(S)
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        flg = False
        memo = 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 = True
                break
        if flg:
            ok = mid  # next mid will be longer
        else:
            ng = mid  # next mid will be shorter
    print(ok)  # max length of substrings appeared twice or more


def __starting_point():
    abc141_e()

__starting_point()

I=input;n=int(I());s=I();j=r=0
for i in range(n):
    while (j<n)and(s[i:j] in s[j:]):j+=1
    r=max(r,j-i-1)
print(r)