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:
n = int(input())
s = input()


def arihon_SA(T):
    rank = [0] * (n + 1)
    SA = [0] * (n + 1)
    temp = [0] * (n + 1)

    def rank_calc(i):
        res1 = rank[i]
        res2 = -1
        if i + k <= n:
            res2 = rank[i + k]
        return (res1, res2)

    for i in range(n + 1):
        SA[i] = i
        if i < n:
            rank[i] = ord(T[i])
        else:
            rank[i] = -1
    k = 1

    while k <= n:
        SA.sort(key=rank_calc)
        temp[SA[0]] = 0
        for i in range(1, n + 1):
            temp[SA[i]] = temp[SA[i - 1]]
            if rank_calc(SA[i - 1]) < rank_calc(SA[i]):
                temp[SA[i]] += 1
        rank = temp[::]
        k *= 2

    return SA


# SAとsからSA[i+1],SA[i]の共通接頭辞LCP[i]を求めたい。
# len(s)=nならlen(SA)=n+1
# LCP[0]は必ず0
def arihon_LCP(s, SA):
    num = len(s)
    rank = [0] * (num + 1)
    LCP = [-1] * (num)
    for i in range(num + 1):
        rank[SA[i]] = i
    h = 0
    LCP[0] = 0
    for i in range(num):
        j = SA[rank[i] - 1]
        if h > 0:
            h -= 1
        while j + h < num and i + h < num:
            if s[j + h] != s[i + h]:
                break
            else:
                h += 1
        LCP[rank[i] - 1] = h
    return LCP


SA = arihon_SA(s)
LCP = arihon_LCP(s, SA)

# sparse table
num = n.bit_length()
ST = [[0] * (num + 1) for _ in range(n)]

for i in range(n):
    ST[i][0] = LCP[i]

for j in range(num):
    for i in range(n):
        ST[i][j + 1] = ST[i][j]
        delta = 1 << j
        if i + delta < n:
            ST[i][j + 1] = min(ST[i][j + 1], ST[i + delta][j])


def query(a, b):
    if a > b:
        a, b = b, a
    d = (b - a).bit_length() - 1
    delta = 1 << d
    res = min(ST[a][d], ST[b - delta][d])
    return res


ans = 0
for i in range(n):
    for j in range(i + 1, n + 1):
        a = SA[i]
        b = SA[j]
        temp = query(i, j)
        if abs(b - a) >= temp:
            ans = max(ans, temp)
print(ans)

Submission status: Accepted

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


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


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


# rolling hash実装

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

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


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


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


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


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

ng = n
ok = 0


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


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

print(ok)

Submission status: Accepted

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def z_algorithm(s):
    ma = 0
    prefix = [0]*len(s)
    j = 0
    for i in range(1,len(s)):
        if i+prefix[i-j] < j+prefix[j]:
            prefix[i] = prefix[i-j]
        else:
            k = max(0,j+prefix[j]-i)
            while i+k < len(s) and s[k] == s[i+k]:
                k += 1
            prefix[i] = k
            j = i
    prefix[0] = len(s)
    for i,pi in enumerate(prefix):
        if i < pi:
            prefix[i] = i
    for i in prefix:
        if ma < i:
            ma = i
    return ma

def main():
    n = int(ipt())
    s = input()
    ma = 0
    for i in range(n):
        pf = z_algorithm(s[i::])
        if ma < pf:
            ma = pf

    print(ma)

    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    def ZAlgorithm(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

    n = int(input())
    S = input()

    res = 0
    for i in range(n):
        T = S[i:]
        LCP = ZAlgorithm(T)
        for j in range(len(T)):
            l = min(LCP[j], j)
            res = max(res, l)
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import random
from collections import defaultdict


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


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

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


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

print(l)

Submission status: Accepted

Solution code:
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)

import sys
import numpy as np

def z_algo(S):  # [z_algo, "i8[:](i8[:])"],
    # Z-algoirhm  O(n)
    # Z[i] := S と S[i:] で prefix が何文字一致しているか
    # 検証: https://atcoder.jp/contests/abc150/submissions/15829530
    i, j, n = 1, 0, len(S)
    Z = np.zeros(S.shape, dtype=np.int64)
    Z[0] = n
    while i < n:
        while i+j < n and S[j] == S[i+j]:
            j += 1
        if j == 0:
            i += 1
            continue
        Z[i] = j
        d = 1
        while i+d < n and d+Z[d] < j:
            Z[i+d] = Z[d]
            d += 1
        i += d
        j -= d
    return Z

def solve(N, S):
    ans = 0
    for i in range(N):
        Z = z_algo(S[i:])
        for idx_Z, z in enumerate(Z):
            an = min(z, idx_Z)
            ans = max(ans, an)
    return ans

numba_compile([
    [z_algo, "i8[:](u1[:])"],
    [solve, "i8(i8,u1[:])"]
])

def main():
    N = int(sys.stdin.buffer.readline())
    S = np.frombuffer(sys.stdin.buffer.readline(), dtype=np.uint8).copy()
    ans = solve(N, S)
    print(ans)

main()

Submission status: Accepted

Solution code:
class RollingHash:
    def __init__(self,S,base,M):
        self.N=len(S)
        self.M=M
        self.H=[0]*(self.N+1)
        self.B=[0]*(self.N+1)
        self.B[0]=1
        for i in range(self.N):
            self.B[i+1]=self.B[i]*base%M
            self.H[i+1]=(self.H[i]*base+(ord(S[i])-96))%M
    def get(self,l,r):
        return (self.H[r]-self.H[l]*self.B[r-l]+self.M)%self.M
    def getall(self,L):
        arr=[]
        for i in range(L,self.N+1):
            arr.append(self.get(i-L,i))
        return arr

def Hash(S,base,M):
    H=0
    for c in S:
        H=(H*base+ord(c)-96)%M
    return H
    
def isbad(L):
    arr=RH.getall(L)
    s=set()
    for i in range(L,N-L+1):
        s.add(arr[i-L])
        if arr[i] in s:
            return False
    return True
    
import random
N=int(input())
S=input()
MOD=2**61-1
base=random.randrange(100,MOD)
RH=RollingHash(S,base,MOD)
l,r=-1,N+1
while(r-l>1):
    mid=(l+r)//2
    if isbad(mid):
        r=mid
    else:
        l=mid
print(l)

Submission status: Accepted

Solution code:
class RollingHash:
    def __init__(self, s):
        b1, b2 = 1007, 2009
        self.mod1, self.mod2 = 10**9+7, 10**9+9
        self.size = len(s)
        self.string = s

        self.hash1 = self.make_hashtable(b1, self.mod1)
        self.hash2 = self.make_hashtable(b2, self.mod2)
        self.pow1 = self.make_powtable(b1, self.mod1)
        self.pow2 = self.make_powtable(b2, self.mod2)

    def make_hashtable(self, B, MOD):
        hashtable = [0] * (self.size+1)
        for i in range(1, self.size+1):
            hashtable[i] = (hashtable[i-1] * B + ord(self.string[i-1]))%MOD
        return hashtable
    
    def make_powtable(self, B, MOD):
        power = [0] * (self.size+1)
        power[0] = 1
        for i in range(1, self.size+1):
            power[i] = (B * power[i-1])%MOD
        return power

    def get_hash(self, l, length):
        r = length+l-1
        l -= 1
        h1 = (self.hash1[r]-self.hash1[l]*self.pow1[r-l])%self.mod1
        h2 = (self.hash2[r]-self.hash2[l]*self.pow2[r-l])%self.mod2
        return (h1, h2)

from collections import defaultdict

def solve1():
    N = int(input())
    S = input()
    size = len(S)
    hash_table = RollingHash(S)

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

            left = 1
            right = min(j-i, size-j+1)+1

            while right-left>1:
                m = (left+right)//2
                if hash_table.get_hash(i, m)==hash_table.get_hash(j, m):
                    left = m
                else:
                    right = m
            ans = max(ans, left)

    print(ans)


def solve2():
    N = int(input())
    S = input()
    size = len(S)
    hash_table = RollingHash(S)

    def check(m):
        d = defaultdict(lambda :10**20)
        for i in range(1, size-m+2):
            h = hash_table.get_hash(i, m)
            d[h] = min(d[h], i)
            if (i-d[h])>=m:
                return True
        return False

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

    print(left)

if __name__ == "__main__":
    # solve1()
    solve2()

Submission status: Accepted

Solution code:
class RollingHash:
    def __init__(self, s):
        b1, b2 = 1007, 2009
        mod1, mod2 = 10**9+7, 10**9+9
        self.size = len(s)
        self.string = s

        self.hash1 = self.make_hashtable(b1, mod1)
        self.hash2 = self.make_hashtable(b2, mod2)
        self.pow1 = self.make_powtable(b1, mod1)
        self.pow2 = self.make_powtable(b2, mod2)

    def make_hashtable(self, B, MOD):
        hashtable = [0] * (self.size+1)
        for i in range(1, self.size+1):
            hashtable[i] = (hashtable[i-1] * B + ord(self.string[i-1]))%MOD
        return hashtable
    
    def make_powtable(self, B, MOD):
        power = [0] * (self.size+1)
        power[0] = 1
        for i in range(1, self.size+1):
            power[i] = (B * power[i-1])%MOD
        return power

    def get_hash(self, l, length):
        r = length+l-1
        l -= 1
        mod1, mod2 = 10**9+7, 10**9+9
        h1 = (self.hash1[r]-self.hash1[l]*self.pow1[r-l])%mod1
        h2 = (self.hash2[r]-self.hash2[l]*self.pow2[r-l])%mod2
        return (h1, h2)

from collections import defaultdict

def solve1():
    N = int(input())
    S = input()
    size = len(S)
    hash_table = RollingHash(S)

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

            left = 1
            right = min(j-i, size-j+1)+1

            while right-left>1:
                m = (left+right)//2
                if hash_table.get_hash(i, m)==hash_table.get_hash(j, m):
                    left = m
                else:
                    right = m
            ans = max(ans, left)

    print(ans)


def solve2():
    N = int(input())
    S = input()
    size = len(S)
    hash_table = RollingHash(S)

    def check(m):
        d = defaultdict(lambda :10**20)
        for i in range(1, size-m+2):
            h = hash_table.get_hash(i, m)
            d[h] = min(d[h], i)
            if (i-d[h])>=m:
                return True
        return False

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

    print(left)

if __name__ == "__main__":
    # solve1()
    solve2()

Submission status: Accepted

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

print(ans)

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import os
import random

# 検索用タグ：ローリングハッシュ
sys.setrecursionlimit(999999999)


class RollingHash:
    # 衝突を防ぐため、res1とres2の基数の異なるハッシュによって判定する。
    BASE1 = 1007
    BASE2 = 2009
    MOD1 = 1000000007
    MOD2 = 1000000009

    def __init__(self, s: str):
        """
        コンストラクタ
        :s 検索の実施対象となる文字列
        """
        self.n = len(s)
        self.hash1 = [0] * (self.n + 1)
        self.hash2 = [0] * (self.n + 1)
        self.power1 = [1] * (self.n + 1)
        self.power2 = [1] * (self.n + 1)
        for i, e in enumerate(s):
            self.hash1[i + 1] = (self.hash1[i] * self.__class__.BASE1 + ord(e)) % self.__class__.MOD1
            self.hash2[i + 1] = (self.hash2[i] * self.__class__.BASE2 + ord(e)) % self.__class__.MOD2
            self.power1[i + 1] = (self.power1[i] * self.__class__.BASE1) % self.__class__.MOD1
            self.power2[i + 1] = (self.power2[i] * self.__class__.BASE2) % self.__class__.MOD2

    def get(self, left: int, right: int):
        res1 = self.hash1[right] - self.hash1[left] * self.power1[right - left] % self.__class__.MOD1
        if res1 < 0:
            res1 += self.__class__.MOD1
        res2 = self.hash2[right] - self.hash2[left] * self.power2[right - left] % self.__class__.MOD2
        if res2 < 0:
            res2 += self.__class__.MOD2
        return res1, res2

    def __func(self, mid, can_duplicate: bool) -> bool:
        """
        2分探索の内部処理(クラスメソッド)
        """
        dic1 = dict()
        # 検索対象の文字数 - 検索する文字列 数分ループ
        for i in range(self.n - mid + 1):
            # ハッシュ値を取得。(例：「ABBABBBBBB」に対してmid=5が渡された場合、「ABBAB,BBABB,BABBB・・」と先頭からう1文字ずつずらして、5文字分のハッシュを取得する。
            res = self.get(i, i + mid)
            # 所得済みのハッシュ値と同じ値を取得できた場合。(文字列の重複を検出できた場合)
            if res in dic1:
                # 部分重複を許容する または 部分重複が無い場合(先頭文字がmidの幅以上ある)なら処理終了。
                if can_duplicate or i - dic1[res] >= mid:
                    return True
                # 上記以外の場合、処理を継続。
                else:
                    continue
            #
            dic1[res] = i
        return False

    def binary_search(self, can_duplicate: bool) -> int:
        """
        2分探索にて、自分の文字列内のLCPを求める例：文字が「ABCABCABCCCC」なら3(ABC)を返す
        :canDuplicate 文字列が重なることを許容するか(部分重複を許容するか)
        """
        ok = 0
        ng = self.n // 2 + 1
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            if self.__func(mid, can_duplicate):
                ok = mid
            else:
                ng = mid
        return ok


# 実装を行う関数
def resolve(test_def_name=""):
    n = int(input())
    s = input()
    rh = RollingHash(s)
    print(rh.binary_search(False))


class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """5
ababa"""
        output = """2"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """2
xy"""
        output = """0"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """13
strangeorange"""
        output = """5"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def test_1original_1(self):
        test_input = """100
aaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaab"""
        output = """50"""
        self.assertIO(test_input, output)
        test_input = """10000
aaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaabaaaaaaaaab"""
        output = """5000"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Accepted

Solution code:
from itertools import accumulate
max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

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

res = 0
for i in range(1,N):
    m = 0
    r = 0
    for a,b in zip(S,S[i:]):
        if a == b:
            r += 1
        else:
            r = 0
        m = max2(m,r)
    m = min2(m,i)
    res = max2(res, m)

print(res)

Submission status: Accepted

Solution code:
n = int(input())
s = list(input())
b = 27
mod = 67280421310721
m = n // 2
x = [1] * (m + 1)
for i in range(1, m + 1):
    x[i] = (x[i - 1] * b) % mod
h0 = [0] * m
h0[0] = ord(s[0]) - 96
d = [{} for _ in range(m + 1)]
for i in range(1, m):
    h0[i] = (h0[i - 1] * b + (ord(s[i]) - 96)) % mod
for i in range(m, 0, -1):
    h = h0[i - 1]
    d[i][h] = 0
    for j in range(i, n):
        h *= b
        h %= mod
        h -= (x[i] * (ord(s[j - i]) - 96) % mod)
        h += (ord(s[j]) - 96)
        h %= mod
        if h in d[i]:
            if (j - i + 1 - d[i][h]) >= i:
                print(i)
                exit()
        else:
            d[i][h] = j - i + 1
print(0)

Submission status: Accepted

Solution code:
n,s = int(input()), list(input())
def z_algo(s):
    n = len(s)
    a = [0]*n
    i,j,l = 1,0,n
    a[0] = n
    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

ans = 0
for i in range(n-1):
    a = z_algo(s[i:])
    len_a = len(a)
    for j in range(len_a):
        ans = max(ans, min(j,a[j]))
print(ans)