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: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import re
n = int(input())
s = input()
start_idx = 0
matcher_idx = 0
match_length = 0
while start_idx < n:
    tmp_s_i = start_idx
    tmp_l = 0
    matcher_idx = start_idx + 1
    matcher_start = matcher_idx
    first_matched = True
    while (matcher_idx < n) & (start_idx < matcher_start):
        if match_length < tmp_l:
            match_length = tmp_l
        if s[start_idx] == s[matcher_idx]:
            start_idx += 1
            if first_matched:
                first_matched = False
                matcher_start = matcher_idx
            matcher_idx += 1
            tmp_l += 1
        else:
            first_matched = True
            start_idx = tmp_s_i
            tmp_l = 0
            matcher_idx += 1
    if match_length < tmp_l:
        match_length = tmp_l
    start_idx = tmp_s_i + 1
print(match_length)

Submission status: Wrong Answer

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

def LCS(S,T):
    dp=[[0 for i in range(len(T)+1)] for j in range(len(S)+1)]
    for i in range(len(S)):
        for j in range(len(T)):
            dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])
            if S[i]==T[j]:
                dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+1)
    return dp[len(S)][len(T)]
arr=[]
for i in range(N-1):
    arr.append(LCS(S[0:i],S[i+1:N]))

print(max(arr))

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
max_l = N//2
ans = 0
from collections import defaultdict as dd
cnt = dd(int)
for l in range(max_l,0,-1):
    for n in range(N-l+1):
        if n + l > N:
            break
        cnt[S[n:n+l]] += 1
        if cnt[S[n:n+l]] >= 2:
            ans = l
            break
    else:
        continue
    break
print(ans)

Submission status: Wrong Answer

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

import re

result = re.search(r'(.+)(?=.*?\1)', s)

if result:
  print(len(result.group()))
else:
  print(0)

Submission status: Wrong Answer

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

res = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        tt = res
        mx = min(j - i, n - j)
        if tt >= mx:
            break
        while tt <= mx:
            tt += 1
            if s[i:i+tt] != s[j:j+tt]:
                break
        _res = tt - 1
        res = max(res, _res)

print(res)

Submission status: Wrong Answer

Solution code:
import math
import heapq
from bisect import bisect_right, bisect_left
from collections import defaultdict, Counter
import itertools
import sys
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7
INF = float("inf")


def main():
    n = int(input())
    s = list(input())
    if len(set(s)) == n:
        print(0)
        exit()
    if n % 2 == 0:
        if s[:n // 2] == s[n // 2:]:
            print(n // 2)
            exit()
    if len(set(s)) == 1:
        print(n // 2)
        exit()

    ans = 0
    for i in range(n):
        le, k = -1, 0
        for j in range(i+1, n):
            if s[i] == s[j] and le == -1:
                le = j - i
                k += 1
                #print(i, s[i], j, s[j], "START")
            elif i + k < n and k < le and s[i + k] == s[j]:
                #print(i+k, s[i + k], j, s[j], "MIDDLE")
                k += 1
            else:
                ans = max(ans, k)
                le = -1
                k = 0
                if s[i] == s[j] and le == -1:
                    le = j - i
                    k += 1
                    #print(i, s[i], j, s[j], "START2")
            ans = max(ans, k)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
ans = 0
p = 0
q = 1
while True:
    word = s[p:q]
    w_l = len(word)
    if w_l > len(s) - q:
        break
    for j in range(q, n - w_l + 1):
        if word == s[j:j + w_l]:
            ans = w_l
            break
    else:
        p += 1
    q += 1

Submission status: Wrong Answer

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


def isok(n):
    for i in range(N-2*n+1):
        now = S[i:i+n]
        if S[i+n:].find(now) != -1:
            return True
    return False


left = 0
right = N//2

while right - left > 1:
    mid = left + (right-left)//2
    if not isok(mid):
        right = mid
    else:
        left = mid

print(left)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
# S = "abcde"*10**3
# N = 5*10**3
i = 0
ans = 0
cnt = 1
for i in range(N//2):
    j = i + 1
    while j < N:
        jadd = 1
        if S[i:i+cnt] == S[j:j+cnt] and i+cnt <= j:
            cnt += 1
            jadd = j + cnt
        else:
            ans = max(ans,cnt)
            j += jadd
print(ans-1)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys

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

for length in range(n//2, 0, -1):
    for i in range(n - length*2 + 1):
        st = [str(s[i:i+length])]
        for j in range(i+length, n-length + 1):
            st.append(str(s[j:j+length]))
        c = Counter(st)
        if c.most_common(1)[0][1] > 1:
            print(length)
            sys.exit()

Submission status: Wrong Answer

Solution code:
import copy
n = int(input())

s = input()

sl = set(s)

ans = 0

f = True

if len(s) == len(sl):
    f = False

d = {}
que = []

for i in sl:
    d[i] = []

for i,x in enumerate(s):
    d[x].append(i)

for i in d.values():
    que.append(i)

while f:
    ans += 1
    prev = copy.deepcopy(que)
    que = []

    for x in prev:
        for i in sl:
            d[i] = []
        for y in x:
            if y + ans >= n:
                continue
            d[s[y + ans]].append(y)

        for y in d.values():
            if len(y) > 1:
                que.append(y)
    if len(que) == 0:
        break

    if ans + 1 >= len(s):
        break

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
S += '0'
l = 0
for i in range(N):
    for j in range(i + 1, N):
        f = True
        for k in range(min(j - i, N - j + 1)):
            if S[i : i + k] == S[j : j + k] :
                pass
            else:
                break
        l = max(l,  k)
        
print(l)

Submission status: Wrong Answer

Solution code:
N=int(input())
S=list(input())
Hitoshi=[[i==j for j in S] for i in S]
DP=[[0]*N for i in range(N)]#DP[i][l]:iまで見たときのl始まりの部分列の最長
for i in range(1,N):
  for l,d in enumerate(DP[i-1]):
    if l>i:break
    if Hitoshi[i][l+d] and l+d<i-d:
      newd=d+1
    else:
      newd=0
    DP[i][l]=newd
print(max([max(i) for i in DP]))

Submission status: Wrong Answer

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

ans = 0
for i in range(1, N):
    S1 = S[:i]
    S2 = S[i:]
    j = 0
    k = 1
    s = S2[0]
    if S1.count(S2[0]) == 0:
        continue
    while j < len(S1):
        if S1[j: j + len(s)] == s:
            j = j + len(s)
            while j < len(S1) and k < len(S2):
                if S1[j] == S2[k]:
                    s += S1[j]
                    j += 1
                    k += 1
                else:
                    j += 1
                    break
        else:
            j += 1
    ans = max(ans, len(s))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
S=input()
a=0
ans=0
while a<=n-2-ans:
    j=a+1+ans
    while j<=n-ans:
        if S[j]==S[a]:
            cnt=1
            while cnt<=n-j-1:
                if S[a+cnt]==S[j+cnt] and a+cnt<j:
                    cnt+=1
                else:
                    break
            ans=max(ans,cnt)
        j+=ans
    a+=1
print(ans)

Submission status: Wrong Answer

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 = [raw[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: Wrong Answer

Solution code:
import time
 
def create_table(pattern):
  table = [0 for _ in range(len(pattern))]
  j = 0
  for i in range(1, len(pattern)):
    if pattern[i] == pattern[j]:
      j += 1
      table[i] = j
    else:
      table[i] = j
      j = 0
  return table
 
def kmp_search(string, pattern):
  table = create_table(pattern)
  i = j = 0
  while i < len(string) and j < len(pattern):
    if string[i] == pattern[j]:
      i += 1
      j += 1
    elif j == 0:
      i += 1
    else:
      j = table[j]
 
  if j == len(pattern):
    return i - j
  else:
    return None

n=int(input())
s=input()
m=n//2
ans=0

for i in range(n-1):
  for length in range(1,min(m,n-i)+1):
    string=s[i+length:]
    pattern=s[i:i+length]
    if kmp_search(string, pattern):
      ans=max(ans,length)
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
S=list(input())
DP=[[0]*N for i in range(N)]#DP[i][l]:iまで見たときのl始まりの部分列の最長
for i in range(1,N):
  s=S[i]
  for l,d in enumerate(DP[i-1]):
    if l>i:break
    if s==S[l+d] and l+d<i-d:
      newd=d+1
    else:
      newd=0
    DP[i][l]=newd
print(max([max(i) for i in DP]))

Submission status: Wrong Answer

Solution code:
import sys
import re
from collections import Counter
n = int(sys.stdin.readline())
S = input()
f = False
for i in range(n//2, 0, -1):
    ptn = '.'*i
    ptn = re.compile(ptn)
    result = ptn.findall(S)
    result = Counter(result)
    for key, value in result.items():
        if value>=2:
            print(len(key))
            f = True
            break
    if f==True:
        break

Submission status: Wrong Answer

Solution code:
def solve():
  n=int(input())
  s=list(input())
  ans=0

  for i in range(n-1):
    if ans >= (n-i)//2:
      break
    for j in range((n-i)//2,ans,-1):
      if s[i:i+j] in s[i+j:]:
        ans = j
        break

  print(ans)


if __name__ == '__main__':
  solve()

Submission status: Wrong Answer

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

nn=n//2
ans=0

while nn and not ans:


    for l in range(n+1-(nn*2)):
        r=nn+1
        a=s[l:r]
        b=s[r:]
        if a in b:
            ans=nn
            break
        r+=1

    nn-=1

print(ans)

Submission status: Wrong Answer

Solution code:

cnt = 0
max = 0
flag = 0
N = int(input())
S = list(input())
x = [-1] * N
for i in range(N-1):
    for j in range(i+1,N):
        if x[i] == -1:
            if x[j] == -1 and S[i] == S[j]:
                x[j] = i
                x[i] = i
                flag = 1
                max = 1

if flag == 0:
    print(0)
else:
    for i in range(N-1):
        if x[i+1] - x[i] == 1:
            cnt += 1
        else:
            if cnt+1 > max:
                max = cnt + 1
            cnt = 0
    print(max)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
S = input()
ans = 0
D = Counter(S)
id = 0
dic = {}
for k in D.keys():
    dic[k] = id
    id += 1
m = 0
OB = [-1]*N
for i in range(N):
    if D[S[i]]<=1:
        pass
    else:
        OB[i] = dic[S[i]]
        m = max(m,dic[S[i]])
SSS = []
for j in range(m):
    SS = [i for i in range(N) if OB[i]==j]
    SSS.append(SS)
for n in range(len(SSS)):
    lss = len(SSS[n])
    for i in range(lss):
        for j in range(lss):
            if i==j:
                continue
            id = 0
            while True:

                if SSS[n][i]+id>=N or SSS[n][j]+id>=N or SSS[n][i]+id>=SSS[n][j]:
                    break
                if S[SSS[n][i]+id]==S[SSS[n][j]+id]:
                    id += 1
                else:
                    break
            ans = max(ans,id)


print(ans)

Submission status: Wrong Answer

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

maxlen = n // 2

ans = 0
for i in range(maxlen, 0, -1):
    for j in range(n - i * 2):
        for k in range(n - j - i - i + 1):
            #print(i,j,k)

            l1 = s[j : j + i]
            l2 = s[j + i + k : j + i + i + k]
            #print(l1,l2)
            if l1 == l2:
                ans = i
                break
        if ans != 0:
            break
    if ans != 0:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
St = input()
ans = 0

#初期化
dp=[[0 for i in range(N)] for j in range(N)]

#DP:dp[i][j] Sのi文字目までとj文字目以降の最大マッチング
for i in range(N-1):
  for j in range(N-1, i, -1):
    dp[i+1][j-1] = max(dp[i][j-1],dp[i+1][j])
    if St[i] == St[j-1]:
      dp[i+1][j-1] = max(dp[i+1][j-1], dp[i][j]+1)
      
ans = 0
for i in range(N):
  ans = max(ans, dp[i][i])
print(ans)

Submission status: Wrong Answer

Solution code:
def solve(n, s, MOD):
    d = 26
    sss = [ord(c) - 97 for c in s]

    for l in range(n // 2, 0, -1):
        m = pow(d, l, MOD)
        t = 0
        for c in sss[:l]:
            t = (t * d + c) % MOD
        acc = [-1] * (l - 1) + [t]
        appeared = set()
        for i in range(l, n):
            c0, c1 = sss[i - l], sss[i]
            t = (t * d - c0 * m + c1) % MOD
            # print(l, c0, c1, t, acc, appeared)
            appeared.add(acc[i - l])
            if t in appeared:
                return l
            acc.append(t)

    return 0


n = int(input())
s = input()
print(solve(n, s, 10 ** 9 + 7))

Submission status: Wrong Answer

Solution code:
def create_table(pattern):
    table = [0 for _ in range(len(pattern))]
    j = 0
    for i in range(1, len(pattern)):
        if pattern[i] == pattern[j]:
            j += 1
            table[i] = j
        else:
            table[i] = j
            j = 0
    return table
N = int(input())
S = input()
ans = 0
for i in range(N):
    ans = max(ans, min(max(create_table(S[i:])),(N-i)//2))
print(ans)

Submission status: Wrong Answer

Solution code:

def resolve():
    n = int(input())
    s = input()

    max_count = 0

    # for i in range(n-1):
    #     for j in range(i+1, n):
    #         cur = 0
    #         while i + cur < j and j + cur < n:
    #             if s[i+cur] != s[j+cur]:
    #                 break;
    #             else:
    #                 cur += 1
    #
    #         if max_count < cur:
    #             max_count = cur

    i = 0
    j = 0

    while i < n-1:
        j = i + max_count + 1

        while j < n:
            cur = 0
            while i + cur < j and j + cur < n:
                if s[i+cur] != s[j+cur]:
                    j += cur
                    break;
                else:
                    cur += 1

            if max_count < cur:
                max_count = cur
            j += 1

        i += 1

    print(max_count)




resolve()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

N = int(input())
S = np.array([ord(x) for x in input().rstrip()],dtype=np.int64)

MOD = 10**9 + 9
base = 1234

def cumprod(arr):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr,Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    return arr.ravel()[:L]

x = np.full(N,base,np.int64); x[0] = 1
power = cumprod(x)
x = np.full(N,pow(base,MOD-2,MOD),np.int64); x[0] = 1
power_inv = cumprod(x)

# rolling hash
H = S * power % MOD
Hcum = H.cumsum() % MOD

def test(n):
    # 長さnの文字列で2回現れるものが存在する
    x = (Hcum[n-1:N] - Hcum[:N-n+1] + H[:N-n+1]) % MOD
    x *= power_inv[:N-n+1]
    x %= MOD
    # 距離n以上離れたところで連番が存在しないといけない
    ind = x.argsort()
    x = x[ind]
    is_left_end = np.zeros(N-n+1,np.bool)
    is_left_end[1:] = (x[1:] != x[:-1])
    is_left_end[0] = 1
    is_right_end = np.zeros(N-n+1,np.bool)
    is_right_end[:-1] = (x[:-1] != x[1:])
    is_right_end[-1] = 1
    gap = ind[is_right_end] - ind[is_left_end]
    return gap.max() >= n

left = 0 # 存在
right = N+1 # 非存在
while left + 1 < right:
    mid = (left + right)//2
    if test(mid):
        left = mid
    else:
        right = mid

answer = left
print(answer)

Submission status: Wrong Answer

Solution code:
N=int(input())
S=list(input())
Hitoshi=[[i==j for j in S] for i in S]
DP=[[0]*N for i in range(N)]#DP[i][l]:iまで見たときのl始まりの部分列の最長
for i in range(1,N):
  s=S[i]
  for l,d in enumerate(DP[i-1]):
    if s==S[l+d] and l+d<i-d:
      newd=d+1
    else:
      newd=0
    DP[i][l]=newd
print(max([max(i) for i in DP]))

Submission status: Wrong Answer

Solution code:
import re

n = int(input())
s = input()
l = (n//2) 
flag=0
for i in range(l, 0, -1):
    if i==1:
        break
    for j in range(l-i+1+1):
        if len(re.findall(s[j:j+i], s))>=2:
            flag=1
            break
    if flag:
        break
    
if(i==1):
    print(0)
else:
    print(i)

Submission status: Wrong Answer

Solution code:
import collections
import sys
n=int(input())
s=input()
if n==2:
  if s[0]==s[1]:
    print(1)
  else:
    print(0)
  sys.exit()
l=0;r=n//2+1
while l!=r:
  x=(l+r)//2
  L=[]
  for i in range(n+1-x):
    L.append(s[i:i+x])
  L2=collections.Counter(L)
  if L2.most_common()[0][1]>=2:
    l=x+1
  else:
    r=x
print(l-1)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = [ord(s) for s in input()]
# N = 5000
# S = [ord(s) for s in input()]

c = 0
for i in range(1, N):
    d = 0
    for s_j, t_j in zip(S, S[i:]):
        if s_j == t_j:
            d += 1
        else:
            c = max(c, min(d, i))
    c = max(c, min(d, i))

# print(S, t)
print(c)

Submission status: Wrong Answer

Solution code:
def longestDupSubstring(S):
    A = [ord(c) - ord('a') for c in S]
    mod = 2**63 - 1

    def test(L):
        p = pow(26, L, mod)
        cur = reduce(lambda x, y: (x * 26 + y) % mod, A[:L], 0)
        seen = {cur}
        get = dict()
        get[cur] = L-1
        for i in xrange(L, len(S)):
            cur = (cur * 26 + A[i] - A[i - L] * p) % mod
            # print("Ran for :",i)
            if cur in seen and i - get[cur] + 1 > L: return i - L + 1
            seen.add(cur)
            try:
                p = get[cur]
            except:
                get[cur] = i

    res, lo, hi = 0, 0, len(S)
    while lo < hi:
        mi = (lo + hi + 1) / 2
        pos = test(mi)
        if pos:
            lo = mi
            res = pos
        else:
            hi = mi - 1
    return len(S[res:res + lo])
n = raw_input()
s = raw_input()
print(longestDupSubstring(s))

Submission status: Wrong Answer

Solution code:
from collections import Counter
input()
s = input()
ls = list(s)
cols = Counter(ls)
# ２個以上ある文字のリスト作成
dbls =[]
for k, v in cols.items():
  if v >= 2:
    dbls.append(k)

left = 0
right = 0
word = ""
ans = 0
# 順番に見ていく

while right < len(s):
  if s[right] in dbls:
    word += s[right]
    if s[right+1:].find(word) >= 0:
      ans = max(ans, len(word))
      right += 1
    else:
      word = ""
      left = max(left + 1, right)
      right = left
  else:
    word = ""
    left = max(left + 1, right)
    right = left

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
S=input()
a=0
ans=0
while a<=n-2-ans:
    for j in range(a+1+ans,n-ans):
        if S[j]==S[a]:
            while ans<=n-j-1:
                if S[a+ans]==S[j+ans] and a+ans<j:
                    ans+=1
                else:
                    break
    a+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
cnt = 0
max = 0
N = int(input())
S = list(input())
x = [-1] * N
for i in range(N-1):
    for j in range(i+1,N):
        if x[i] == -1:
            if x[j] == -1 and S[i] == S[j]:
                x[j] = i
                x[i] = i
                max = 1

for i in range(N-1):
    if x[i+1] - x[i] == 1:
        cnt += 1
    else:
        if cnt > max:
            max = cnt + 1
        cnt = 0
print(max)

Submission status: Wrong Answer

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

ans = 0
for i in range(N//2, 0, -1):
    for j in range(i):
        l = [S[j: i+j]] + [S[i+j+k: i*2+j+k] for k in range(max(N-2*i, 1))]
        if len(l) > len(set(l)):
            ans = i
            break
    if ans > 0:
        break
        
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n=int(input())
s=input()

dic=defaultdict(list)
ans=0
for i in range(n-1):
    if (n-i-1) <=ans*2:
        print(ans)
        exit()
    for j in range(i+1,n+1):
        ss=s[i:j]
        if dic[ss]==[]:
            dic[ss]+=[j]
            continue
    
        elif max(dic[ss])<=i:
            dic[ss]+=[j]
        if len(dic[ss])>=2 and len(ss)>ans:
            ans=len(ss)

Submission status: Wrong Answer

Solution code:
def create_table(pattern):
    table = [0 for _ in range(len(pattern))]
    j = 0
    for i in range(1, len(pattern)):
        if pattern[i] == pattern[j]:
            j += 1
            table[i] = j
        else:
            table[i] = j
            j = 0
    print(pattern,table)
    return table
N = int(input())
S = input()
ans = 0
for i in range(N):
    ans = max(ans, max(create_table(S[i:])))
print(ans)

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
s = input()
top = math.floor(n/2)
swi = 0

for k in range(n):
    if top - k - 1 < 0 or swi > 0:
        break
    else:
        for i in range(top + k * 2):
            if s[(top-k)+i:n].count(s[i:(top-k)+i]) > 0:
                swi = top - k
                break

print(swi)

Submission status: Wrong Answer

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

import re

result = re.sub(r'^.*?(.+).*?\1.*?$', r'\1', s)

if result != s:
  print(len(result))
else:
  print(0)

Submission status: Wrong Answer

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

ans = 0
p1 = 0
while p1 < N - 1:
  p1c = p1
  p2 = p1 + 1
  maxcnt = 0
  while p2 < N:
    cnt = 0
    while p2 < N and S[p1] == S[p2]:
      p1 += 1
      p2 += 1
      cnt += 1
      
    maxcnt = max(maxcnt, cnt)
    ans = max(ans, cnt)
    p1 = p1c
    p2 += 1
    
  p1 += maxcnt + 1

print(ans)

Submission status: Wrong Answer

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

cache = {}
for i in range(n):
    cache[i] = 0

res = 0
for i in range(n):
    for j in range(i + 1, n):
        tt = max(cache[i], cache[j])
        mx = min(j - i, n - j)
        if tt >= mx:
            break
        while tt <= mx:
            tt += 1
            if s[i:i+tt] != s[j:j+tt]:
                break
        res = max(res, tt - 1)
        cache[i] = tt - 1
        cache[j] = tt - 1

print(res)

Submission status: Wrong Answer

Solution code:
N = int(input())
St = input()
ans = 0

#初期化
dp=[[0 for i in range(N)] for j in range(N)]

#DP:dp[i][j] Sのi文字目までとj文字目以降の最大マッチング
for i in range(N-1):
  for j in range(N-1, i-1, -1):
    dp[i+1][j-1] = max(dp[i][j-1],dp[i+1][j])
    if St[i+1] == St[j-1]:
      dp[i+1][j-1] = max(dp[i+1][j-1], dp[i][j]+1)
      
ans = 0
for i in range(N):
  ans = max(ans, dp[i][i])
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
dp = [[0]*(n) for i in range(n)]
for i in range(n):
    dp[0][i] = 1 if s[0] == s[i] else 0
ans = 0
for i in range(1,n):
    for j in range(i,n):
        if s[i] == s[j]:
            if dp[i-1][j-1] > 0:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = 1
for i in range(n):
    for j in range(i + 1,n):
        if ans < dp[i][j]:
            ans = dp[i][j]
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque
n = int(input())
s = input()
dic = defaultdict(list)
used = [0]*(n+1)
ans = 0


def search(lst, a):
    global ans
    if ans < a:
        ans = a
    n_dic = defaultdict(list)
    for i in lst:
        used[i] = 1
        if used[i+1] == 0 and i < n-1:
            n_dic[s[i+1]].append(i+1)
    for n_lst in n_dic.values():
        if len(n_lst) >= 2:
            search(n_lst, a+1)
        else:
            used[n_lst[0]] = 1

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

for lst in dic.values():
    c_lst = []
    if len(lst) >= 2:
        search(lst, 1)
    else:
        used[lst[0]] = 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter
import math
import heapq
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()

n = ni()
s = input()
d = []
ln = len(s)
flag = False
for l in range(ln//2)[::-1]:
    for i in range(ln - l + 1):
        c = s[i:i+l+1]
        if c not in d:
            d.append(c)
        else:
            print(len(c))
            flag = True
            break
    if flag:
        break
if flag is False:
    print(0)

Submission status: Wrong Answer

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

ans = 0
for i in range(1,n-1):
    t = s[i:n]
    count = 0
    l = 0
    r = n
    if l >= ans:
        start = False
        for j in range(len(t)):
            if i == 2 and j == 3:
                pass
            if s[j] == t[j] and l < r-1:
                if not start:
                    r = j + i
                    start = True
                count += 1
                l = j
            elif start:
                ans = max(count,ans)
                count = 0
                start = False
                r = n
                l = 0
        ans = max(count,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n=int(input())
s=input()

dic=defaultdict(list)
ans=0
for i in range(n-1):
    for j in range(i+1,n+1):
        ss=s[i:j]
        if dic[ss]==[]:
            dic[ss]+=[j]
            continue
    
        elif max(dic[ss])<=i:
            dic[ss]+=[j]
        if len(dic[ss])>=2 and len(ss)>ans:
            ans=len(ss)
        
        if (n-i) <=ans:
            print(ans)
            exit()

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
p = 0
q = 0
def check(l):
  global p, q
  for i in range(p, N-l):
    s = S[i:i+l]
    j = S.find(s, max(q, i+l))
    if not j < 0:
      p = i
      q = j
      return True
  return False
a = 1
b = N
while a < b:
  i = (a + b)//2
  if not check(i):
    b = i
  else:
    if a == i:
      break
    a = i
r = b-1
print(r)

Submission status: Wrong Answer

Solution code:
import math
import heapq
from bisect import bisect_right, bisect_left
from collections import defaultdict, Counter
import itertools
import sys
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7
INF = float("inf")


def main():
    n = int(input())
    s = list(input())
    if len(set(s)) == 1:
        print(n // 2)
        exit()

    ans = 0
    for i in range(n):
        le, k = -1, 0
        for j in range(i+1, n):
            if s[i] == s[j] and le == -1:
                le = j - i
                k += 1
                #print(i, s[i], j, s[j], "START")
            elif i + k < n and k < le and s[i + k] == s[j]:
                #print(i+k, s[i + k], j, s[j], "MIDDLE")
                k += 1
            else:
                ans = max(ans, k)
                le = -1
                k = 0
                if s[i] == s[j] and le == -1:
                    le = j - i
                    k += 1
                    #print(i, s[i], j, s[j], "START")
            ans = max(ans, k)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
dp = [[0] * (N+2) for _ in range(N+2)]
ans = 0
for i in range(1,N+1):
    for d in range(N+1-i):
        print(i,d)
        if S[i-1] == S[i-1+d]:
            dp[i][d] = min(d, dp[i-1][d]+1)
            ans = max(ans, dp[i][d])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter
import math
import heapq
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()

n = ni()
s = input()
d = []
ln = len(s)
flag = False
for l in range(1, ln//2)[::-1]:
    for i in range(ln - l + 1):
        c = s[i:i+l+1]
        if c not in d:
            d.append(c)
        else:
            print(len(c))
            flag = True
            break
    if flag:
        break
if flag is False:
    print(0)

Submission status: Wrong Answer

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

left = 0
right = n//2
mid = right//2
ans =[]
flag2 =0
while right-left>=2:
    for i in range(n-mid*2):
        flag1 =0
        for j in range(i+mid,n-mid):
            if s[i:i+mid] == s[j:j+mid]:
                left = mid
                mid = (right+left)//2
                flag1 = 1
                flag2 =1
        #        print("find",mid,i,j)
                ans.append(mid)
    if flag1 ==0:
        right = mid
        mid =(right+left)//2
        #print("not found")


for i in [mid,right]:
    for j in range(n-2*i):
        for k in range(j+i,n-i):
            if s[j:j+i] == s[k:k+i]:
                ans.append(i)
                break
if flag2:
    print(max(ans)+1)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter

def main():
    n = int(input().strip())
    s = input().strip()
    ans = 0
    for i in range(len(s)):
        c = 0
        s_i = i
        s_j = i+1
        for j in range(i+1, len(s)):
            if s[i] == s[j]:
                if s_i + c == s_j:
                    continue
                if c == 0:
                    s_i = i
                    s_j = j
                i += 1
                c += 1
            else:
                c = 0
            ans = max(ans, c)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
n = int(input())
s = input()
m = len(s)//2
li = []
for i in range(m,0,-1):
    for ni in range(0,n-i+1):
        if s[ni:ni+i] not in li:
            li.append(s[ni:ni+i])
        else:
            print(i)
            sys.exit()
print(0)

Submission status: Wrong Answer

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

ans = 0
p1 = 0
while p1 < N - 1:
  p1c = p1
  p2 = p1 + 1
  while p2 < N:
    cnt = 0
    while p2 < N and S[p1] == S[p2]:
      p1 += 1
      p2 += 1
      cnt += 1
      if cnt == maxn:
        print(cnt)
        exit()
    ans = max(ans, cnt)
    p1 = p1c
    p2 += 1
    
  p1 += ans + 1

print(ans)