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
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


def Z_algo(S):
    n = len(S)
    LCP = [0] * n
    c = 0  
    for i in range(1, n):
        
        if i + LCP[i - c] < c + LCP[c]:
            LCP[i] = LCP[i - c]
        else:
            j = max(0, c + LCP[c] - i)
            while i + j < n and S[j] == S[i + j]:
                j += 1
            LCP[i] = j
            c = i
    LCP[0] = n
    return LCP


n = int(readline())
s = read().rstrip().decode()
ans = 0
for i in range(n):
    for j, m in enumerate(Z_algo(s[i:])):
        ans = max(ans, min(j, m))
print(ans)

Solution (Python):
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)

Solution (Python):


def Z_algorithm(S): 
    n = len(S)
    LCP = [0]*n
    i = 1
    j = 0
    LCP[0] = l = n
    while i < l:
        while i+j < l and S[j] == S[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        LCP[i] = j
        k = 1
        while l-i > k < j - LCP[k]:
            LCP[i+k] = LCP[k]
            k += 1
        i += k
        j -= k
    return LCP 



N = int(input())
S = input()
ans = 0
for i in range(N):
    lcp = Z_algorithm(S[i:])
    for j in range(len(lcp)):
        if lcp[j]<=j:
            ans = max(ans,lcp[j])
print(ans)

Solution (Python):

import sys
from random import randint

def main():
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())   
    
    class RollingHash:
        def __init__(self, s):
            self.s = s    
            self.size = len(s)
            self.hashmod = 2 ** 64 - 1
            self.base = randint(2 ** 10, 2 ** 11)
            self.hash_list = self._make_rolling_hash_list()

        def _make_rolling_hash_list(self):
            hash_list = [0] * (self.size + 1)    
            prev = 0
            for i in range(1, self.size + 1):
                hash_num = (prev * self.base + ord(self.s[i-1])) % self.hashmod
                hash_list[i] = hash_num
                prev = hash_num
            return hash_list
        
        def calc_interval_hash(self, i, j):
            """
            s[i:j] のハッシュを計算
            """
            return (self.hash_list[j] - self.hash_list[i] * pow(self.base, (j - i), self.hashmod)) % self.hashmod

    
    def span_bisect(rolling):
        left = 1    
        right = (n // 2) + 1    
        while right - left > 1:
            d = dict()
            mid_span = left + (right - left) // 2    
            for i in range(n - mid_span + 1):
                j = i + mid_span
                h = rolling.calc_interval_hash(i, j)
                try:
                    first_j = d[h]
                    if first_j <= i:
                        left = mid_span
                        break
                except KeyError:
                    d[h] = j
            else:
                right = mid_span
        return left


    n = ii()
    s = input()
    if len(list(set(list(s)))) == n:
        print(0)
    else:
        
        rolling = RollingHash(s)
        print(span_bisect(rolling))


if __name__ == "__main__":
    main()

Solution (Python):
def rolling_hash(s):
    l = len(s)
    h = [0]*(l + 1)
    v = 0
    for i in range(l):
        h[i+1] = v = (v * base + ord(s[i])) % mod
    return h
def setup_pw(l):
    pw = [1]*(l + 1)
    v = 1
    for i in range(l):
        pw[i+1] = v = v * base % mod
    return pw
def get(h, b, l, r):
    return (h[r] - h[l] * b[r-l]) % mod

def check_bisect(l,h1,b1,h2,b2):
    for j in range(N-2*l+1):
        a1 = get(h1,b1,j,l+j)
        a2 = get(h2,b2,j,l+j)
        for k in range(N-2*l-j+1):
            if a1 == get(h1,b1,j+l+k,2*l+j+k) and a2 == get(h2,b2,j+l+k,2*l+j+k):
                return True
    return False

N = int(input())
S = input()
mod = 1000000007
base = 37
h1 = rolling_hash(S)
b1 = setup_pw(N)
base = 401
h2 = rolling_hash(S)
b2 = setup_pw(N)
left = 1
right = N // 2
finish = False
if N <= 26:
    s = set(list(S))
    if N <= 3:
        if len(s) < N:
            print('1')
        else:
            print('0')
        finish = True
    else:
        if len(s) == N:
            print('0')
            finish = True
while finish == False:
    if left == right:
        print(left)
        finish = True
    elif right - left == 1:
        if check_bisect(right,h1,b1,h2,b2):
            print(right)
        else:
            print(left)
        finish = True
    else:
        mid = (left+right) // 2
        if check_bisect(mid,h1,b1,h2,b2):
            left = mid
        else:
            right = mid - 1

Solution (Python):
import sys
import random
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines






class RollingHash:
    MASK30 = (1 << 30) - 1
    MASK31 = (1 << 31) - 1
    MOD = (1 << 61) - 1
    POSITVIZER = MOD * ((1 << 3) - 1)

    def __init__(self, S):
        
        Base = random.randrange(129, (1 << 61) - 1)
        self.Base = Base

        L = len(S)
        powMemo = [0] * (L + 1)
        rhash = [0] * (L + 1)

        powMemo[0] = 1
        for i in range(1, L + 1):
            powMemo[i] = self.calcMod(self.Mul(powMemo[i - 1], Base))

        for i in range(L):
            rhash[i + 1] = self.calcMod(self.Mul(rhash[i], Base) + ord(S[i]))

        self.powMemo = powMemo
        self.rhash = rhash

    def getHash(self, begin, length):
        r = self.calcMod(
            self.rhash[begin + length]
            + self.POSITVIZER
            - self.Mul(self.rhash[begin], self.powMemo[length])
        )

        return r

    def Mul(self, l, r):
        lu = l >> 31
        ld = l & self.MASK31
        ru = r >> 31
        rd = r & self.MASK31
        middle = ld * ru + lu * rd

        return (
            ((lu * ru) << 1) + ld * rd + ((middle & self.MASK30) << 31) + (middle >> 30)
        )

    def calcMod(self, val):
        val = (val & self.MOD) + (val >> 61)
        if self.MOD <= val:
            val -= self.MOD
        return val


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

RH = RollingHash(S)


def check(n, RH):
    ret = False
    cnt = defaultdict(int)
    for i in range(0, N - n + 1):
        h = RH.getHash(i, n)

        if not cnt[h]:
            cnt[h] = i + 1
        else:
            f = cnt[h]
            if f + n <= i + 1:
                ret = True
                break

    return ret


l = 0  
r = (N // 2) + 1  

while (r - l) != 1:
    mid = (l + r) // 2
    if check(mid, RH):
        l = mid
    else:
        r = mid

print(l)

Solution (Python):
import sys
import random
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines






class RollingHash:
    MASK30 = (1 << 30) - 1
    MASK31 = (1 << 31) - 1
    MOD = (1 << 61) - 1
    POSITVIZER = MOD * ((1 << 3) - 1)

    def __init__(self, S):
        
        Base = random.randrange(129, (1 << 61) - 1)
        self.Base = Base

        L = len(S)
        powMemo = [0] * (L + 1)
        rhash = [0] * (L + 1)

        powMemo[0] = 1
        for i in range(1, L + 1):
            powMemo[i] = self.calcMod(self.Mul(powMemo[i - 1], Base))

        for i in range(L):
            rhash[i + 1] = self.calcMod(self.Mul(rhash[i], Base) + ord(S[i]))

        self.powMemo = powMemo
        self.rhash = rhash

    def getHash(self, begin, length):
        r = self.calcMod(
            self.rhash[begin + length]
            + self.POSITVIZER
            - self.Mul(self.rhash[begin], self.powMemo[length])
        )

        return r

    def Mul(self, l, r):
        lu = l >> 31
        ld = l & self.MASK31
        ru = r >> 31
        rd = r & self.MASK31
        middle = ld * ru + lu * rd

        return (
            ((lu * ru) << 1) + ld * rd + ((middle & self.MASK30) << 31) + (middle >> 30)
        )

    def calcMod(self, val):
        val = (val & self.MOD) + (val >> 61)
        if self.MOD <= val:
            val -= self.MOD
        return val


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

RH = RollingHash(S)


def check(n, RH):
    ret = False
    cnt = defaultdict(int)
    for i in range(0, N - n + 1):
        h = RH.getHash(i, n)

        if not cnt[h]:
            cnt[h] = i + 1
        else:
            f = cnt[h]
            if f + n <= i + 1:
                ret = True
                break

    return ret


l = 0  
r = (N // 2) + 1  

while (r - l) != 1:
    mid = (l + r) // 2
    if check(mid, RH):
        l = mid
    else:
        r = mid

print(l)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines







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

ans = 0


def Z_Algorithm(S):
    L = len(S)
    Z = [0] * L
    Z[0] = L

    i = 1
    j = 0

    while i < L:
        
        
        while i + j < L and S[j] == S[i + j]:
            j += 1
        Z[i] = j

        
        if j == 0:
            i += 1
            continue

        
        
        k = 1
        while k < j and k + Z[k] < j:
            Z[i + k] = Z[k]
            k += 1

        i += k
        j -= k

    return Z


ans = 0
for i in range(N):
    Z = Z_Algorithm(S[i:])

    L = len(Z)
    for j in range(1, L):
        l = min(Z[j], j)
        ans = max(l, ans)

print(ans)

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

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

ans = 0

for l2 in range(1, N):
    same_len = 0
    for i in range(N):
        if N - 1 < l2 + i:
            continue

        if S[i] == S[l2 + i]:
            same_len += 1
        else:
            same_len = min(l2, same_len)
            ans = max(ans, same_len)
            same_len = 0
    same_len = min(l2, same_len)
    ans = max(same_len, ans)

print(ans)

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

suc=[0]*(n-1)
ans=0
for i,c in enumerate(s):
    for j in range(n-1):
        idx=(i+1+j)%n
        if idx==0:
            suc[j]=0
        if c==s[idx]:
            suc[j]+=1
            suc[j]=min(suc[j],j+1,n-1-j)
            ans=max(ans,suc[j])
        else:
            suc[j]=0
print(ans)

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

    
    

    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)

if __name__ == '__main__':
    main()

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

    
    

    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)

if __name__ == '__main__':
    main()

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

import random
base1 = 1007
mod1 = 10**9+7
modTank1 = [3000012541,3000012553,3000012563,3000012649,3000012683,3000012709]
mod1 = modTank1[random.randint(0,5)]
base1 = 1007
mod1 = 10**9+7
hash1 = [0]*(n+1)
power1 = [1]*(n+1)
for i,e in enumerate(s):
    hash1[i+1] = (hash1[i]*base1 + ord(e))%mod1
    power1[i+1] = (power1[i]*base1)%mod1
def rolling_hash(i, j):
    return (hash1[j]-hash1[i]*power1[j-i]%mod1)%mod1



hash = set()
l = 0
r = n
while r - l > 1:
    m = l + (r-l)//2
    hash = dict()
    flag = 0
    for i in range(n-m+1):
        h = rolling_hash(i, i+m)
        if h not in hash.keys():
            hash[h] = i
        elif hash[h]+m <= i:
            flag = 1
            break
    if flag == 1:
        l = m
    else:
        r = m

print(l)

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(input())
    s = input()
    x = 1

    sn = [ord(c) - 96 + x for c in s]

    lmax = n // 2
    m1 = 10 ** 9 + 7
    m2 = 2 ** 61 - 1

    ans = 0

    ng = n + 1
    ok = 0

    while abs(ng - ok) > 1:
        l = (ng + ok) // 2
        found = False

        appeared = set()
        diff = pow(m1, l - 1, m2)

        h_init = 0

        for i in range(l):
            h_init += sn[i] * pow(m1, l - 1 - i, m2)
            h_init %= m2

        hashlist = [0] * n
        hashlist[l - 1] = h_init
        h = h_init

        for i in range(l, n):
            h -= sn[i - l] * diff
            h *= m1
            h += sn[i]
            h %= m2
            hashlist[i] = h
            if i - l >= 0:
                appeared.add(hashlist[i - l])
            if h in appeared:
                found = True
                break

        if found:
            ok = l
        else:
            ng = l

    print(ok)


if __name__ == '__main__':
    main()

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

def z_alg(S):
  N=len(S)
  Z=[N]+[0]*(N-1)
  i,j=1,0
  while i<N:
    while i+j<N and S[j]==S[i+j]:
      j+=1
    if not j:
      i+=1
      continue
    Z[i]=j
    k=1
    while N-i>k and k<j-Z[k]:
      Z[i+k]=Z[k]
      k+=1
    i+=k
    j-=k
  return Z

answer=0
for i in range(N):
  zlist=z_alg(S[i:])
  
  for j in range(N-i):
    if j>=zlist[j] and answer<zlist[j]:
      answer=zlist[j]
      
print(answer)

Solution (Python):
n=int(input())
S=list(input())
dp=[[0]*(n+1) for i in range(n+1)]
for i in range(1,n):
  for j in range(i+1,n+1):
    if S[i-1]==S[j-1]:
      if j-i<dp[i-1][j-1]+1:
        dp[i][j]=dp[i-1][j-1]
      else:
        dp[i][j]=dp[i-1][j-1]+1
ans=0
for i in range(n+1):
  for j in range(n+1):
    if dp[i][j]>ans:
      ans=dp[i][j]
print(ans)

Solution (Python):
n = int(input())
s = input()
Z = [0 for _ in range(n)]
ans = 0
for begin in range(n):
    Z[begin] = n-begin
    i = begin + 1
    j = 0
    while i < n:
        while i+j < n and s[begin+j] ==s[i+j]:
            j += 1
        Z[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < n and k+Z[begin+k] < j:
            Z[i+k] = Z[begin+k]
            k += 1
        i += k
        j -= k
    for i in range(begin,n):
        l = min(i-begin,Z[i])
        ans = max(ans,l)
print(ans)

Solution (Python):
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):
        c = s[i]
        equal = (c == s)

        dp[i+1][1:] += equal
        dp[i+1][1:] += equal * dp[i][:-1]


    dp = np.minimum(dp, t)


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

if __name__ == "__main__":
    main()

Solution (Python):


def Z_algorithm(s):
    N = len(s)
    Z_alg = [0]*N

    Z_alg[0] = N
    i = 1
    j = 0
    while i < N:
        while i+j < N and s[j] == s[i+j]:
            j += 1
        Z_alg[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k + Z_alg[k]<j:
            Z_alg[i+k] = Z_alg[k]
            k += 1
        i += k
        j -= k
    return Z_alg

N=int(input())
S=input()
S=[S[i] for i in range(0,N)]

ans=0
for i in range(0,N):
    data=Z_algorithm(S)
    for j in range(0,len(data)):
        ans=max(min(data[j],j),ans)
    S=S[1:]
print(ans)

Solution (Python):



"""
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)
    
    l += 1
    if l == r:
        r = l + 1

print(ans)

Solution (Python):




def z_algorithm(s):
    N = len(s)
    z_alg = [0]*N
    z_alg[0] = N
    i = 1
    j = 0
    
    while i < N:
        while i+j < N and s[j] == s[i+j]: 
            j += 1
        z_alg[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k+z_alg[k] < j: 
            z_alg[i+k] = z_alg[k]
            k += 1
        i += k
        j -= k
    return z_alg

n = int(input())
S = input()
max_ = 0
for i in range(n):
    k = S[i:len(S)]
    li = z_algorithm(k)
    for j in range(len(li)):
        if li[j] < j+1:
            max_ = max(max_, li[j])
print(max_)

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

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


class RollingHash:
    base1 = 1007
    base2 = 2009
    mod1 = 10 ** 9 + 7
    mod2 = 10 ** 9 + 9
    
    def __init__(self, s):
        self.s = s
        
        n = len(s)
        self.hash1 = [0] * (n + 1)
        self.hash2 = [0] * (n + 1)
        self.power1 = [1] * (n + 1)
        self.power2 = [1] * (n + 1)
        for i in range(n):
            self.hash1[i + 1] = (self.hash1[i] * self.base1 + ord(s[i])) % self.mod1
            self.hash2[i + 1] = (self.hash2[i] * self.base2 + ord(s[i])) % self.mod2
            self.power1[i + 1] = (self.power1[i] * self.base1) % self.mod1
            self.power2[i + 1] = (self.power2[i] * self.base2) % self.mod2
            
    def get_hash(self, l, r):
        """Gets hash of S[left:right]"""
        res1 = self.hash1[r] - self.hash1[l] * self.power1[r - l] % self.mod1
        if res1 < 0:
            res1 += self.mod1
        res2 = self.hash2[r] - self.hash2[l] * self.power2[r - l] % self.mod2
        if res2 < 0:
            res2 += self.mod2
            
        return (res1, res2)
    
    def get_lcp(self, a, b):
        """Gets lcp of S[a:] and S[b:]"""
        low = 0
        high = min(len(self.hash1) - a, len(self.hash1) - b)
        
        while high - low > 1:
            mid = (low + high) >> 1
            if self.get_hash(a, a + mid) != self.get_hash(b, b + mid):
                high = mid
            else:
                low = mid
                
        return low


def check(d):
    ctr = {}
    for i in range(N - d + 1):
        p = rh.get_hash(i, i + d)
        if p in ctr:
            if i - ctr[p] >= d:
                return True
        else:
            ctr[p] = i
            
    return False


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

print(left)

Solution (Python):
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)

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

def z_algorithm(s):
    n = len(s)
    res = [0] * n
    i = 1
    j = 0
    while i < n:
        while i + j < n and s[j] == s[i + j]:
            j += 1
            
        res[i] = j
        if j == 0:
            i += 1
            continue

        
        k = 1
        while i + k < n and k + res[k] < j:
            res[i + k] = res[k]
            k += 1
        
        i += k
        j -= k
        
    return res


res = 0
for i in range(N):
    lcp = z_algorithm(S[i:])
    for j in range(N - i):
        res = max(res, min(lcp[j], j))
        
print(res)

Solution (Python):
def ok(k):
    
    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()

l, r = 0, n+1
while r-l > 1:
    c = (l+r)//2
    if ok(c):
        l = c
    else:
        r = c
print(l)

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,j-i)
        j+=1
    else:
        i+=1

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

Solution (Python):
def ok(l):
    
    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()

l, r = 0, n+1
while r-l > 1:
    c = (l+r)//2
    if ok(c):
        l = c
    else:
        r = c
print(l)

Solution (Python):
def ok(l):
    
    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()

l, r = 0, n+1
while r-l > 1:
    c = (l+r)//2
    if ok(c):
        l = c
    else:
        r = c
print(l)

Solution (Python):
def ok(l):
    
    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()

l, r = 0, n+1
while r-l > 1:
    c = (l+r)//2
    if ok(c):
        l = c
    else:
        r = c
print(l)

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

def solve(SS):
	n = len(SS)
	Z = [0] * n
	Z[0] = n
	i, j = 1, 0
	while i < n:
		while (i + j < n) and (SS[j] == SS[i + j]):
			j += 1
		Z[i] = j
		if j == 0:
			i += 1
			continue
		else:
			k = 1
			while (i + k < n) and (k + Z[k] < j):
				Z[i + k] = Z[k]
				k += 1
			i += k
			j -= k

	out = 0
	for i in range(n):
		tmp = min(Z[i], i)
		out = max(out, tmp)
	return out

ans = 0
for i in range(N):
	ans = max(ans, solve(S[i:]))

print(ans)

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

def judge(x):
    d = defaultdict(int)
    
    for i in range(N-x+1):
        k = hash(S[i:i+x])
        
        if k not in d:
            d[k] = i
        else:
            if i-d[k]>=x:
                return True
    
    return False

def binary_search():
    l, r = 0, N
    
    while l<=r:
        m = (l+r)//2
        
        if judge(m):
            l = m+1
        else:
            r = m-1
    
    return r

N = int(input())
S = input()[:-1]

print(binary_search())

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
N = int(input())
S = input()
def f(m):
    res = False
    hs = []
    for i in range(0,N-m+1):
        hs.append(hash(S[i:i+m]))
    for i in range(0,N-m+1):
        if hash(S[i:i+m]) in hs[i+m:]:
            res = True
            break
    return res

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

Solution (Python):
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)

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

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

mod = 10**20 + 7
base = 12345

def ok(l):
    array = {}
    rolling_hash = 0
    for i in range(n):
        rolling_hash *= base
        rolling_hash += ord(s[i])
        if i - l >= 0:
            rolling_hash -= ord(s[i-l]) * pow(base, l, mod)
        rolling_hash %= mod
        if i >= l-1:
            if rolling_hash in array.keys():
                array[rolling_hash].append(i)
            else:
                array[rolling_hash] = [i]
    for check in array.values():
        if max(check) - min(check) >= l:
            return True
    return False

top = n
bottom = 0

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

Solution (Python):
def zarg(N, S):
    Z = [0] * N
    Z[0] = N
    i = 1
    j = 0
    while i < N:
        while i+j < N and S[j] == S[i+j]:
            j += 1
        Z[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while k + Z[k] < j:
            Z[i + k] = Z[k]
            k += 1
        i += k
        j -= k
    M = 0
    for i in range(1,N):
        M = max(M, min(Z[i], i))
    return M

N = int(input())
S = input()
ans = 0
for i in range(N):
    s = S[i:]
    ans = max(ans, zarg(N-i, s))
print(ans)

Solution (Python):
def z_algorithm(S):
    l=len(S)
    A=[0]*n
    i=1;j=0
    while i<l:
        while(i+j<l and S[j]==S[i+j]):
            j+=1
        A[i]=j
        if j==0:
            i+=1
            continue
        k=1
        while i+k<l 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):
    a=z_algorithm(s[i:])
    for j in range(len(a)):
        if(a[j]<=j):
            ans=max(ans,a[j])
print(ans)

Solution (Python):

"""
最長共通部分文字列を求める問題。
最長共通接頭辞(z-algorithm)を用いて、O(N**2)で求まる。
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

def Z_algorithm(s):
    N = len(s)
    Z_alg = [0]*N
    Z_alg[0] = N
    i = 1
    j = 0
    res = 0 
    while i < N:
        while i+j < N and s[j] == s[i+j]:
            j += 1
        if i+1 > j:
            res = max(res,j)
        else:
            res = max(res,i)
        Z_alg[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k + Z_alg[k]<j:
            Z_alg[i+k] = Z_alg[k]
            k += 1
        i += k
        j -= k
    return res
n = int(readline())
s = readline().rstrip().decode('utf-8')
ans = 0
i = 0
while True:
    ans = max(ans,Z_algorithm(s))
    if len(s)<=2:
        break
    s = s[1:]
    i += 1

print(ans)

Solution (Python):




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





ans = 0
for num in range(n - 1):
    S = s[num:]
    A = [0] * (n - num)
    A[0] = n - num
    i = 1
    j = 0
    while i < n - num:
        while i + j < n - num and S[j] == S[i + j]:
            j += 1
        A[i] = j
        ans = max(ans, min(i, j))
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < n - num and k + A[k] < j:
            A[i + k] = A[k]
            ans = max(ans, min(k, A[k]))
            k += 1
        i += k
        j -= k
print(ans)

Solution (Python):
def zalgo(S):
    
    n = len(S)
    A = [0] * n
    j = 0
    for i in range(1, n):
        if i+A[i-j] < j+A[j]:
            A[i] = A[i-j]
        else:
            k = max(0, A[j]-i+j)
            while i+k < n and S[k] == S[i+k]:
                k += 1
            A[i] = k
            j = i
    A[0] = n
    return A


n = int(input())
S = input()
l = 0
for i in range(n):
    A = zalgo(S[i:])
    B = [min(j, a) for j, a in enumerate(A)]
    l = max(l, max(B))
print(l)