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: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
dp = [[0 for i in range(5001)] for j in range(5001)]

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

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

Submission status: Time Limit Exceeded

Solution code:
from random import randint


class RollingHash(object):
    mod = 1 << 61 - 1
    base = randint(2, mod - 2)

    def __init__(self, s):
        """
        sに関するローリングハッシュを構築する O(|s|)
        """
        self.s = s
        self.pw = pw = [1] * (len(s) + 1)

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

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

    def hash(self, l, r):
        """ s[l:r] のhash (rはexclusive) O(1) """
        return (self.h[r] - self.h[l] * self.pw[r - l]) % self.mod

    def contains(self, t):
        """
        sがtを含むか O(|s|-|t|)
        tはRollingHashオブジェクト
        """
        slen, tlen = len(self.s), len(t.s)
        if slen < tlen:
            return False
        th = t.hash(0, tlen)
        for i in range(slen - tlen + 1):
            if th == self.hash(i, i + tlen):
                return True
        return False

    def count(self, t):
        """
        s中に含まれるtの数をカウントする O(|s|-|t|)
        tはRollingHashオブジェクト
        """
        slen, tlen = len(self.s), len(t.s)
        if slen < tlen:
            return 0
        cnt = 0
        th = t.hash(0, tlen)
        for i in range(slen - tlen + 1):
            if th == self.hash(i, i + tlen):
                cnt += 1
        return cnt

    def getLCP(self, a, b):
        l = min(len(self.s) + 1 - a, len(self.s) + 1 - b)
        low, high = 0, l
        while high - low > 1:
            mid = (low + high) >> 1
            if self.hash(a, a + mid) != self.hash(b, b + mid):
                high = mid
            else:
                low = mid
        return low


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

rh = RollingHash(S)
ans = 0
for i in range(N):
    for j in range(i + 1, N):
        lcp = rh.getLCP(i, j)
        lcp = min(lcp, j - i)
        ans = max(ans, lcp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def z_algo(S):  # SとS[i:]の最長共通接頭辞 Z Algorithm
    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: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import random


class RollingHash():

    def __init__(self, S, b=-1, m=10**9+7):
        if b < 0:
            b = random.randint(2, m-1)
        self.rh = self.make_hash(S, m, b)
        self.S = S
        self.m = m
        self.b = b
    
    def encode(self, c):
        return ord(c) - ord("a") + 1
    
    def make_hash(self, S, m, b):
        h = 0
        for s in S:
            h *= b
            h %= m
            c = self.encode(s)
            h += c
            h %= m
        return h

    def match(self, T):
        ns = len(self.S)
        nt = len(T)
        rh = self.make_hash(T[:ns], self.m, self.b)
        b_ns = pow(self.b, ns, self.m)

        i = 0
        while i < nt - ns:
            if rh == self.rh:
                yield i
            rh = rh * self.b + self.encode(T[i+ns]) - self.encode(T[i]) * b_ns
            rh %= self.m
            i += 1
        if rh == self.rh:
            yield i

    def find_lcp(self, T):
        ns = len(self.S)
        nt = len(T)
        rh = self.make_hash(T[:ns], self.m, self.b)
        b_ns = pow(self.b, ns, self.m)
        b_inv = pow(self.b, self.m-2, self.m)

        i = 0
        while i < nt - ns:
            sh = self.rh
            th = rh
            j = ns-1
            while j >= 0:
                if sh == th:
                    yield (i, j+1)
                    break
                sh -= self.encode(self.S[j])
                sh *= b_inv
                sh %= self.m
                th -= self.encode(T[i+j])
                th *= b_inv
                th %= self.m
                j -= 1
            rh = rh * self.b + self.encode(T[i+ns]) - self.encode(T[i]) * b_ns
            rh %= self.m
            i += 1
        sh = self.rh
        th = rh
        j = ns-1
        while j >= 0:
            if sh == th:
                yield (i, j+1)
                break
            sh -= self.encode(self.S[j])
            sh *= b_inv
            sh %= self.m
            th -= self.encode(T[i+j])
            th *= b_inv
            th %= self.m
            j -= 1


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


def solve(N, S):
    max_j = 0
    for i in range(1, N):
        rh = RollingHash(S[i:])
        if i >= len(S[i:]):
            for i, j in rh.find_lcp(S[:i]):
                max_j = max(max_j, j)
    return max_j

if __name__ == "__main__":
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

d = defaultdict(list)
for i in range(N):
    for j in range(i+1, N):
        s = S[i:j+1]
        d[s].append([i, j])
ans = 0
for k in d.keys():
    if len(k) <= ans:
        continue
    l = len(d[k])
    for i in range(l):
        for j in range(i+1, l):
            if d[k][i][1] >= d[k][j][0]:
                continue
            else:
                ans = len(k)
print(ans)

Submission status: Time Limit Exceeded

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


def slv(N, S):
    srh = RollingHash(S, num=5)
    h2i = defaultdict(list)
    for i in range(N):
        for j in range(i+1, N+1):
            h = srh.calc(i, j)
            h2i[h].append((i, j))

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


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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline

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

def zalgo(S):
  N = len(S)
  res = [0] * N
  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):
  T = S[i:]
  lcp = zalgo(T)
  for j in range(len(T)):
    l = min(lcp[j],j)
    if res < l:
      res = l

print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline


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


def solve(N, S):
    ans = 0
    l0 = 0
    r0 = 1
    while l0 < N:
        for l1 in range(l0+1, N):
            # find and compare
            if S[l0] == S[l1]:
                k = 1
                while l0 + k < l1 and l1+k < N and S[l0+k] == S[l1+k]:
                    k += 1
                ans = max(ans, k)
                l1 += k
        l0 += 1
    return ans

if __name__ == "__main__":
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline


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


def solve(N, S):
    ans = 0
    l0 = 0
    r0 = 1
    while l0 < N:
        for l1 in range(l0+1, N):
            # find and compare
            if S[l0] == S[l1]:
                k = 1
                while l0 + k < l1 and l1+k < N and S[l0+k] == S[l1+k]:
                    k += 1
                ans = max(ans, k)
        l0 += 1
    return ans

if __name__ == "__main__":
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Time Limit Exceeded

Solution code:
# 左の文字を決め打ちして、右の文字を試していく 右の文字の候補の位置はあらかじめdicで記録

from collections import defaultdict
pos = defaultdict(list)

import sys
readline = sys.stdin.readline

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

for i in range(N):
  pos[S[i]].append(i)

import bisect
def find_tar(s,i): # i + 1文字目以降からsを探す
#  print("pos[s]",pos[s],"から",i+1,"番目以降の最小値を探す")
  j = bisect.bisect_left(pos[s],i+1)
  if j == len(pos[s]):
    return None
  return pos[s][j:] # 全リストを返す

ans = 0
i = 0
while i < N:
  rest = find_tar(S[i],i)
  if rest is None:
    i += 1
    continue
  bestfit = 1
#  print(S[i],rest)
  for j in rest:
    # i,jに同じ文字がある状態
    fit = 1
#    print("i",i,S[i],"j",j,S[j],"からスタート")
    while i + fit < j and j + fit < N:
      if S[i + fit] == S[j + fit]:
#        print("fit",fit,"一致",S[i + fit])
        fit += 1
      else:
        break
    if bestfit < fit:
      bestfit = fit
    if bestfit > ans:
      ans = bestfit
#  print("i",i,"を",i + bestfit,"まで進める")
  i += 1 # i += bestfit

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def z_algorithm(s: str) -> list:
	n = len(s)
	Z = [0] * 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 i + k < n 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:])
	t = max(min(j, z[j]) for j in range(n - i))
	ans = max(ans, t)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def z_algorithm(s: str) -> list:
	n = len(s)
	Z = [0] * 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 i + k < n 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:])
	t = max(min(j, z[j]) for j in range(n - i))
	ans = max(ans, t)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
N=int(sys.stdin.readline().strip())
S=sys.stdin.readline().strip()
ans=0   #文字列一致が存在しない場合は0を返す

for i in range(N):
    s=S[i]
    for j in range(i+1,N):
        while j<N:  #jが文字列からはみ出さない間はループを回す
            t=S[j]
            if s==t:    #文字が一致したら、jを1つ進める
                current_j=j     #文字が一致したら現在のjの位置を記録しておく
                cnt=0
                while s==t:
                    cnt+=1
                    i+=1    #チェックする文字を1文字ずつ右にスライド
                    j+=1    #チェックする文字を1文字ずつ右にスライド
                    if i==current_j:    #iがjのスタート位置と重なったらbreak
                        break
                    elif i<N and j<N:    #i,jともに文字列内だったら
                        s=S[i]
                        t=S[j]
                    else:    #i or jが文字列の右側からはみ出したら
                        break
                ans=max(ans,cnt)
                j=current_j+1 #元のjの値を戻して、1つ進める
            else:    #文字が一致しなかったら、jを1つ進める
                j+=1

print ans

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = list(input())
dp = [[0]*N for _ in range(N)]
dp[N-1][N-1] = 1
for i in range(N-1, -1, -1):
  if S[i] == S[-1]:
    dp[N-1][i] = 1

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

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

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

Submission status: Time Limit Exceeded

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


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

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

l = len(S)

res = 0
for i in range(N):
    for j in range(i + 1, N):
        min_len = min(N - j, j - i)

        left = i
        right = i + min_len

        if S[i] == S[j]:
            while left < right:
                mid = (left + right) // 2
                h1 = rh.get_hash(i, mid)
                h2 = rh.get_hash(j, j + (mid - i))

                if h1 == h2:
                    left = mid + 1
                else:
                    right = mid - 1

            res = max(res, left - i)

print(res)

Submission status: Time Limit Exceeded

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


def suffix_array(S):
    suffix = []
    for i in range(len(S)):
        suffix.append((S[i:], i))

    return sorted(suffix)


def lcp_array(S, SA):
    SA_idx = [i for _, i in SA]
    l = len(S)

    rank = [0] * l
    for i in range(l):
        rank[SA_idx[i]] = i

    h = 0
    LCP = [0] * l
    for i in range(l):
        j = SA_idx[rank[i] - 1]

        if h > 0:
            h -= 1

        while j + h < l and i + h < l:
            if S[j + h] != S[i + h]:
                break
            h += 1

        LCP[rank[i] - 1] = h

    return LCP


SA = suffix_array(S)
LCP = lcp_array(S, SA)

idx2SAidx = [0] * N

for i, (_, j) in enumerate(SA):
    idx2SAidx[j] = i

res = 0
for i in range(N):
    for j in range(i + 1, N):
        k1 = idx2SAidx[i]
        k2 = idx2SAidx[j]

        if k2 < k1:
            k1, k2 = k2, k1

        min_ = N
        for k in range(k1, k2):
            min_ = min(min_, LCP[k])

        if min_ > (j - i):
            min_ = j - i

        res = max(res, min_)


print(res)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
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 ** 32 - 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)    # [h(s[0:0]), h(s[0:1]), h(s[0:2]), h(s[0:3]), ..., h(s[0:size])]
            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

    
    n = ii()
    s = input()
    if len(list(set(list(s)))) == n:
        print(0)
    else:
        # main
        rolling = RollingHash(s)
        calc_interval_hash = rolling.calc_interval_hash    # 定数倍高速化
        for span in range((n // 2) + 1, 0, -1):
            d = dict()
            for i in range(n - span + 1):
                j = i + span
                h = calc_interval_hash(i, j)
                try:
                    right = d[h]
                    if right <= i:
                        print(span)
                        exit()
                except KeyError:
                    d[h] = j

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    

    from random import randint
    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)    # [h(s[0:0]), h(s[0:1]), h(s[0:2]), h(s[0:3]), ..., h(s[0:size])]
            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_hash_str(self, pattern):
            """
            pattern のハッシュを計算
            """
            n = len(pattern)
            hash_num = 0
            for i in range(n):
                hash_num = (hash_num + ord(pattern[i]) * pow(self.base, n - 1 - i, self.hashmod)) % self.hashmod
            return hash_num
        
        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

    
    n = ii()
    s = input()
    if len(list(set(list(s)))) == n:
        print(0)
    else:
        # main
        rolling = RollingHash(s)
        updated = False
        ans = 0
        for span in range((n // 2) + 1, 0, -1):
            d = dict()
            for i in range(n - span + 1):
                j = i + span
                h = rolling.calc_interval_hash(i, j)
                try:
                    right = d[h]
                    if right <= i:
                        ans = span
                        updated = True
                except KeyError:
                    d[h] = j
                if updated:
                    print(ans)
                    exit()


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    

    from random import randint
    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)    # [h(s[0:0]), h(s[0:1]), h(s[0:2]), h(s[0:3]), ..., h(s[0:size])]
            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_hash_str(self, pattern):
            """
            pattern のハッシュを計算
            """
            n = len(pattern)
            hash_num = 0
            for i in range(n):
                hash_num = (hash_num + ord(pattern[i]) * pow(self.base, n - 1 - i, self.hashmod)) % self.hashmod
            return hash_num
        
        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

    
    n = ii()
    s = input()
    if len(list(set(list(s)))) == n:
        print(0)
    else:
        # main
        rolling = RollingHash(s)
        updated = True
        ans = 0
        for span in range(1, (n // 2) + 1):
            if not updated:
                break
            updated = False
            d = dict()
            for i in range(n - span + 1):
                j = i + span
                h = rolling.calc_interval_hash(i, j)
                try:
                    right = d[h]
                    if right <= i:
                        ans = span
                        updated = True
                except KeyError:
                    d[h] = j
                if updated:
                    break
        print(ans)



if __name__ == "__main__":
    main()