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: Runtime Error

Solution code:
def resolve():
    import sys
    input=sys.stdin.readline
    N = int(input().rstrip())
    S = input().rstrip()

    def z_algo(s):
        """
        param s:str
        return list of int with length len(s)
        """
        # initialization
        n=len(s)
        z=[0]*n
        z[0]=n
        # construct
        L,R=0,0
        for i in range(1,n):
            if i>R: # 過去の結果が全く使えない
                L=R=i
                while(R<n and s[R-L]==s[R]): R+=1
                z[i]=R-L
                R-=1 # 0-indexedでiと比較するため
            elif z[i-L]<R-i+1:
                z[i]=z[i-L]
            else:
                L=i
                R+=1 # Rまでは確定しているので、R+1から確認
                while(R<n and s[R-L]==s[R]): R+=1
                z[i]=R-L
                R-=1
        return z

    ans = 0
    for i in range(N):
        z = z_algo(S[i:])
        z = z[(len(z)+1)//2:]
        max_z = max(z)
        ans = max(ans, max_z)
    print(ans)

resolve()

Submission status: Runtime Error

Solution code:
input=sys.stdin.readline
N = int(input())
S = input()

def z_algo(s):
    """
    param s:str
    return list of int with length len(s)
    """
    # initialization
    n=len(s)
    z=[0]*n
    z[0]=n
    # construct
    L,R=0,0
    for i in range(1,n):
        if i>R: # 過去の結果が全く使えない
            L=R=i
            while(R<n and s[R-L]==s[R]): R+=1
            z[i]=R-L
            R-=1 # 0-indexedでiと比較するため
        elif z[i-L]<R-i+1:
            z[i]=z[i-L]
        else:
            L=i
            R+=1 # Rまでは確定しているので、R+1から確認
            while(R<n and s[R-L]==s[R]): R+=1
            z[i]=R-L
            R-=1
    return z

ans = 0
for i in range(N-1):
    z = z_algo(S[i:])
    z = z[(len(z)+1)//2:]
    max_z = max(z)
    ans = max(ans, max_z)
print(ans)

Submission status: Runtime Error

Solution code:
from random import shuffle
N = int(input())
S = input()

def check(l):
    r = range(N - 2 * l + 1)
    shuffle(r)
    for i in r:
        if S[i : i + l] in S[i + l :]:
            return True

ok = 0
ng = N // 2 + 1

while ng - ok > 1:
    m = (ok + ng) // 2
    if check(m):
        ok = m
    else:
        ng = m

print(ok)

Submission status: Runtime Error

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

def rec(start, minlen):
    if start+minlen >= N:
        return minlen
    part_s = S[start: start+minlen+1]
    remain_s = S[start+minlen+1:]
    if part_s in remain_s:
        return rec(start, minlen+1)
    else:
        return rec(start+1, minlen)

print(rec(0, 0))

Submission status: Runtime Error

Solution code:
def calc_length(s: str, l1: int, l2, int, n: int) -> int:
  for i in range(1, min[l2 - l1, n - l2]):
    if s[l1 + i] != s[l2 + i]:
      return i
  return i + 1

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

longest = 0
for l1 in range(n - 1):
  for l2 in range(l1 + 1, n):
    if s[l1] == s[l2]:
      length = calc_length(s, l1, l2, n)
      if length > longest:
        longest = length

print(longest)