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:
def atcoderD(str):
    n = len(str)
    LCSRe = [[0 for x in range(n + 1)]
             for y in range(n + 1)]

    res = ""
    res_length = 0
    index = 0
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            if (str[i - 1] == str[j - 1] and
                    LCSRe[i - 1][j - 1] < (j - i)):
                LCSRe[i][j] = LCSRe[i - 1][j - 1] + 1
                if (LCSRe[i][j] > res_length):
                    res_length = LCSRe[i][j]
                    index = max(i, index)
            else:
                LCSRe[i][j] = 0
    if (res_length > 0):
        for i in range(index - res_length + 1,
                       index + 1):
            res = res + str[i - 1]

    return res_length
n = int(input())
s = input()
print(atcoderD(s))

Submission status: Time Limit Exceeded

Solution code:
import collections
def main():

    N = int(input())
    S = input()
    d = collections.defaultdict(list)
    for l in range(1, N+1):
        for i in range(N-l+1):
            d[S[i:i+l]].append([i, i+l-1])
    for s in d:
        d[s] = sorted(d[s], key = lambda x: x[0])

    ans = 0
    for s in d:
        if len(d[s]) > 1:
            i, j = d[s][0]
            k, l = d[s][-1]
            if j < k:
                ans = max(ans, j-i+1)
    return ans

if __name__ == '__main__':
    print(main())

Submission status: Time Limit Exceeded

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

from collections import defaultdict
D = defaultdict(list)

for i in range(N):
    for j in range(i+1,N+1):
        if D[S[i:j]] == []:
            D[S[i:j]].append(j-i)
        D[S[i:j]].append(i)
        
ans = 0
for i in D:
    L = D[i][0]
    tmp = 0
    if len(D[i]) >= 3:
        if D[i][1] + L <= D[i][-1]:
            tmp = L
    if ans < tmp:
        ans = tmp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque


def main():
    num = int(input())
    s = list(input())

    ans = 0
    for i in range(num):
        if ((num - i) // 2) + 2 <= ans:
            break
        now_str = s[i]
        for j in range(i + 1 + ans, num):
            if now_str == s[j]:
                i_ind, j_ind = i, j
                kari = 1

                if ans >= num - j:
                    break

                while 1:
                    i_ind += 1
                    j_ind += 1
                    if i_ind == j or j_ind >= num:
                        break
                    if s[i_ind] == s[j_ind]:
                        kari += 1
                    else:
                        break
                ans = max(ans, kari)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    s = input()
    if s == "Sunny":
        print("Cloudy")
    elif s == "Cloudy":
        print("Rainy")
    else:
        print("Sunny")
    return

#B
def B():
    s = S()
    for i in range(len(s)):
        if i%2:
            if s[i] not in ["L","U","D"]:
                print("No")
                return
        else:
            if s[i] not in ["R","U","D"]:
                print("No")
                return
    print("Yes")
    return

#C
def C():
    n,k,q = LI()
    a = IR(q)
    f = [k-q]*(n)
    for i in range(q):
        ai = a[i]-1
        f[ai] += 1
    for i in f:
        if i <= 0:
            print("No")
        else:
            print("Yes")
    return

#D
def D():
    n,m = LI()
    a = LI()
    q = []
    for i in range(n):
        heappush(q,-a[i])
    for i in range(m):
        x = heappop(q)
        x *= -1
        x >>= 1
        heappush(q,-x)
    print(-sum(q))
    return

#E
def E():
    n = I()
    s = S()
    l = 0
    r = n
    while r-l > 1:
        m = (l+r)>>1
        d = defaultdict(lambda : float("inf"))
        for i in range(n-m+1):
            ts = tuple(s[i:i+m])
            if d[ts]+m <= i:
                l = m
                break
            d[ts] = i
        else:
            r = m
    print(l)
    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    E()

Submission status: Accepted

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

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

for i in range(1, N-1):
  for j in range(i+1, N):
    if S[i] == S[j]:
      if dp[i-1][j-1] == j - i:
        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):
  ans = max(ans, max(dp[i]))

print(ans)

Submission status: Accepted

Solution code:
def z_algo(s):
    res = [0] * len(s)
    res[0] = len(s)
    i = 1
    j = 0
    while i < len(s):
        while i + j < len(s) and s[j] == s[i + j]:
            j += 1
        res[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < len(s) and k + res[k] < j:
            res[i + k] = res[k]
            k += 1
        i += k
        j -= k
    return res


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

ans = 0
for i in range(n):
    res = z_algo(s[i:])
    for i, lcp in enumerate(res):
        ans = max(ans, min(lcp, i))
print(ans)

Submission status: Accepted

Solution code:
import types

_atcoder_code = """
# Python port of AtCoder Library.

__version__ = '0.0.1'
"""

atcoder = types.ModuleType('atcoder')
exec(_atcoder_code, atcoder.__dict__)

_atcoder_string_code = """
import copy
import functools
import typing


def _sa_naive(s: typing.List[int]) -> typing.List[int]:
    sa = list(range(len(s)))
    return sorted(sa, key=lambda i: s[i:])


def _sa_doubling(s: typing.List[int]) -> typing.List[int]:
    n = len(s)
    sa = list(range(n))
    rnk = copy.deepcopy(s)
    tmp = [0] * n
    k = 1
    while k < n:
        def cmp(x: int, y: int) -> bool:
            if rnk[x] != rnk[y]:
                return rnk[x] - rnk[y]
            rx = rnk[x + k] if x + k < n else -1
            ry = rnk[y + k] if y + k < n else -1
            return rx - ry
        sa.sort(key=functools.cmp_to_key(cmp))
        tmp[sa[0]] = 0
        for i in range(1, n):
            tmp[sa[i]] = tmp[sa[i - 1]] + (1 if cmp(sa[i - 1], sa[i]) else 0)
        tmp, rnk = rnk, tmp
        k *= 2
    return sa


def _sa_is(s: typing.List[int], upper: int) -> typing.List[int]:
    '''
    SA-IS, linear-time suffix array construction
    Reference:
    G. Nong, S. Zhang, and W. H. Chan,
    Two Efficient Algorithms for Linear Time Suffix Array Construction
    '''

    threshold_naive = 10
    threshold_doubling = 40

    n = len(s)

    if n == 0:
        return []
    if n == 1:
        return [0]
    if n == 2:
        if s[0] < s[1]:
            return [0, 1]
        else:
            return [1, 0]

    if n < threshold_naive:
        return _sa_naive(s)
    if n < threshold_doubling:
        return _sa_doubling(s)

    sa = [0] * n
    ls = [False] * n
    for i in range(n - 2, -1, -1):
        if s[i] == s[i + 1]:
            ls[i] = ls[i + 1]
        else:
            ls[i] = s[i] < s[i + 1]

    sum_l = [0] * (upper + 1)
    sum_s = [0] * (upper + 1)
    for i in range(n):
        if not ls[i]:
            sum_s[s[i]] += 1
        else:
            sum_l[s[i] + 1] += 1
    for i in range(upper + 1):
        sum_s[i] += sum_l[i]
        if i < upper:
            sum_l[i + 1] += sum_s[i]

    def induce(lms: typing.List[int]) -> None:
        nonlocal sa
        sa = [-1] * n

        buf = copy.deepcopy(sum_s)
        for d in lms:
            if d == n:
                continue
            sa[buf[s[d]]] = d
            buf[s[d]] += 1

        buf = copy.deepcopy(sum_l)
        sa[buf[s[n - 1]]] = n - 1
        buf[s[n - 1]] += 1
        for i in range(n):
            v = sa[i]
            if v >= 1 and not ls[v - 1]:
                sa[buf[s[v - 1]]] = v - 1
                buf[s[v - 1]] += 1

        buf = copy.deepcopy(sum_l)
        for i in range(n - 1, -1, -1):
            v = sa[i]
            if v >= 1 and ls[v - 1]:
                buf[s[v - 1] + 1] -= 1
                sa[buf[s[v - 1] + 1]] = v - 1

    lms_map = [-1] * (n + 1)
    m = 0
    for i in range(1, n):
        if not ls[i - 1] and ls[i]:
            lms_map[i] = m
            m += 1
    lms = []
    for i in range(1, n):
        if not ls[i - 1] and ls[i]:
            lms.append(i)

    induce(lms)

    if m:
        sorted_lms = []
        for v in sa:
            if lms_map[v] != -1:
                sorted_lms.append(v)
        rec_s = [0] * m
        rec_upper = 0
        rec_s[lms_map[sorted_lms[0]]] = 0
        for i in range(1, m):
            left = sorted_lms[i - 1]
            right = sorted_lms[i]
            if lms_map[left] + 1 < m:
                end_l = lms[lms_map[left] + 1]
            else:
                end_l = n
            if lms_map[right] + 1 < m:
                end_r = lms[lms_map[right] + 1]
            else:
                end_r = n

            same = True
            if end_l - left != end_r - right:
                same = False
            else:
                while left < end_l:
                    if s[left] != s[right]:
                        break
                    left += 1
                    right += 1
                if left == n or s[left] != s[right]:
                    same = False

            if not same:
                rec_upper += 1
            rec_s[lms_map[sorted_lms[i]]] = rec_upper

        rec_sa = _sa_is(rec_s, rec_upper)

        for i in range(m):
            sorted_lms[i] = lms[rec_sa[i]]
        induce(sorted_lms)

    return sa


def suffix_array(s: typing.Union[str, typing.List[int]],
                 upper: typing.Optional[int] = None) -> typing.List[int]:
    if isinstance(s, str):
        return _sa_is([ord(c) for c in s], 255)
    elif upper is None:
        n = len(s)
        idx = list(range(n))
        idx.sort(key=functools.cmp_to_key(lambda l, r: s[l] - s[r]))
        s2 = [0] * n
        now = 0
        for i in range(n):
            if i and s[idx[i - 1]] != s[idx[i]]:
                now += 1
            s2[idx[i]] = now
        return _sa_is(s2, now)
    else:
        assert 0 <= upper
        for d in s:
            assert 0 <= d <= upper

        return _sa_is(s, upper)


def lcp_array(s: typing.Union[str, typing.List[int]],
              sa: typing.List[int]) -> typing.List[int]:
    '''
    Reference:
    T. Kasai, G. Lee, H. Arimura, S. Arikawa, and K. Park,
    Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its
    Applications
    '''

    if isinstance(s, str):
        s = [ord(c) for c in s]

    n = len(s)
    assert n >= 1

    rnk = [0] * n
    for i in range(n):
        rnk[sa[i]] = i

    lcp = [0] * (n - 1)
    h = 0
    for i in range(n):
        if h > 0:
            h -= 1
        if rnk[i] == 0:
            continue
        j = sa[rnk[i] - 1]
        while j + h < n and i + h < n:
            if s[j + h] != s[i + h]:
                break
            h += 1
        lcp[rnk[i] - 1] = h

    return lcp


def z_algorithm(s: typing.Union[str, typing.List[int]]) -> typing.List[int]:
    '''
    Reference:
    D. Gusfield,
    Algorithms on Strings, Trees, and Sequences: Computer Science and
    Computational Biology
    '''

    if isinstance(s, str):
        s = [ord(c) for c in s]

    n = len(s)
    if n == 0:
        return []

    z = [0] * n
    j = 0
    for i in range(1, n):
        z[i] = 0 if j + z[j] <= i else min(j + z[j] - i, z[i - j])
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        if j + z[j] < i + z[i]:
            j = i
    z[0] = n

    return z
"""

atcoder.string = types.ModuleType('atcoder.string')
exec(_atcoder_string_code, atcoder.string.__dict__)
z_algorithm = atcoder.string.z_algorithm

from collections import deque
# from atcoder.string import z_algorithm

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

ans = 0
for i in range(n):
    zs = z_algorithm(s[i:])
    for j in range(i+1,n):
        ind = j-i
        dist = j-i
        v = min(dist,zs[ind])
        ans = max(ans,v)

print(ans)

Submission status: Accepted

Solution code:

M = int(input())
T = input()
ans = 0
for l in range(M):
    i, j = 1, 0
    S = T[l:]
    N = M-l
    Z = [0]*N
    Z[0] = N
    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
    for i in range(N):
        ans = max(ans, min(i, Z[i]))

print(ans)

Submission status: Accepted

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

def z_algorythm(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

ans = 0
for i in range(n):
    LCP = z_algorythm(s[i:])
    for j, l in enumerate(LCP):
        if j >= l:
            ans = max(ans, l)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
left = 0
right = n // 2 + 1
while right - left > 1:
    mid = (right + left) // 2
    length = mid
    check = set()
    for i in range(n - length + 1):
        s1 = s[i:i+length]
        check.add(s1)
        if s[i+length: i + 2*length] in check:
            left = mid
            break
    else:
        right = mid
print(left)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
ok, ng = 0, N + 1
while abs(ok - ng) > 1:
    x = (ok + ng) // 2
    check = set()
    for i in range(N - x + 1):
        check.add(S[i: i + x])
        if S[i + x: i + 2 * x] in check:
            ok = x
            break
    else:
        ng = x

print(ok)

Submission status: Accepted

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

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import permutations
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
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] = dp[i + 1][j + 1] + 1
ans = 0
for i in range(N):
    for j in range(N):
        if i >= j:
            continue
        now = min(dp[i][j], j - i)
        ans = max(now, ans)
print(ans)

Submission status: Accepted

Solution code:
def z_algorithm(s):
    n = len(s)
    if(n == 0):
        return []
    if(type(s) is str):
        s2 = [0] * n
        for i, si in enumerate(s):
            s2[i] = ord(si)
        s = s2
    z = [0] * n
    j = 0
    for i in range(1, n):
        z[i] = 0 if (j + z[j] <= i) else min(j + z[j] - i, z[i-j])
        while(i+z[i] < n):
            if(s[z[i]] != s[i + z[i]]):
                break
            z[i] += 1
        if(j + z[j] < i + z[i]):
            j = i
    z[0] = n
    return z

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

ans = 0
for i in range(n-1):
    si = s[i:]
    z = z_algorithm(si)
    for j,zj in enumerate(z[1:],1):
        ans = max(ans, min(zj, j))
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


def z_algorithm(s):
    """
    各iについてs[0..n)とs[i..n)のLCP(Longest Common Prefix)の長さを求める
    s: str or (list of int )
    """
    n = len(s)
    if n==0:
        return []
    z = [None]*n
    z[0] = 0
    j = 0
    for i in range(1,n):
        k = 0 if j + z[j] <= i else min(j+z[j]-i, z[i-j])
        z[i] = k
        while i+k<n and s[k]==s[i+k]:
            k += 1
        z[i] = k
        if j+z[j] < i+z[i]:
            j = i
    z[0] = n
    return z
n = int(input())
s = input()
ans = 0
for i in range(n):
    z = z_algorithm(s[i:])
    val = -1
    for j in range(len(z)):
        val = max(val, min(z[j], j))
    ans = max(ans, val)
#     print(z)
print(ans)

Submission status: Accepted

Solution code:
import sys


# \n
def input():
    return sys.stdin.readline().rstrip()


def main():
    N = int(input())
    S = list(map(ord,input()))

    ans =0
    for k in range(N+1,0,-1):
        i=0
        count =0
        while i<N-k:
            if S[i]==S[i+k]:
                count+=1
                ans =max(ans,count)
            else:
                count=0
            if count==k:
                break

            i+=1

    print(ans)









if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys


# \n
def input():
    return sys.stdin.readline().rstrip()


def main():
    N = int(input())
    S = list(input())



    ans =0
    for k in range(N+1,0,-1):
        i=0
        count =0
        while i<N-k:
            if S[i]==S[i+k]:
                count+=1
                ans =max(ans,count)
            else:
                count=0
            if count==k:
                break

            i+=1

    print(ans)









if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys


# \n
def input():
    return sys.stdin.readline().rstrip()


def main():
    N = int(input())
    S = list(input())



    ans =0
    for k in range(N+1,0,-1):
        i=0
        count =0
        while i<N-k:
            if S[i]==S[i+k]:
                count+=1
                ans =max(ans,min(count,k))
            else:
                count=0
            if ans==k:
                break

            i+=1

    print(ans)









if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys


# \n
def input():
    return sys.stdin.readline().rstrip()


def main():
    N = int(input())
    S = list(input())



    ans =0
    for k in range(N+1,0,-1):
        i=0
        count =0
        while i<N-k:
            if S[i]==S[i+k]:
                count+=1
                ans =max(ans,min(count,k))
            else:
                count=0

            i+=1

    print(ans)









if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys


# \n
def input():
    return sys.stdin.readline().rstrip()


def main():
    N = int(input())
    S = list(input())



    ans =0
    for k in range(1,N):
        i=0
        count =0
        while i<N-k:
            if S[i]==S[i+k]:
                count+=1
                ans =max(ans,min(count,k))
            else:
                count=0

            i+=1

    print(ans)









if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
s = tuple(map(lambda x: ord(x) - ord("a") + 1, input()))
base = 1007
mod = 2**61 - 1

length = n//2
b = [1] * (length + 1)
shash = [0] * (length+1)
for i in range(1, length + 1):
    b[i] = b[i-1] * base % mod
    shash[i] = (shash[i - 1] * base + s[i - 1]) % mod

for ans in reversed(range(1, length+1)):
    # calc hash
    hash_ = 0
    check = {}
    #y = set([])
    for left in range(n - ans + 1):
        if left == 0:
            hash_ = shash[ans]
            check[hash_] = left
            #y.add(hash_)
        else:
            hash_ = base * hash_ - b[ans] * s[left - 1] + s[left + ans - 1]
            hash_ %= mod
            if hash_ in check.keys():
                # print("tmp = ", tmp)
                if check[hash_] <= left - ans:
                    print(ans)
                    # a = check[hash_][tmp-1]
                    # at = "".join(map(lambda x: chr(x + ord("a")), s[a:a+ans]))
                    # for j in range(ans):
                        # if s[a+j] != s[left+j]:
                            # print("Fail")
                            # exit()
                    # print("Success")
                    sys.exit()
            else:
                check[hash_] = left
                #y.add(hash_)
        # print(hash_, s[left:left+ans])
print(0)

Submission status: Accepted

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

l,r=0,1
res=0
def check(l,r):
    #半閉区間[l,r)
    if not l<r:
        return False
    t=S[l:r]
    s=S[r:]
    n=(r-l)
    for i in range(len(s)-n+1):
        if s[i:i+n]==t:
            return True
    return False
        


while l<N and r<N:
    if r==l:
        r+=1
    if check(l,r):
        res=max(r-l,res)
        r+=1
    else:
        l+=1
    
print(res)

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit
 
@njit(cache=True)
def main(N, s):
    dpt = np.zeros((N+1, N+1), dtype=np.int16)
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            if s[j-1] == s[i-1]:
                if j - dpt[i-1][j-1] > i:
                    dpt[i][j] = dpt[i-1][j-1] + 1
 
    return np.amax(dpt)
 
if __name__ == '__main__':
    N = int(input())
    s = np.array([ord(c) for c in input()]) 
 
    print(main(N, s))

Submission status: Accepted

Solution code:
def Z_algo(S):
    n = len(S)
    LCP = [0]*n
    i = 1
    j = 0
    c = 0#最も末尾側までLCPを求めたインデックス
    for i in range(1, n):
        #i番目からのLCPが以前計算したcからのLCPに含まれている場合
        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

x=int(input())

s=input()
ans=0

for i in range(x):
    t=s[i:]
    lst=Z_algo(t)
    for i,v in enumerate(lst):
        cnt=min(i,v)
        ans=max(ans,cnt)


print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
from typing import overload
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def z_algo(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 k < j and k + Z[k] < j:
            Z[i + k] = Z[k]
            k += 1
        
        i += k
        j -= k
    return Z


def main():
    N = int(input())
    S = input().strip()

    res = 0
    for i in range(N - 1):
        Z = z_algo(S[i:])
        t = 0
        for i, z in enumerate(Z):
            if i < z:
                continue
            t = max(t, z)
        res = max(res, t)
        
    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from random import randint


class RollingHash:
    def __init__(self, s):
        self.base = [7073, 7577, 5445, 2742, 6972, 7547, 2267, 286, 6396, 7147,
                     3307, 188, 266, 8253, 2818, 9527, 5110, 1207, 4633, 6196,
                     309, 2646, 7533, 85, 9870, 4730, 6862, 9213, 7456, 7098,
                     6805, 674, 5821, 4864, 8061, 1826, 2219, 459, 5937, 5667,
                     9033, 5552, 7263, 2402, 9809, 3701, 7048, 2874, 8350, 6006,
                     973, 3317, 2522, 5546, 1669, 1545, 7972, 4979, 9905, 173,
                     6812, 7715, 5006, 6068, 6340, 4989, 5510, 6380, 1200, 6739,
                     5527, 4000, 6519, 3448, 2933, 6048, 3133, 1667, 9086, 8368,
                     4914, 7142, 2770, 7752, 391, 7052, 5476, 3105, 8322, 3501,
                     7454, 3167, 8730, 9002, 4564, 138, 2197, 7238, 3411, 7433][randint(0, 99)]
        self.mod = 4611686018427387903
        self.size = len(s)
        self.string = s

        self.hash = self.make_hashtable(s)
        self.pow = self.make_powtable()

    def make_hashtable(self, _s):
        hashtable = [0] * (self.size + 1)
        for i in range(self.size):
            hashtable[i + 1] = (hashtable[i] * self.base + ord(_s[i])) % self.mod
        return hashtable

    def make_powtable(self):
        power = [1] * (self.size + 1)
        for i in range(self.size):
            power[i + 1] = (self.base * power[i]) % self.mod
        return power

    def get_hash(self, left, right):
        """get hash of s[left:right]"""
        return (self.hash[right] - self.hash[left] * self.pow[right - left]) % self.mod

    def contain(self, a):
        """return a in s"""
        m = len(a)
        if m > self.size:
            return False
        hashs = self.get_hash(0, m)
        hasha = 0
        for i in range(m):
            hasha = (hasha * self.base + ord(a[i])) % self.mod
        for i in range(self.size - m + 1):
            if hasha == hashs:
                return True
            hashs = self.get_hash(i, m + i)
        return hasha == hashs


from collections import defaultdict
# d = defaultdict(int)で0で初期化
# d = defaultdict(lambda: 100)で100で初期化
n, s = int(input()), input()
rh = RollingHash(s)


def check(m):
    d = defaultdict(lambda: 10000000)
    for i in range(n - m + 1):
        h = rh.get_hash(i, i + m)
        d[h] = min(d[h], i)
        # m以上離れていて2回目
        if i - d[h] >= m:
            return True
    return False


l, r = 0, n // 2 + 1
while l + 1 < r:
    mid = (l + r) // 2
    if check(mid):
        l = mid
    else:
        r = mid
print(l)

Submission status: Accepted

Solution code:
from random import randint


class RollingHash:
    def __init__(self, s):
        self.base = [7073, 7577, 5445, 2742, 6972, 7547, 2267, 286, 6396, 7147,
                     3307, 188, 266, 8253, 2818, 9527, 5110, 1207, 4633, 6196,
                     309, 2646, 7533, 85, 9870, 4730, 6862, 9213, 7456, 7098,
                     6805, 674, 5821, 4864, 8061, 1826, 2219, 459, 5937, 5667,
                     9033, 5552, 7263, 2402, 9809, 3701, 7048, 2874, 8350, 6006,
                     973, 3317, 2522, 5546, 1669, 1545, 7972, 4979, 9905, 173,
                     6812, 7715, 5006, 6068, 6340, 4989, 5510, 6380, 1200, 6739,
                     5527, 4000, 6519, 3448, 2933, 6048, 3133, 1667, 9086, 8368,
                     4914, 7142, 2770, 7752, 391, 7052, 5476, 3105, 8322, 3501,
                     7454, 3167, 8730, 9002, 4564, 138, 2197, 7238, 3411, 7433][randint(0, 100)]
        self.mod = 4611686018427387903
        self.size = len(s)
        self.string = s

        self.hash = self.make_hashtable(s)
        self.pow = self.make_powtable()

    def make_hashtable(self, _s):
        hashtable = [0] * (self.size + 1)
        for i in range(self.size):
            hashtable[i + 1] = (hashtable[i] * self.base + ord(_s[i])) % self.mod
        return hashtable

    def make_powtable(self):
        power = [1] * (self.size + 1)
        for i in range(self.size):
            power[i + 1] = (self.base * power[i]) % self.mod
        return power

    def get_hash(self, left, right):
        """get hash of s[left:right]"""
        return (self.hash[right] - self.hash[left] * self.pow[right - left]) % self.mod

    def contain(self, a):
        """return a in s"""
        m = len(a)
        if m > self.size:
            return False
        hashs = self.get_hash(0, m)
        hasha = 0
        for i in range(m):
            hasha = (hasha * self.base + ord(a[i])) % self.mod
        for i in range(self.size - m + 1):
            if hasha == hashs:
                return True
            hashs = self.get_hash(i, m + i)
        return hasha == hashs


from collections import defaultdict
# d = defaultdict(int)で0で初期化
# d = defaultdict(lambda: 100)で100で初期化
n, s = int(input()), input()
rh = RollingHash(s)


def check(m):
    d = defaultdict(lambda: 10000000)
    for i in range(n - m + 1):
        h = rh.get_hash(i, i + m)
        d[h] = min(d[h], i)
        # m以上離れていて2回目
        if i - d[h] >= m:
            return True
    return False


l, r = 0, n // 2 + 1
while l + 1 < r:
    mid = (l + r) // 2
    if check(mid):
        l = mid
    else:
        r = mid
print(l)