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
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


class RollingHash(object):
    def __init__(self, source: str, base=1000000007, mod=9007199254740997):
        self.source = source
        self.base = base
        self.mod = mod
        self.hash_from_zero_to = self._get_hash_from_zero_to()
        self.base_pow = self._get_base_pow()

    
    def _get_hash_from_zero_to(self):
        hash_from_zero_to = [0]
        for si in self.source:
            hash_from_zero_to.append((hash_from_zero_to[-1] * self.base + ord(si)) % self.mod)

        return hash_from_zero_to

    
    def _get_base_pow(self):
        base_pow = [1]
        for i in range(len(self.source)):
            base_pow.append(base_pow[-1] * self.base % self.mod)

        return base_pow

    
    def get_hash(self, left: int, right: int):
        return (self.hash_from_zero_to[right]
                - self.hash_from_zero_to[left] * self.base_pow[right - left]) % self.mod



def binsearch(func, rh: RollingHash, ok: int, ng: int):
    source_length = len(rh.source)
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if func(rh, mid, source_length):
            ok = mid
        else:
            ng = mid

    return ok



def judge(rh: RollingHash, target_length: int, source_length: int):
    memo = {}
    for start_idx in range(source_length - target_length + 1):
        cur_hash = rh.get_hash(start_idx, start_idx + target_length)
        if cur_hash in memo:
            if start_idx - memo[cur_hash] >= target_length:
                return True
        else:
            memo[cur_hash] = start_idx

    return False


n = ni()
s = ns()

rh = RollingHash(s)
print(binsearch(judge, rh, 0, n//2 + 2))

Solution (Python):
n1 = int(input())
s1 = input()

r1 = 0
r2 = 0
for i1 in range (n1):
    if n1 - (r1 * 2) - i1 < 0:
        break
    for i2 in range(n1 - r1):
        t2 = r1 + i2 + 1
        if s1[i1:i1 + t2] in s1[i1 + t2:] and s1[i1:i1 + t2] != "":
            continue
        else:
            r1 = max(r1, r1 + i2)
            break


print(r1)

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

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


class RollingHash(object):
    def __init__(self, source: str, base=10**9+7, mod=(1<<64)-1):
        self.source = source
        self.base = base
        self.mod = mod
        self.hash_from_zero_to = self._get_hash_from_zero_to()
        self.base_pow = self._get_base_pow()

    
    def _get_hash_from_zero_to(self):
        hash_from_zero_to = [0]
        for si in self.source:
            hash_from_zero_to.append((hash_from_zero_to[-1] * self.base + ord(si)) % self.mod)

        return hash_from_zero_to

    
    def _get_base_pow(self):
        base_pow = [1]
        for i in range(len(self.source)):
            base_pow.append(base_pow[-1] * self.base % self.mod)

        return base_pow

    
    def get_hash(self, left: int, right: int):
        return (self.hash_from_zero_to[right]
                - self.hash_from_zero_to[left] * self.base_pow[right - left]) % self.mod


def binsearch(func, rh: RollingHash, ok: int, ng: int):
    source_length = len(rh.source)
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if func(rh, mid, source_length):
            ok = mid
        else:
            ng = mid

    return ok



def judge(rh: RollingHash, target_length: int, source_length: int):
    memo = {}
    for start_idx in range(source_length - target_length + 1):
        cur_hash = rh.get_hash(start_idx, start_idx + target_length)
        if cur_hash in memo:
            if start_idx - memo[cur_hash] >= target_length:
                return True
        else:
            memo[cur_hash] = start_idx

    return False


n = ni()
s = ns()

rh = RollingHash(s)
print(binsearch(judge, rh, 0, n//2 + 2))

Solution (Python):
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N = int(input())
        S = input().rstrip()

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



if __name__ == '__main__':
    AtCoder().main()

Solution (Python):
import sys

input = sys.stdin.readline

def main():
    n = int(input())
    s = input()[::-1]
    ans = 0
    l = 0
    r = 1
    for r in range(1,n):
        if s[l:r] in s[r:]:
            ans=r-l
        else:
            l += 1
    print(ans)

main()

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

dp = [[0 for i in range(5005)] for j in range(5005)]

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

res = 0
for i in range(n):
    for j in range(n):
        if i >= j:
            continue
        curr = min(dp[i][j], j - i)
        res = max(res, curr)

print(res)

Solution (Python):
n = int(input())
s = input()
ans = 0
cursor = 1
for i in range(n):
    while s[i:cursor] in s[cursor:n]:
        ans = max(ans, cursor - i)
        cursor += 1
print(ans)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
S = input()


dp = list2d(N+1, N+1, 0)

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

mx = 0
for i in range(N+1):
    for j in range(N+1):
        
        if dp[i][j] > mx and abs(i-j) >= dp[i][j]:
            mx = dp[i][j]
print(mx)

Solution (Python):
n = int(input())
s = input()
_max = 0
memo_ls = [[0 for i in range(n)] for j in range(n)]
memo_dict = {i : [0 for j in range(n)] for i in range(-1,n)}
for i in range(n):
    for j in range(min(i+1,n-1), n):
        if s[i] != s[j]:
            continue
        candidate = memo_dict[i-1][j-1] + 1
        if candidate > j - i:
            candidate = j - i
        memo_dict[i][j] = candidate
        if candidate > _max:
            _max = candidate
print(_max)

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

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

Solution (Python):
from sys import stdin

N = int(stdin.readline().rstrip())
S = stdin.readline().rstrip()
dp = [[0] * (N + 1) for _ in range(N + 1)]
res = 0

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

print(res)

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

res = 0
dp = [[0]*(n+1) for _ in range(n+1)]
for i in reversed(range(n)):
    for j in reversed(range(i+1,n)):
        if s[i] == s[j]:
            dp[i][j] = dp[i+1][j+1] + 1
        cres = min(j-i, dp[i][j])
        res = max(res, cres)

print(res)

Solution (Python):
from collections import defaultdict

N = int(input())
S = input()
mod1 = 10 ** 9 + 7
mod2 = 10 ** 9 + 9
base1 = 1007
base2 = 2009

ok = 0
ng = N // 2 + 1
mid = (ok + ng) // 2
while ng - ok > 1:
    seen1 = defaultdict(lambda: 10 ** 5)
    seen2 = defaultdict(lambda: 10 ** 5)
    rh1 = 0
    rh2 = 0
    for i in range(mid):
        rh1 += ord(S[i]) * pow(base1, mid - i - 1, mod1)
        rh2 += ord(S[i]) * pow(base2, mid - i - 1, mod2)
        rh1 %= mod1
        rh2 %= mod2
    seen1[rh1] = 0
    seen2[rh2] = 0
    flag = 0
    for i in range(1, N - mid + 1):
        if flag == 1:
            break
        rh1 = (rh1 * base1 + ord(S[i + mid - 1]) - ord(S[i - 1]) * pow(base1, mid, mod1)) % mod1
        rh2 = (rh2 * base2 + ord(S[i + mid - 1]) - ord(S[i - 1]) * pow(base2, mid, mod2)) % mod2
        if i - seen1[rh1] >= mid and i - seen2[rh2] >= mid:
            ok = mid
            mid = (ok + ng) // 2
            flag = 1
        else:
            if seen1[rh1] == 10 ** 5:
                seen1[rh1] = i
            if seen2[rh2] == 10 ** 5:
                seen2[rh2] = i
    if flag == 0:
        ng = mid
        mid = (ok + ng) // 2

print(ok)

Solution (Python):
import sys

input = sys.stdin.readline

def main():
    n = int(input())
    s = input()[::-1]
    ans = 0
    l = 0
    r = 1
    while l < n:
        if s[l:r] in s[r:]:
            r += 1
            if r == n + 1: break
        else:
            l += 1
            ans = max(ans, r - l)
    ans = max(ans, r - l - 1)
    print(ans)

main()

Solution (Python):
inpl = lambda: list(map(int,input().split()))
N = int(input())
S = input()
character_pos = [ set() for _ in range(26) ]
ans = 0
continue_list = dict()
for i in range(N):
    s = S[i]
    new_continue_list = dict()
    cpos = character_pos[ord(s)-ord('a')]
    for p in cpos:
        new_continue_list[p] = 1
    cpos.add(i)
    for k, v in continue_list.items():
        if s == S[k+1]  and v + 1 <= i - k - 1:
            new_continue_list[k+1] = v+1
        elif v > ans:
            ans = v
    continue_list = new_continue_list

if len(continue_list.values()) > 0:
    ans = max(ans, max(continue_list.values()))
print(ans)

Solution (Python):
inpl = lambda: list(map(int,input().split()))
N = int(input())
S = input()
character_pos = [ set() for _ in range(26) ]
ans = 0
continue_list = dict()
for i in range(N):
    s = S[i]
    new_continue_list = dict()
    cpos = character_pos[ord(s)-ord('a')]
    for p in cpos:
        new_continue_list[p] = 1
    cpos.add(i)
    for k, v in continue_list.items():
        if s == S[k+1]  and v + 1 <= i - k - 1:
            new_continue_list[k+1] = v+1
        elif v > ans:
            ans = v
    continue_list = new_continue_list

if len(continue_list.values()) > 0:
    ans = max(ans, max(continue_list.values()))
print(ans)

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

import bisect

N = int(input())
s = input().split() 
s = list(s[0])

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

print(ans)

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

n=int(input())
s=input()
ans=0
for i in range(n-1):
    z=Z_algo(s[i:])
    ans=max(ans,max(z[j] for j in range(1,n-i) if z[j]-1<j))
print(ans)

Solution (Python):
from sys import stdin

N = int(stdin.readline().rstrip())
S = stdin.readline().rstrip()
dp = [[0] * (N + 1) for _ in range(N + 1)]
res = 0

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

print(res)

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

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

Solution (Python):
N = int(input())
S = input()
j = 1
ans = 0
for i in range(N):
  s = S[i:i + j]
  while S[i + j:].find(s) != -1:
    j += 1
    s = S[i:i + j]
    ans += 1
print(ans)

Solution (Python):
N = int(input())
S = input()
DP = [[0]*5005 for _ in range(5005)]

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

print(ans)

Solution (Python):

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


if __name__ == "__main__":
    main()

Solution (Python):

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


if __name__ == "__main__":
    main()

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

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
S = input()

def bisearch_max(mn, mx, func):
    """ 条件を満たす最大値を見つける二分探索 """

    ok = mn
    ng = mx
    while ok+1 < ng:
        mid = (ok+ng) // 2
        if func(mid):
            
            ok = mid
        else:
            
            ng = mid
    return ok

def calc(m):
    A = {}
    for i in range(N-m+1):
        a = S[i:i+m]
        if a in A:
            
            j = A[a]
            
            if i-j >= m:
                return True
        else:
            
            A[a] = i
    return False

print(bisearch_max(0, N, calc))

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
S = input()

def bisearch_max(mn, mx, func):
    """ 条件を満たす最大値を見つける二分探索 """

    ok = mn
    ng = mx
    while ok+1 < ng:
        mid = (ok+ng) // 2
        if func(mid):
            
            ok = mid
        else:
            
            ng = mid
    return ok

def calc(m):
    A = {}
    for i in range(N-m+1):
        a = S[i:i+m]
        if a in A:
            
            j = A[a]
            
            if i-j >= m:
                return True
        else:
            
            A[a] = i
    return False

print(bisearch_max(0, N, calc))

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
S = input()

def bisearch_max(mn, mx, func):
    """ 条件を満たす最大値を見つける二分探索 """

    ok = mn
    ng = mx
    while ok+1 < ng:
        mid = (ok+ng) // 2
        if func(mid):
            
            ok = mid
        else:
            
            ng = mid
    return ok

class RollingHash:

    MOD = 2 ** 64
    b = 10 ** 8 + 7

    def __init__(self, S):
        
        S = [ord(s)-97 for s in S]

        self.len = len(S)
        self.pow = [1] * (self.len+1)
        for i in range(self.len):
            self.pow[i+1] = self.pow[i] * self.b
            self.pow[i+1] %= self.MOD
        
        self.hash = [0] * (self.len+1)
        for i in range(self.len):
            self.hash[i+1] = self.hash[i] * self.b + S[i]
            self.hash[i+1] %= self.MOD
    
    
    def get(self, l, r):
        return (self.hash[r] - self.hash[l] * self.pow[r-l]) % self.MOD

def calc(m):
    A = {}
    for i in range(N-m+1):
        a_hash = rh.get(i, i+m)
        if a_hash in A:
            
            j = A[a_hash]
            
            if i-j >= m:
                return True
        else:
            
            A[a_hash] = i
    return False

rh = RollingHash(S)
print(bisearch_max(0, N, calc))

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
S = input()

def bisearch_max(mn, mx, func):
    """ 条件を満たす最大値を見つける二分探索 """

    ok = mn
    ng = mx
    while ok+1 < ng:
        mid = (ok+ng) // 2
        if func(mid):
            
            ok = mid
        else:
            
            ng = mid
    return ok

class RollingHash:

    MOD = 2 ** 64
    b = 10 ** 8 + 7

    def __init__(self, S):
        
        S = [ord(s)-97 for s in S]

        self.len = len(S)
        self.pow = [1] * (self.len+1)
        for i in range(self.len):
            self.pow[i+1] = self.pow[i] * self.b
            self.pow[i+1] %= self.MOD
        
        self.hash = [0] * (self.len+1)
        for i in range(self.len):
            self.hash[i+1] = self.hash[i] * self.b + S[i]
            self.hash[i+1] %= self.MOD
    
    
    def get(self, l, r):
        return (self.hash[r] - self.hash[l] * self.pow[r-l]) % self.MOD

def calc(m):
    A = {}
    for i in range(N-m+1):
        a_hash = rh.get(i, i+m)
        if a_hash in A:
            
            j = A[a_hash]
            
            if i-j >= m:
                return True
        else:
            
            A[a_hash] = i
    return False

rh = RollingHash(S)
print(bisearch_max(0, N, calc))

Solution (Python):

def main():
    n = int(input())
    s = input()
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    for i, c in enumerate(s):
        for j in range(n):
            if c == s[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
    ans = 0
    for i in range(n):
        for j in range(i+1,n+1):
            tmp=min(dp[i][j],j-i)
            ans=max(tmp,ans)
    print(ans)

main()

Solution (Python):
if __name__ == "__main__":
    N = int(input())
    S = input()

    dp = [[0] * 5005 for i in range(5005)]

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

    result = 0
    for i in range(N):
        for j in range(N):
            if i >= j:
                continue
            now = min(dp[i][j], j-i)
            result = max([now, result])

    print(result)

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

yes = 0
no = n // 2 + 1
while abs(yes - no) > 1:
	center = (yes + no) // 2
	d = set()
	for i in range(n - 2 * center + 1):
		d.add(s[i:i+center])
		if (s[i+center:i+2*center] in d):
			yes = center
			
			break
	if (yes != center):
		no = center
print(yes)

Solution (Python):
n = int(input())
S = input()
m = n//2
l,r = 0,n-1
ans = 0
def check(m):
    Se = set()
    for i in range(n-2*m+1):
        Se.add(S[i:i+m])
        if S[i+m:i+2*m] in Se:
            return True
    return False

while l<=r:
    m = (l + r) // 2
 
    if check(m):
        fl = True
        l = m+1
        ans = l-1
 
    else:
        r = m-1
 
print(ans)

Solution (Python):
n = int(input())
S = input()
m = n//2
l,r = 0,n-1
ans = 0
def check(m):
    Se = set()
    for i in range(n-2*m+1):
        Se.add(S[i:i+m])
        if S[i+m:i+2*m] in Se:
            return True
    return False

while l<=r:
    m = (l + r) // 2
 
    if check(m):
        fl = True
        l = m+1
        ans = l-1
 
    else:
        r = m-1
 
print(ans)

Solution (Python):
def calc(N, S):
    ll = 1
    lr = N // 2 + 1
    l = (ll + lr) // 2
    while True:
        d = {}
        for i in range(0, N - l + 1):
            s = S[i: i + l]
            if s in d:
                d[s] += [i]
            else:
                d[s] = [i]
        f = True
        for s in d:
            if len(d[s]) > 1 and [e for e in d[s][1:] if e > d[s][0] + l - 1]:
                ll = l
                f = False
                break
        if f:
            if l == 1:
                return 0
            lr = l
            if ll == lr:
                return ll
        else:
            if ll == lr - 1:
                return ll
        l = (ll + lr) // 2
    return 0


N = int(input())
S = input()
print(calc(N, S))

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

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

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


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

print(ans)

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

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

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


ans = 0
for i in range(N):
    for j in range(N):
       val = min(abs(i-j),dp[i][j])
       ans = max(val,ans)

print(ans)

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

ans = 0
i = j= 0

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

Solution (Python):
import sys

def main():

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

	maxlen = 0

	for i in range(N):
		SS = S[i:N]
		Z = [0]*len(SS)
		Z[0] = len(SS)
		ZA = [0]*len(SS)
		ZA[0] = min(0,Z[0])
		rt = 0
		lt = 0

		for k in range(1,len(SS)):
			if k>rt:
				n = 0
				while n+k<len(SS) and SS[n]==SS[n+k]:
					n += 1
				Z[k] = n
				ZA[k] = min(k,Z[k])
				if n>0:
					lt = k
					rt = k+n-1
			else:
				p = k-lt
				rlen = rt-k+1

				if Z[p]<rlen:
					Z[k] = Z[p]
					ZA[k] = min(k,Z[k])
				else:
					i = rt+1
					while i<len(SS) and SS[i]==SS[i-k]:
						i += 1
					Z[k] = i-k
					ZA[k] = min(k,Z[k])
					lt = k
					rt = i-1
		
		maxlen = max(maxlen,max(ZA))

	print(maxlen)

if __name__ == "__main__":
    main()

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

ans = 0
len_s = 1
for i in range(N):
    tmp_s = S[i:i+len_s]
    while tmp_s in S[i+len_s:]:
        len_s += 1
        tmp_s = S[i:i+len_s]
        ans += 1
print(ans)

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

dp = [0]*N
j = 1

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

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

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

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

print(ans)

Solution (Python):

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

    """
    他言語ならこれで行けるはずだが、pythonだとTLE
    dp = [[0 for _ in range(N+10)] for _ in range(N+10)]
    for i in reversed(range(N)):
        for j in reversed(range(i+1,N)):
            if S[i] != S[j]:
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i+1][j+1] + 1
            if i >= j: continue
            tmp = min(dp[i][j], j-i)
            ans = max(ans, tmp)
    """
    i = j = 0

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

    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

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

def isOk(leng):
    strList = set()
    que = deque([])
    for left in range(N - leng + 1):
        sub = S[left: left + leng]
        if sub in strList:
            return True
        que.append(sub)
        if len(que) >= leng:
            strList.add(que.popleft())
    return False

ok = 0
ng = N

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

print(ok)

Solution (Python):
from collections import deque

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

def isOk(leng):
    hashList = set()
    que = deque([])
    for left in range(N - leng + 1):
        hs = hash(S[left: left + leng])
        if hs in hashList:
            return True
        que.append(hs)
        if len(que) >= leng:
            hashList.add(que.popleft())
    return False

ok = 0
ng = N

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

print(ok)

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

Solution (Python):
N = int(input())
S = input()
 
 
r = 1
ans = 0
for l in range(N):
 
    while True:
        
 
        if S.rfind(S[l:r+1]) >= r+1:
            r += 1
            ans = max(ans, r-l)
        else:
            break
 
print(ans)

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

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

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







def Z_Algorithm(S):
    N = len(S)
    R = 0 
    L = 0 
    Z = [0 for _ in range(N)] 
    Z[0] = N

    for i in range(1, N):
        if i > R:
            
            L = i
            R = i
            while (R < N and S[R-L] == S[R]):
                R += 1
            Z[i] = R - L
            R -= 1
        else:
            k = i - L
            if Z[k] < R - i + 1:
                
                Z[i] = Z[k]
            else:
                
                L = i
                while (R < N and S[R-L] == S[R]):
                    R += 1
                Z[i] = R - L
                R -= 1
    return Z


def main():
    ans = 0
    for i in range(N):
        Z = Z_Algorithm(S[i:])
        for j, z in enumerate(Z):
            ans = max(ans, min(z, j))
    print(ans)


if __name__ == "__main__":
    main()

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

Solution (Python):
N = int(input())
S = list(map(str, input()))

dp = [[0 for _ in range(N)] for _ in range(N)]
edge_r = N - 1
edge_d = N - 1
for i in reversed(range(N)):
	for j in reversed(range(N)):
		if i == edge_d or j == edge_r:
			if S[i] == S[j]:
				dp[i][j] = 1
			else:
				dp[i][j] = 0
		else:
			if S[i] == S[j]:
				dp[i][j] = dp[i + 1][j + 1] + 1
ans = 0
for i in range(N):
	for j in range(N):
		if i >= j:
			continue
		
		tmp = min(dp[i][j], j - i)
		ans = max(tmp, ans)
		
print(ans)

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

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

for i in range(N-1, -1, -1):
  for j in range(N-1, -1, -1):
    if s[i] != s[j]:
      dp[i][j] = 0
    else:
      dp[i][j] = dp[i+1][j+1] + 1
    
ans = 0
for i in range(N):
  for j in range(N):
    if i >= j:
      continue
    now = min(dp[i][j], j - i)
    ans = max(ans, now)
print(ans)

Solution (Python):







N = int(input())
S = input()
"""
5
ababa
2

13
strangeorange
5
"""





i = 0
j = 1
max_cont = 0

while j < N:
    if S[i:j] in S[j:]:
        max_cont = max(max_cont, len(S[i:j]))
        j += 1
    else:
        i += 1
    if i == j:
        i += 1
        j += 2





print(max_cont)