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:
N = int(input())
S = input()

ans = 0

# 3文字以上
for i in range(0, N - 2):
    for j in range(i + 3, N):
        if S[i:i + 3] == S[j:j + 3]:
            i += 2
            j += 2
            max_length = j
            length = 3
            while True:
                if i + 1 == max_length or j + 1 == N:
                    break
                else:
                    i += 1
                    j += 1
                if S[i] == S[j]:
                    length += 1
                else:
                    break
            if length > ans:
                ans = length

# 2文字
if ans == 0:
    for i in range(0, N - 1):
        s = S[i:i + 2]
        if s in S[i + 1:]:
            ans = 2

# 1文字
if ans == 0:
    for i in range(N):
        s = S[i]
        if s in S[i + 1:]:
            ans = 1

print(ans)

Submission status: Runtime Error

Solution code:
if 1 == 1:
  n = int(input())
  s = input()
  raw = []
  for i in range(n):
    raw.append(s[i:])
  raw.sort()
  #print(raw)
  can = [a[0]]
  if all( raw[i-1][0] != raw[i][0] for i in range(1,n)):
    ans = 0
  else:
    ans = 1
    for i in range(1,n):
      two = raw[i]
      last = can
      can = []
      for one in last:
        lone = len(one)
        ltwo = len(two)
        stop = min(lone,ltwo,abs(lone-ltwo))
        if ans > stop:
          can.append(one)
        elif one[:ans] != two[:ans]:
          pass
        else:
          can.append(one)
          for i in range(ans,stop):
            if one[i] == two[i]:
              ans += 1
      can.append(two)
  print(ans)

Submission status: Runtime Error

Solution code:

# coding: utf-8

# In[2]:


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


# In[25]:


pairs = []
for i,c in enumerate(S):
    if i+1<N:
        for j,c1 in enumerate(S[i+1:]):
            if c == c1:
                pairs.append([i,i+j+1,1])


# In[26]:


for i1,pair1 in enumerate(pairs):
    for i2,pair2 in enumerate(pairs[i1+1:]):
        if pair1[0]+1==pair2[0] and pair1[1]+1==pair2[1]:
            pair2[2]=pair1[2]+1


# In[30]:


print(max(pairs, key=lambda x:x[2])[2])

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from itertools import combinations


def p_e():
    N = int(input())
    S = input()

    S_idx = defaultdict(list)

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

    ans = []

    for c in S_idx.keys():
        if len(S_idx[c]) <= 1:
            continue

        comb_list = list(combinations(S_idx[c], 2))
        i = 1

        f = True
        while f:
            i += 1
            f = False
            for comb in comb_list:
                a = comb[0]
                b = comb[1]
                if S[a: a + i] == S[b: b + i]:
                    f = True

        ans.append(i - 1)

    print(max(ans))


if __name__ == '__main__':
    p_e()

Submission status: Runtime Error

Solution code:
N = int(input())
S = list(map(str, input()))

def next_char(candidate, cor_char_index, ctr):
	# print("next_char")
	# print(candidate, cor_char_index, ctr)
	char = S[cor_char_index]
	satisfy = []
	for i in candidate:
		if cor_char_index < i - ctr + 1 and i + 1 < N and S[i + 1] == char:
			satisfy.append(i + 1)
	if len(satisfy) >= 1 and cor_char_index + 1 < N:
		return next_char(satisfy, cor_char_index + 1, ctr + 1)
	else:
		return ctr
	
ret = 0
for i in range(N):
	if ret > N - i:
		break
	else:
		tmp = (next_char([j for j in range(i, N)], i, 0))
		ret = max(ret, tmp)
		
print(ret)

Submission status: Runtime Error

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


class Node:
    def __init__(self, num_):
        self.nums = [num_]
        self.children = {}  # dict

    def match(self, num_):
        self.nums.append(num_)

    def addChild(self, ch_, num_):
        self.children[ch_] = Node(num_)


ma_max = 0
Tr = {}


def addTree(tr, b, n, ma):
    if n == N:
        return ma
    if S[n] not in tr:
        tr[S[n]] = Node(n)
        return addTree(tr[S[n]].children, b, n + 1, ma)
    else:
        if min(tr[S[n]].nums) >= b:
            ma = 0
        tr[S[n]].match(n)
        return addTree(tr[S[n]].children, b, n + 1, ma + 1)


for i in range(0, N):
    ma_max = max(ma_max, addTree(Tr, i, i, 0))

print(ma_max)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = [int(x) for x in input().split()]
list.sort(A, reverse=True)

for _ in range(M):
    A[0] //= 2
    list.sort(A, reverse=True)

print(sum(A))

Submission status: Runtime Error

Solution code:
N = int(input())
S = list(map(str, input()))

def next_char(candidate, cor_char_index, ctr):
	# print("next_char")
	# print(candidate, cor_char_index, ctr)
	char = S[cor_char_index]
	satisfy = []
	for i in candidate:
		if cor_char_index < i - ctr + 1 and i + 1 < N and S[i + 1] == char:
			satisfy.append(i + 1)
	if len(satisfy) >= 1:
		return next_char(satisfy, cor_char_index + 1, ctr + 1)
	else:
		return ctr
	
ret = 0
for i in range(N):
	if ret > N - i:
		break
	else:
		tmp = (next_char([j for j in range(i, N)], i, 0))
		ret = max(ret, tmp)
		
print(ret)

Submission status: Runtime Error

Solution code:
N = int(input())
S = input()
ans = 0
for i in range(1, N):
    # cnt = 0
    pass
    for j in range(N-i):
    #     if S[j] == S[i+j]:
    #         cnt += 1
    #     else:
    #         ans = max(ans, min(cnt, i))
    #         cnt = 0
    # ans = max(ans, min(cnt, i))
    pass
print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
for j in range(m):
  if len(a) != 1:
    if a[0] >= a[1]:
      a[0] //= 2
    else:
      a[1] //= 2
      a.sort(reverse=True)
  else:
    a[0] //= 2
print(sum(a))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
from bisect import bisect_left

def hantei(mid, s, suffix):
    # print(mid, s, suffix)
    for i in range(n - mid + 1):
        tmp = (s[i:i+mid], i)
        idx = bisect_left(suffix, tmp)
        flag = True
        while(flag):
            tgt = suffix[idx]
            # print(tgt)
            if tmp[0] == tgt[0]:
                if tgt[1] >= i + mid:
                    return True
                else:
                   idx += 1
            else:
                flag = False

n = getN()
s = input().strip()

suffix = []

for i in range(n):
    suffix.append((s[i:], i))

suffix.sort()

mn = 0
mx = n // 2
while(mx-mn>1):
    mid = (mx + mn + 1) // 2
    is_succ = hantei(mid, s, suffix)
    if is_succ:
        mn = mid
    else:
        mx = mid

if hantei(mx, s, suffix):
    print(mx)
else:
    print(mn)

Submission status: Runtime Error

Solution code:
N=int(input())
S=input()
import numpy as np
#S=np.array(S)
ans=0
for i in range(N//2):
    for j in range(N-i):
        for k in range(j+i+1,N-i):
            #print(j,j+i+1,k,k+i+1)
            
            if S[j:j+i+1]==S[k:k+i+1]:
                ans=i+1
                break
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-                                                         
tmp = input()
my_str = input()

start = 0
end = 1
max_len = 0

while (end < len(my_str)):
    if my_str[start:end] in my_str[end:]:
        if end - start > max_len:
            max_len = end - start
     	end += 1
    else:
        start += 1

print(max_len)

Submission status: Runtime Error

Solution code:
def hersCode(n):
  ok = 0
  ng = n
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if nasu(mid):
      ok = mid
    else:
      ng = mid
  return ok

def nasu(n):
  for i in range(N - n * 2 + 1):
    for j in R[S[i]]:
      if i >= j: continue
      if honya(i, j, n):
        return True
  return False

def honya(x, y, n):
  for i in range(n):
    if S[x + i] != S[y + i]:
      return False
  return True

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

R = {}
for i in range(N):
  if S[i] not in R:
    R[S[i]] = [i]
  else:
    R[S[i]].append(i)

print(hersCode(N))

Submission status: Runtime Error

Solution code:
N = int(input())
S = input()
length = N//2

while length:
  strings = [S[i:i+length] for i in range(N-length+1)]
  print(length, strings)
  for i in range(N-length+1):
    for j in range(i+length,N-length+1):
      if S[i:i+length] == S[j:j+length]:
        print(length)
        break
  
  length -= 1
else:
  print(0)

Submission status: Runtime Error

Solution code:
n=int(input())
s=input()
m=n//2
ans=0
for length in range(1,m+1):
    for one in range(n-2*i):
        for two in range(one+length,n-length+1):
            if s[one:one+length]==s[two:two+length]:
                ans=max(ans,length)
print(ans)