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:
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(1, 11):
        kari = 0
        for j in range(num - i):
            if s[j + i] == s[j]:
                kari += 1
            else:
                ans = max(kari // i, ans)
                kari = 0
        ans = max(kari // i, ans)
    ans = min(ans, num // 2)
    # print(ans)

    # 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: 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
x=l-1
L=[]
for i in range(n+1-x):
  L.append(s[i:i+x])
L2=collections.Counter(L)
L3=[]
c=[]
for i in range(n+1-x):
  L3.append(s[i:i+x])
for i in range(len(L3)):
  if L3[i]==L2.most_common()[0][0]:
    c.append(i)
if max(c)-min(c)>=l-1:
  print(l-1)
else:
  print(l-2)

Submission status: Wrong Answer

Solution code:
N = 13
S = list("strangeorange")

#N = int(input())
#S = input()
ba = ord("a")
for i in range(N):
  S[i] = ord(S[i]) - ba + 1
B = 27
mod = 10 ** 11 + 7
def contain(a, b):
  al = len(a)
  bl = len(b)
  #print(al, a)
  if al > bl: return False
  t = pow(B, al)
  ah = 0; bh = 0
  for i in range(al):
    ah = ah * B + a[i]
    bh = bh * B + b[i]
  for i in range(bl - al + 1):
    if ah == bh: return True
    if i + al < bl:
      #print(i, i + al)
      bh = bh * B + b[i + al] - b[i] * t
  return False
res = 0
for i in range(N):
  for j in range(i + 1, len(S)):
    if j - i > N // 2:
      break
    #print(i, j)
    if contain(S[i: j], S[j: ]):
      #print(i, j, j - i)
      res = max(res, j - i)
print(res)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import re
import sys


def solve(N: int, S: str):
    max_length = 1
    found = False
    for i in range(N):
        is_break = False
        if i + max_length > N:
            break
        while not is_break:
            org = S[i:i + max_length]
            rest = S[i + max_length:N]
            print(org, rest)
            if org in rest:
                max_length += 1
            else:
                is_break = True
    print(max_length - 1)
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
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 > min(lone,ltwo):
        pass
      elif ans > abs(lone-ltwo):
        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:
n = int(input())
s = input()

max_len = 0

zero_fl = 0
last_k = 0
last_j = 0
for i in range(1, (n // 2 + 1)):
    if zero_fl == 1:
        break
    s_closed = set()
    fl = 0
    for j in range(max(0, last_j), n - i + 1):
        if fl == 1:
            break
        ss = s[j:j + i]
        if ss in s_closed:
            j += i - 1
            continue
        s_closed.add(ss)
        for k in range(max(j + i, last_k), n - i + 1):
            sss = s[k:k + i]
            if ss == sss:
                last_k = k
                last_j = j
                max_len = i
                fl = 1
                break
        if j == n - i:
            zero_fl = 1

print(max_len)

Submission status: Wrong Answer

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

import bisect

N = int(input())
s = input().split() 
s = list(s[0])
alf_i = [[] for _ in range(26)]

for i in range(N):
    alf_i[ord(s[i])-97].append(i)


ans=0
max_cnt=0
i=0
while i < N:
    x = bisect.bisect_left(alf_i[ord(s[i])-97], i)
    for j in range(x+1,len(alf_i[ord(s[i])-97])):
        y = alf_i[ord(s[i])-97][j]
        cnt=0
        max_cnt=0
        while y+cnt<N and s[i+cnt]==s[y+cnt]:
            if i+cnt==y:
                break
            cnt+=1
        if max_cnt < cnt:
            max_cnt=cnt
    ans = max(ans,max_cnt)
    
    if max_cnt==0:
        i+=1
    else:
        i+=max_cnt
print(ans)

Submission status: Wrong Answer

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

    maxlen = 0
    for k in range(1, n // 2 + 1):
        strs = {}
        for m in range(n - k + 1):
            p = s[m:m+k]
            # print(k, m, p, strs)
            if p in strs and strs[p] + k <= m:
                maxlen = k
                break
            strs[p] = m
        else:
            break
    
    print(maxlen)


main()

Submission status: Wrong Answer

Solution code:
import math


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


def check(length_s):
    for start_s in range(0, N-length_s):
        check_s = S[start_s:start_s+length_s]
        if length_s > N - start_s - length_s:
            break
        if check_s in S[start_s+length_s:]:
            return True
    return False


max_s = N // 2
length_s = N // 2 // 2
min_s = 0
while True:
    if check(length_s):
        min_s = length_s
        length_s = math.ceil((max_s + length_s) / 2)
    else:
        max_s = length_s
        length_s = math.ceil((min_s + length_s) / 2)
    if length_s == max_s or length_s == min_s:
        break
print(length_s)

Submission status: Wrong Answer

Solution code:

# coding: utf-8

# In[45]:


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


# In[46]:


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[47]:


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[48]:


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

Submission status: Wrong Answer

Solution code:
n = int(input())
s = list(input())
num = [0]*n
for i in range(n):
    if s[i] in s[i+1:]:
        num[i] += 1
        for x in [j for j, x in enumerate(s[i+1:]) if x == s[i]]:
            for y in range(1, i+1+x+1):
                if s[i+1+x-y] == s[i-y]:
                    num[i-y] += 1

print(max(num))

Submission status: Wrong Answer

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

start_n = s_len //2
max_len = 0
for i in range(-start_n, 0):
    search_s = s[i:]
    if s.count(search_s) >= 2:
        if max_len < len(search_s):
            max_len = len(search_s)
print(max_len)

Submission status: Wrong Answer

Solution code:
n = int(input())
S = input()
m = n//2
l,r = 0,n-1
ans = 0
while l<=r:
    m = (l + r) // 2
#    print("m = ", m)
    for i in range(min(m,n-2*m+1)) :
        # 切り取る
        sub = S[i :i + m]
#        print("sub=", sub)
#        print("i=", i)
        fl = False
        Se = set()
        for j in range(n - m + 1) :
#            print("j=", j)
            sub2 = S[j :j + m]
            Se.add(sub2)
#        print(Se)
        if len(Se) < n-m+1:  # 共通する部分がある場合
            fl = True
            l = m+1
            ans = l-1
#            print(l-1,"にて共通部分有")
            break
    else:
        r = m-1
#        print(r+1,"にて共通部分無")
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
    elif s==S[l]:
      newd=1
    else:
      newd=0
    DP[i][l]=newd
print(max([max(i) for i in DP]))

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)) == 2:
        if s[:n // 2][0] not in 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:
def slove():
    import sys
    import collections
    import copy
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    s = str(input().rstrip('\n'))
    c = collections.Counter(s).most_common()
    ml = n // 2

    d = collections.defaultdict(list)
    for i in range(n):
        d[s[i]] += [[i, i]]
    ans = 1
    ll = 2
    while True:
        td = collections.defaultdict(list)
        ad = collections.defaultdict(list)
        for k, v in d.items():
            if len(v) > 1:
                for i in range(1, len(v)):
                    if v[i-1][1] <= v[i][0]:
                        ans = len(k)
                        ad[v[i-1][0]]
                        ad[v[i][0]]
        for k, v in ad.items():
            td[s[k:k+ll]] += [[k, k+ll]]
        if len(td) != 0:
            if ll > ml:
                print(ans)
                exit()
            else:
                d = copy.deepcopy(td)
                ll += 1
        else:
            print(ans)
            exit()


if __name__ == '__main__':
    slove()

Submission status: Wrong Answer

Solution code:
def solve(n, s, MOD):
    d = 27
    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
            appeared.add(acc[i - l])
            # print(l, c0, c1, t, acc, appeared)
            if t in appeared:
                return l
            acc.append(t)

    return 0


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

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs,heapq as hq
input = sys.stdin.readline
sys.setrecursionlimit(100000)
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def search(a,n):
    se = dict()
    data = []
    for i in range(0,len(a)-n+1):
        kkk = a[i:i+n]
        kkk = "".join(kkk)
        if In(kkk,data):
            if hq.heappop(se[kkk]) <= i-n:
                    return True
            else:
                hq.heappush(se[kkk],i)
        else:
            bs.insort(data,kkk)
            se[kkk] = [i]
    return False
def solver():
    n = onem()

    s = list(input())
    l = 0
    r = n//2
    for i in range(n):
        mid = -(-(l+r)//2)
        ans = search(s,mid)
        if l == mid:
            break
        if ans:
            l = mid
        else:
            r = mid-1
    print(l)




solver()

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):
            t = (top-k)+i
            if s[t:n].count(s[i:t]) > 0:
                swi = top - k
                break

print(swi)

Submission status: Wrong Answer

Solution code:
n = int(input())
S = input()
k = n//2

for l in range(k, 0, -1):
    check = set()
    word = S[0:l]
    check.add(word)

    for i in range(n-l):
        word = word[1:] + S[l+i]
        if word in check:
            print(l)
            exit()
        else:
            check.add(word)

print(0)

Submission status: Wrong Answer

Solution code:
# ABC141e
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n = int(input())
s = input()[:-1]

setsu = []
for i in range(n):
    setsu.append(s[i:])
# print(setsu)
setsu.sort()
# print(setsu)

fm = []

for i in range(n-1):
    l = 0
    if (len(setsu[i]) > len(setsu[i + 1])):
        l = setsu[i].count(setsu[i + 1])
    else:
        l = setsu[i+1].count(setsu[i])
    fm.append([min(len(setsu[i]), len(setsu[i + 1])), l, i])
# print(fm)

fm.sort(reverse=True)

# print(fm)
ind = -1
for i in range(len(fm)):
    if (fm[i][1] > 1):
        ind = i
        break
# print(ind)

# print(setsu[fm[ind][2]])

print(len(setsu[fm[ind][2]]) if ind != -1 else 0)

Submission status: Wrong Answer

Solution code:
if __name__ == '__main__':
    N = int(input())
    S = input()
    for k in range(N//2, 0, -1):
        for i in range(N-k-k+1):
            l = S[i:i+k]
            for j in range(N-k-(k-1)):
                l2 = S[k + j:k + j + k]
                if l == l2:
                    print(k)
                    exit()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Sep 15 22:04:50 2019
ABC141E
@author: maezawa
"""

n = int(input())
s = list(input())
maxcnt = 0
cnt = 0
i = 0
j = 1
di = 0

while True:
    if s[i+di] == s[j+di]:
        cnt += 1
        if maxcnt < cnt:
            maxcnt = cnt
        if i+di+1 == j or j+di+1 == n:
            cnt = 0
            j += 1
            di = 0
            if j >= n-1:
                i += 1
                if i == n-1:
                    break
                j = i + 1
                di = 0
        else:
            di += 1
            
    else:
        j += 1
        if j+di >= n:
            i += 1
            j = i + 1
            di = 0
            if i == n-1:
                break

print(maxcnt)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
def main():
    from bisect import bisect_right
    import sys
    input = sys.stdin.readline
    N = int(input())
    M = N // 2 + N % 2
    S = input()
    D = {c:[] for c in "abcdefghijklmnopqrstuvwxyz"}
    for i in range(N):
        D[S[i]].append(i)
    l = 0
    m = 0

    for l in range(N):
        if m >= N//2:
            break

        print(m)
        c = S[l]
        d = D[c]
        j = bisect_right(d, l+m)
        if j == N:
            continue
        for r in d[j:]:
            k = 1
            while S[l+k] == S[r+k] and l+k < r and r+k < N:
                k += 1
            #if k > m: print((l, r, k), S[l:l+k], S[r:r+k])
            m = max(k, m)
    print(m)

def gen():
    import random
    N = 5*10**3
    print(N)
    a = ord('a')
    #print("".join(chr(a + random.randint(0, 3)) for i in range(N)))
    print("".join("a" if i % 2 == 1 else "b" for i in range(N)))
if 1 == 0:
    gen()
else:
    main()

Submission status: Wrong Answer

Solution code:
import sys
import collections
import copy
import math
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
N = int(input())
S = input()
chk = N//2
ans_dic = {}
fin = 0
for i in reversed(range(chk+1)):
    for j in range(N-i+1):
        if S[j:i+j] in ans_dic.keys():
            fin = 1
            print(i)
            break
        else:
            ans_dic[S[j:i+j]] = 1
    if fin == 1:
        break
    if i == 0:
        print(0)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input() 
nd = n // 2

for nn in range(nd):
  na = nd - nn
  for a in range(nn + 2):
    x = s[a:(na + a)]
    y = s[(na + a):]
    if x in y:
      print(na)
      exit()
print(0)

Submission status: Wrong Answer

Solution code:
N = int(input())
M = N//2
S = input()
y = 0
for i in range(M)[::-1]:
    i=i+1
    seter = set()
    x = N-i+1
    for j in range(x):
        seter.add(S[j:j+i])
        #print(S[j:j+i])
    if x > len(seter):
        y = i
        break
print(y)

Submission status: Wrong Answer

Solution code:
import sys
import heapq
import bisect

mod = 10**9+7
dd = ((-1,0),(1,0),(0,-1),(0,1))

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def S(): return(sys.stdin.readline()[:-1])

def GCD(a,b):
    while b!=0:
        a,b = b,a%b
    return a

def LCM(a,b):
    return a * b // GCD(a,b)

def main():
    N = I()
    s = S()

    ans = 0

    que_cur = set()
    for i in range(N):
        que_cur.add(s[i])

    s = "_" + s + "_"

    while True:
        que_nxt = set()
        for q in que_cur:
            List = s.split(q)
            if len(List)>=3:
                dic = {}
                for x in List:
                    if len(x)>=1:
                        dic[x[0]] = dic.get(x[0],0)+1
                for k in dic:
                    if dic[k] >= 2:
                        que_nxt.add(q+k)
        if len(que_nxt)==0:
            break
        ans += 1
        que_cur = set()
        for q in que_nxt:
            que_cur.add(q)

    return(ans)





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

Submission status: Wrong Answer

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

ans = 0
flag = False

for i in range(N):
    for j in range(i+1, N//2+1):
        if S[i:j] in S[j:]:
            flag = True
            if len(S[i:j]) > ans:
                ans = len(S[i:j])

print(ans)

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs,heapq as hq
sys.setrecursionlimit(100000)
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def search(a,n):
    se = dict()
    data = []
    for i in range(0,len(a)-n+1):
        kkk = a[i:i+n]
        kkk = "".join(kkk)
        if In(kkk,data):
            if hq.heappop(se[kkk]) <= i-n:
                    return True
            else:
                hq.heappush(se[kkk],i)
        else:
            bs.insort(data,kkk)
            se[kkk] = [i]
    return False
def solver():
    n = onem()

    s = list(input())
    l = 0
    r = n//2
    for i in range(n):
        mid = -(-(l+r)//2)
        ans = search(s,mid)
        if l == mid:
            break
        if ans:
            l = mid
        else:
            r = mid-1
    print(l)




solver()

Submission status: Wrong Answer

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


def lcs(s1, s2):
    len1, len2 = len(s1), len(s2)
    ir, jr = 0, 0
    for i1 in range(len1):
        i2 = s2.find(s1[i1])
        while i2 >= 0:
            j1, j2 = i1+1, i2+1
            while j1 < len1 and j2 < len2 and s2[j2] == s1[j1]:
                if j1-i1 > jr-ir:
                    ir, jr = i1, j1
                j1 += 1
                j2 += 1
            i2 = s2.find(s1[i1], i2+1)
    return jr+1-ir


ans = 0
for i in range(1, N):
    ls = lcs(S[:i], S[i:])
    ans = max(ans, ls)
    # if len(ls) > ans:
    #     ans = len(ls)


print(ans)

Submission status: Wrong Answer

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

ans = 0
for i in range(n-ans):
    tmp = 0
    if n - ans > ans:
        for j in range(i+1, n-ans):
            if s[i] == s[j]:
                tmp += 1
                ans = max(ans, tmp)
                for k in range(1,n-j):
                    if s[i+k] == s[j+k] and i+k < j-1:
                        tmp += 1
                        ans = max(ans, tmp)
    else:
        break
print(ans)

Submission status: Wrong Answer

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

a1 = 0
a2 = 1
l = 0
first_point = -1
ans = 0

while a1 < n-1:
    if a2 > n-1:
        ans = max([ans, l])
        l = 0
        first_point = -1
        a1 += 1
        a2 = a1 + 1
        if a2 > n-1:
            break
        
    
    if a1 == first_point:
        # 重複できないのでここで一旦終わり
        ans = max([ans, l])
        l = 0
        first_point = -1
        
    if a1 == a2:
        # 同じ点のときは前を一歩進める
        l = 0
        a2 += 1
        continue
        
    if s[a1] == s[a2]:
        # 2点の文字が一緒だったら次も一緒か確かめる
        l += 1
        a1 += 1
        a2 += 1
        if first_point == -1:
            #a2の初期値を登録する
            first_point = a2-1
    else:
        # 異なってたら前へ進む
        l = 0
        a2 += 1
        
ans = max([ans, l])

print(ans)

Submission status: Wrong Answer

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

def is_ok(l):
    hs = set()
    for i in range(N-l+1):
        h = hash(S[i:i+l])
        if h in hs:
            return True
        hs.add(h)
    return False

ok = 0
ng = N//2+1
while ng-ok > 1:
    m = (ng+ok)//2
    if is_ok(m):
        ok = m
    else:
        ng = m
print(ok)

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
if f == False:
    print(0)

Submission status: Wrong Answer

Solution code:
N=int(input())
S=input()
d={}
for i in range(N):
  for j in range(i,N+1):
    now=S[i:j]
    if now in d:
      d[now]+=1
    else:
      d.setdefault(now,1)
twice={k:v for k, v in d.items() if v>=2}
v1=sorted(twice.keys(), key=len)[::-1] 
for v in v1:
    f=S.find(v)+len(v)-1
    if v in S[f:]:
        break
print(len(v))

Submission status: Wrong Answer

Solution code:
import time
N = int(input())
S = input()
limit_time = time.time() + 1.80

for l in range(N//2, 0, -1):
    tried = set()
    for i in range(N-2*l+1):
        part = S[i:l+i]
        if part in tried:
            continue
        tried.add(part)
        for j in range(l+i, N-l+1):
            cmp = S[j:j+l]
            if cmp == part:
                print(l)
                import sys
                sys.exit()
            if time.time() > limit_time:
                print(0)
                import sys
                sys.exit()
    del tried
else:
    print(0)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import re
import sys


def solve(N: int, S: str):
    max_length = 1
    found = False
    for i in range(N // 2):
        is_break = False
        while not is_break:
            org = S[i:i + max_length]
            rest = S[i + max_length:N]
            # print(org, rest)
            if org in rest:
                max_length += 1
            else:
                is_break = True
    print(max_length - 1)
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def slove():
    import sys
    import collections
    import copy
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    s = str(input().rstrip('\n'))
    c = collections.Counter(s).most_common()
    ml = n // 2

    d = collections.defaultdict(list)
    for i in range(n):
        d[s[i]] += [[i, i]]
    ans = 0
    ll = 2
    while True:
        td = collections.defaultdict(list)
        ad = collections.defaultdict(list)
        for k, v in d.items():
            if len(v) > 1:
                for i in range(1, len(v)):
                    if v[i-1][1] <= v[i][0]:
                        ans = len(k)
                        ad[v[i-1][0]]
                        ad[v[i][0]]
        for k, v in ad.items():
            td[s[k:k+ll]] += [[k, k+ll]]
        if len(td) != 0:
            d = copy.deepcopy(td)
            ll += 1
        else:
            print(ans)
            exit()


if __name__ == '__main__':
    slove()

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
            appeared.add(acc[i - l])
            # print(l, c0, c1, t, acc, appeared)
            if t in appeared:
                return l
            acc.append(t)

    return 0


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

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
l = 0
r = 1
ans = 0
for l in range(-(-N//2)):
    if S[l] not in S[l+1:]:
        continue
    for r in range(l+1, -(-N//2)+1):
        s = S[l:r]
        if S[r:].count(s) < 1:
            break
        if len(s) > ans:
            ans = len(s)
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
            appeared.add(acc[i - l])
            print(l, c0, c1, t, acc, appeared)
            if t in appeared:
                return l
            acc.append(t)

    return 0


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

Submission status: Wrong Answer

Solution code:
n=int(input())
s=input()
for l in range(n//2,n+1):
  for i in range(l+1):
    k=s[i:i+(n-l)]
    r=s[:i]+s[i+n-l:]
    if k in r:
      print(n-l)
      exit()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

len_sub = N//2
while len_sub > 1:
    dict_subwords = defaultdict(int)
    for i in range(N-len_sub+1):
        subword = S[i:i+len_sub]
#        print(subword)
        dict_subwords[subword] += 1
#    print(dict_subwords)
    if max(dict_subwords.values()) > 1:
        print(len_sub)
        exit()
    len_sub -= 1
print(0)

Submission status: Wrong Answer

Solution code:
import heapq as hq

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

sw=0
for L in range(N-1,0,-1):
  tmp=[]
  for i in range(N-L+1):
    hq.heappush(tmp,S[i:i+L])
  tmp2=""
  #print(tmp)
  for i in range(N-L+1):
    tmp1=hq.heappop(tmp)
    if tmp1==tmp2:
        sw=1
        break
    tmp2=tmp1
  if sw==1:
    break
print(L if sw==1 else 0)