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



Sample input:
5
ababa


Sample output:
2

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

def judge(x):
    d = defaultdict(int)
    
    for i in range(N-x+1):
        k = S[i:i+x]
        
        if k in d:
            if i>=d[k]+x:
                return True
        else:
            d[k] = i
    
    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())

Submission status: Accepted

Solution code:
def z_algorithm(s):
    n = len(s)
    z = [0 for i in range(n)]
    z[0] = n
    i, j = 1, 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 < j and k + z[k] < j:
            z[i+k] = z[k]
            k += 1
        i += k
        j -= k
    return z

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

ans = 0
for i in range(n):
    z = z_algorithm(s[i:])
    for j in range(len(z)):
        if z[j] <= j:
            ans = max(ans, z[j])
print(ans)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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 in d:
            if i>=d[k]+x:
                return True
        else:
            d[k] = i
    
    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())

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

def judge(x):
    d = defaultdict(int)
    q = deque([])
    
    for i in range(x):
        q.append(S[i])
        
    d[''.join(q)] = 0
    
    for i in range(x, N):
        q.append(S[i])
        q.popleft()
        k = ''.join(q)
        
        if k in d:
            if i-x+1-d[k]>=x:
                return True
        else:
            d[k] = i-x+1
    
    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())

Submission status: Accepted

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

def z_algorithm(s):
    n = len(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 i+k < n and k+Z[k] < j:
            Z[i+k] = Z[k]
            k += 1
        i += k
        j -= k
    return Z

s = list(s)
s.reverse()
import copy
ans = 0
for i in range(n):
    if i != 0:
        s.pop()
    t = copy.copy(s)
    t.reverse()
    t = ''.join(t)
    Z = z_algorithm(t)
    for i, z in enumerate(Z):
        ans = max(ans, min(i, z))
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    n=int(readline())
    s=readline().strip()

    ans=0
    for i in range(n):
        res=z_algorithm(s[i:])
        for j in range(n-i):
            ans=max(ans,min(res[j],j))

    print(ans)

def z_algorithm(s):
    n=len(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 i+k<n and k+z[k]<j:
            z[i+k]=z[k]
            k+=1
        i+=k
        j-=k
    return z

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

N = ri()
S = rs()

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

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

def Zalgo(S):
    N = len(S)
    A = [0]*N

    froms = -1
    lasts = -1
    for i in range(1, N):
        same = 0
        if froms != -1:
            same = min(A[i-froms], lasts-i)
            same = max(0, same)
        while i+same<N and S[same] == S[i+same]:
            same += 1
        
        if i+same > lasts:
            lasts = i+same
            froms = i
        A[i] = same
    A[0] = N
    return A

N = int(input())
S = input().rstrip()

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

Submission status: Accepted

Solution code:
m = int(input())
s = input().rstrip()
def zalgo(s):
  n = len(s)
  lcp = [0]*n
  lcp[0] = n
  i = 1
  j = 0
  while i < n:
    while i+j < n and s[j] == s[i+j]:
      j += 1
    lcp[i] = j
    if j == 0:
      i += 1
      continue
    k = 1
    while i+k < n and k+lcp[k] < j:
      lcp[i+k] = lcp[k]
      k += 1
    i += k
    j -= k
  return lcp
ans = 0
for i in range(m):
  ss = s[i:]
  lcp = zalgo(ss)
  ans = max([ans]+[min(lcp[j],j) for j in range(m-i)])
print(ans)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
  n = int(input())
  S = input()
  ans = 0
  dp = [[0]*n for _ in range(n)]
  for j in range(n-1, 0, -1):
    for i in range(j-1, -1, -1):
      if j == n-1:
        dp[i][j] = int(S[i] == S[j])
      else:
        if S[i] == S[j]:
          dp[i][j] = dp[i+1][j+1] + 1
      ans = max(ans, min(dp[i][j], j-i))
  print(ans)
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Accepted

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

def Z_algo(S):
    n = len(S)
    LCP = [0]*n
    i = 1
    j = 0
    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
  
ans = 0
for i in range(n):
  z = Z_algo(s[i:])
  for i,zi in enumerate(z):
    ans = max(ans,min(i,z[i]))
    
print(ans)

Submission status: Accepted

Solution code:
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)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Accepted

Solution code:
n = int(input())
s = input()
ret = 0
for d in range(1, n - 1):
    l = 0
    for i in range(n - d):
        if s[i] == s[i + d]:
            l += 1
        else:
            l = 0
        ret = max(ret, min(l, d))
print(ret)

Submission status: Accepted

Solution code:
def z_algo(S):
    N = len(S)
    A = [0] * N
    i = 1
    j = 0
    A[0] = l = len(S)
    while i < l:
        while i + j < l and S[j] == S[i + j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i + k] = A[k]
            k += 1
        i += k
        j -= k
    return A


def resolve():
    n = int(input())
    s = input()
    ans = 0
    for i in range(n):
        a = z_algo(s[i:])
        for index, j in enumerate(a):
            if j <= index:
                ans = max(ans, j)
    print(ans)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
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] = dp[i+1][j+1] + 1
        else:
            dp[i][j] = 0

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

Submission status: Accepted

Solution code:
import math

def main():
    n = int(input())
    s = input()
    ans = solve(n, s)
    print(ans)


def solve(n, s):
    ans = 0
    for i in range(n - 1):
        tmp = Z(s[i:])
        t = [min(tmp[j], j)for j in range(n - i)]
        ans = max(ans, max(t))
        #print(tmp)
    return ans

def Z(s):
    l = len(s)
    ans = [l for _ in range(l)]

    i, j = 1, 0
    while i < l:
        while i + j < l and s[j] == s[i + j] :
            j += 1
        ans[i] = j

        if j == 0:
            i += 1
            continue

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit
# getarr = lambda _f: list(map(_f, input().split()))

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

s += '_'

ans = 0
for i in range(1, n):
    tmp = 0
    for j in range(i, n + 1):
        if s[j - i] == s[j]:
            tmp += 1
            if tmp >= i:
                ans = i
                break
        else:
            ans = max(ans, tmp)
            tmp = 0

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import Counter, defaultdict
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline


class RollingHash():
    """
    Original code is https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
    """
    class RH():
        def __init__(self, s, base, mod):
            self.base = base
            self.mod = mod
            self.rev = pow(base, mod-2, mod)

            l = len(s)
            self.h = h = [0]*(l+1)
            tmp = 0
            for i in range(l):
                num = ord(s[i])
                tmp = (tmp*base + num) % mod
                h[i+1] = tmp

            self.pw = pw = [1]*(len(s)+1)
            v = 1
            for i in range(l):
                pw[i+1] = v = v * base % mod

        def calc(self, l, r):
            return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod

    @staticmethod
    def gen(a, b, num):
        result = set()
        while 1:
            import random
            import math
            random.seed()
            while 1:
                v = random.randint(a, b)//2*2+1
                if v not in result:
                    break
            for x in range(3, int(math.sqrt(v))+1, 2):
                if v % x == 0:
                    break
            else:
                result.add(v)
                if len(result) == num:
                    break
        return result

    def __init__(self, s, rand=False, num=5):
        if rand:
            bases = RollingHash.gen(2, 10**3, num)
        else:
            assert num <= 10
            bases = [641, 103, 661, 293, 547, 311, 29, 457, 613, 599][:num]

        MOD = 10**9+7
        self.rhs = [self.RH(s, b, MOD) for b in bases]

    def calc(self, l, r):
        return tuple(rh.calc(l, r) for rh in self.rhs)


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo


def slv(N, S):
    srh = RollingHash(S)

    def f(m):
        h2i = defaultdict(list)
        for i in range(N-m+1):
            h2i[srh.calc(i, i+m)].append(i)

        for l in h2i.values():
            n = l[-1] - l[0]
            if n >= m:
                return 0
        return 1

    return Bisect(f).bisect_right(0, 1, N//2+1) - 1


def main():
    N = int(input())
    S = input()
    print(slv(N, S))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import Counter, defaultdict
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline


class RollingHash():
    """
    Original code is https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
    """
    class RH():
        def __init__(self, s, base, mod):
            self.base = base
            self.mod = mod
            self.rev = pow(base, mod-2, mod)

            l = len(s)
            self.h = h = [0]*(l+1)
            tmp = 0
            for i in range(l):
                num = ord(s[i])
                tmp = (tmp*base + num) % mod
                h[i+1] = tmp

            self.pw = pw = [1]*(len(s)+1)
            v = 1
            for i in range(l):
                pw[i+1] = v = v * base % mod

        def calc(self, l, r):
            return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod

    @staticmethod
    def gen(a, b, num):
        result = set()
        while 1:
            import random
            import math
            random.seed()
            while 1:
                v = random.randint(a, b)//2*2+1
                if v not in result:
                    break
            for x in range(3, int(math.sqrt(v))+1, 2):
                if v % x == 0:
                    break
            else:
                result.add(v)
                if len(result) == num:
                    break
        return result

    def __init__(self, s, rand=False, num=5):
        if rand:
            bases = RollingHash.gen(2, 10**3, num)
        else:
            assert num <= 10
            bases = [641, 103, 661, 293, 547, 311, 29, 457, 613, 599][:num]

        MOD = 10**9+7
        self.rhs = [self.RH(s, b, MOD) for b in bases]

    def calc(self, l, r):
        return tuple(rh.calc(l, r) for rh in self.rhs)


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo


def slv(N, S):
    srh = RollingHash(S)

    def f(m):
        h2i = defaultdict(list)
        for i in range(N-m+1):
            j = i + m
            h = srh.calc(i, j)
            h2i[h].append(i)

        for l in h2i.values():
            n = l[-1] - l[0]
            if n >= m:
                return 0
        return 1

    return Bisect(f).bisect_right(0, 1, N//2+1) - 1


def main():
    N = int(input())
    S = input()
    print(slv(N, S))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import Counter, defaultdict
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline


class RollingHash():
    """
    Original code is https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
    """
    class RH():
        def __init__(self, s, base, mod):
            self.base = base
            self.mod = mod
            self.rev = pow(base, mod-2, mod)

            l = len(s)
            self.h = h = [0]*(l+1)
            tmp = 0
            for i in range(l):
                num = ord(s[i])
                tmp = (tmp*base + num) % mod
                h[i+1] = tmp

            self.pw = pw = [1]*(len(s)+1)
            v = 1
            for i in range(l):
                pw[i+1] = v = v * base % mod

        def calc(self, l, r):
            return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod

    @staticmethod
    def gen(a, b, num):
        result = set()
        while 1:
            import random
            import math
            random.seed()
            while 1:
                v = random.randint(a, b)//2*2+1
                if v not in result:
                    break
            for x in range(3, int(math.sqrt(v))+1, 2):
                if v % x == 0:
                    break
            else:
                result.add(v)
                if len(result) == num:
                    break
        return result

    def __init__(self, s, rand=False, num=5):
        if rand:
            bases = RollingHash.gen(2, 10**3, num)
        else:
            assert num <= 10
            bases = [641, 103, 661, 293, 547, 311, 29, 457, 613, 599][:num]

        MOD = 10**9+7
        self.rhs = [self.RH(s, b, MOD) for b in bases]

    def calc(self, l, r):
        return tuple(rh.calc(l, r) for rh in self.rhs)


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo


def slv(N, S):
    srh = RollingHash(S)

    def f(m):
        h2i = defaultdict(list)
        for i in range(N-m+1):
            j = i + m
            h = srh.calc(i, j)
            h2i[h].append(i)

        for l in h2i.values():
            l0 = l[0]
            for i in range(1, len(l)):
                n = l[i] - l0
                if n >= m:
                    return 0
        return 1

    return Bisect(f).bisect_right(0, 1, N//2+1) - 1


def main():
    N = int(input())
    S = input()
    print(slv(N, S))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import Counter, defaultdict
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline


class RollingHash():
    """
    Original code is https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
    """
    class RH():
        def __init__(self, s, base, mod):
            self.base = base
            self.mod = mod
            self.rev = pow(base, mod-2, mod)

            l = len(s)
            self.h = h = [0]*(l+1)
            tmp = 0
            for i in range(l):
                num = ord(s[i])
                tmp = (tmp*base + num) % mod
                h[i+1] = tmp

            self.pw = pw = [1]*(len(s)+1)
            v = 1
            for i in range(l):
                pw[i+1] = v = v * base % mod

        def calc(self, l, r):
            return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod

    @staticmethod
    def gen(a, b, num):
        result = set()
        while 1:
            import random
            import math
            random.seed()
            while 1:
                v = random.randint(a, b)//2*2+1
                if v not in result:
                    break
            for x in range(3, int(math.sqrt(v))+1, 2):
                if v % x == 0:
                    break
            else:
                result.add(v)
                if len(result) == num:
                    break
        return result

    def __init__(self, s, rand=False, num=5):
        if rand:
            bases = RollingHash.gen(2, 10**3, num)
        else:
            assert num <= 10
            bases = [641, 103, 661, 293, 547, 311, 29, 457, 613, 599][:num]

        MOD = 10**9+7
        self.rhs = [self.RH(s, b, MOD) for b in bases]

    def calc(self, l, r):
        return tuple(rh.calc(l, r) for rh in self.rhs)


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo


def slv(N, S):
    srh = RollingHash(S, rand=True, num=2)

    def f(m):
        h2i = defaultdict(list)
        for i in range(N-m+1):
            j = i + m
            h = srh.calc(i, j)
            h2i[h].append(i)

        for l in h2i.values():
            l0 = l[0]
            for i in range(1, len(l)):
                n = l[i] - l0
                if n >= m:
                    return 0
        return 1

    return Bisect(f).bisect_right(0, 1, N//2+1) - 1


def main():
    N = int(input())
    S = input()
    print(slv(N, S))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import Counter, defaultdict
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline


class RollingHash():
    """
    Original code is https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
    """
    class RH():
        def __init__(self, s, base, mod):
            self.base = base
            self.mod = mod
            self.rev = pow(base, mod-2, mod)

            l = len(s)
            self.h = h = [0]*(l+1)
            tmp = 0
            for i in range(l):
                num = ord(s[i])
                tmp = (tmp*base + num) % mod
                h[i+1] = tmp

            self.pw = pw = [1]*(len(s)+1)
            v = 1
            for i in range(l):
                pw[i+1] = v = v * base % mod

        def calc(self, l, r):
            return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod

    @staticmethod
    def gen(a, b, num):
        import random
        import math
        result = set()
        while 1:
            while 1:
                v = random.randint(a, b)//2*2+1
                if v not in result:
                    break
            for x in range(3, int(math.sqrt(v))+1, 2):
                if v % x == 0:
                    break
            else:
                result.add(v)
                if len(result) == num:
                    break
        return result

    def __init__(self, s, rand=False, num=5):
        if rand:
            bases = RollingHash.gen(2, 10**3, num)
        else:
            assert num <= 10
            bases = [641, 103, 661, 293, 547, 311, 29, 457, 613, 599][:num]

        MOD = 10**9+7
        self.rhs = [self.RH(s, b, MOD) for b in bases]

    def calc(self, l, r):
        return tuple(rh.calc(l, r) for rh in self.rhs)


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo


def slv(N, S):
    srh = RollingHash(S, num=5)

    def f(m):
        h2i = defaultdict(list)
        for i in range(N-m+1):
            j = i + m
            h = srh.calc(i, j)
            h2i[h].append(i)

        for l in h2i.values():
            l0 = l[0]
            for i in range(1, len(l)):
                n = l[i] - l0
                if n >= m:
                    return 0
        return 1

    return Bisect(f).bisect_right(0, 1, N//2+1) - 1


def main():
    N = int(input())
    S = input()
    print(slv(N, S))


if __name__ == '__main__':
    main()