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
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):
#  print(s[right], word)
  if s[right] in dbls:
    word += s[right]
    if s[right+1:].find(word) >= 0:
      ans = max(ans, len(word))
      right += 1
    else:
      word = word[1:]
      left += 1
      right = max(left, right)
  else:
    word = ""
    left = max(left + 1, right + 1)
    right = left

print(ans)

Submission status: Wrong Answer

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

res = 0

for k in range(1,n//2+10):
    d = [0]*n
    for i in range(n-k):
        if i+k <= n-1 and s[i] == s[i+k]:
            d[i] = min(k,d[i-1]+1)
            res = max(res,d[i])
print(res)

Submission status: Wrong Answer

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


r = 0
ans = 0
for l in range(N):

    while True:
        print(S.rfind(S[l:r+1]), S[l:r+1], l, r)
        
        if S.rfind(S[l:r+1]) >= r+1:
            r += 1
            ans = max(ans, r-l)
        else:
            break

print(ans)

Submission status: Wrong Answer

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

res = 0

for k in range(1,n//2+1):
    d = [0]*n
    for i in range(n-k):
        if i+k <= n-1 and s[i] == s[i+k]:
            d[i] = min(k,d[i-1]+1)
            res = max(res,d[i])
print(res)

Submission status: Wrong Answer

Solution code:
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline


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

    ans = 0

    for i in range(1,n):
        count = 0
        top = 0
        flag = False
        for j,k in zip(s, s[i:]):
            if flag:
                if j == k:
                    count += 1
                else:
                    top = max([top, count])
                    flag = False
            else:
                if j == k:
                    count = 1
                    flag = True
        ans = min([ans, top])
    print(ans)

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):
#  print(s[right], word)
  if s[right] in dbls:
    word += s[right]
    if s[right+1:].find(word) >= 0:
      ans = max(ans, len(word))
      right += 1
    else:
      word = word[1:]
      left += 1
      right = max(left, right)
  else:
    word = ""
    left = max(left + 1, right + 1)
    right = left

print(ans)

Submission status: Wrong Answer

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

s_map = {}
for s in S:
    if not s in s_map:
        s_map[s] = 0
    s_map[s] += 1

cnt = 0
l = ''
ln = {}

for s in S:
    c = s_map[s]
    if c >= 2:
        l += s
        if not l in ln:
            ln[l] = 0
        ln[l] += 1
    else:
        l = ''

max_l = 0
for k, v in ln.items():
    if v >= 2:
        l = len(k)
        if max_l < l:
            max_l = l

print(max_l)

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, 6):
        kari = 0
        for j in range(num - i):
            if s[j + i] == s[j]:
                kari += 1
            else:
                ans = max(kari // i, ans)
                kari = 0
        aaa = ((kari // i) // 2) * i
        ans = max(aaa, 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:
n = int(input())
s = input()
dic = {}
for i in range(n):
    for j in range(i+1,i+(n+1-i)//2+1):
        t = s[i:j]
        if t not in dic:
            dic[t] = []
        dic[t].append(i)
ans = 0
for k,v in dic.items():
    if len(v) < 2:
        continue
    l,r = v[0], v[-1]
    if l+len(k)-1 < r:
        ans = max(ans, len(k))
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
n = int(input())
s = input()
def split_list(l, n):
    """
    リストをサブリストに分割する
    :param l: リスト
    :param n: サブリストの要素数
    :return: 
    """
    for idx in range(0, len(l), n):
        yield l[idx:idx + n]

half_n = n // 2
def get_ans():
    for i in range(half_n):
        cand = list(split_list(s, half_n-i))
        cand2 = set(cand)
        if len(cand) != len(cand2):
            return(half_n-i)
print(get_ans())

Submission status: Wrong Answer

Solution code:
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline


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

    ans = 0

    for i in range(1,n):
        count = 0
        top = 0
        flag = False
        for j,k in zip(s, s[i:]):
            if flag:
                if j == k:
                    count += 1
                else:
                    top = max([top, count])
                    flag = False
            else:
                if j == k:
                    count = 1
                    flag = True
        ans = max([ans, top])
    print(ans)

Submission status: Wrong Answer

Solution code:
def lcp(s, t):  
  n = min(len(s),len(t));  
  for i in range(0,n):  
    if(s[i] != t[i]):  
      return s[0:i];  
  else:  
    return s[0:n];  

n = int(input())
str = input()
lrs = ''
for i in range(0,n):  
  for j in range(i+1,n):  
    x = lcp(str[i:n],str[j:n])
    if(len(x) > len(lrs)):  
      lrs=x;    
print(len(lrs))

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[i+j+k:i+k+k+j]
                if l == l2:
                    print(k)
                    exit()
    print(1)

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 = word[1:]
      left += 1
      right = max(left, right)
  else:
    word = ""
    left += max(left + 1, right + 1)
    right = left

print(ans)

Submission status: Wrong Answer

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


def search(L, a, modulus, n, nums):
    """
    Rabin-Karp with polynomial rolling hash.
    Search a substring of given length
    that occurs at least 2 times.
    @return start position if the substring exits and -1 otherwise.
    """
    # compute the hash of string S[:L]
    h = 0
    for i in range(L):
        h = (h * a + nums[i]) % modulus
            
    # already seen hashes of strings of length L
    seen = {h} 
    # const value to be used often : a**L % modulus
    aL = pow(a, L, modulus) 
    for start in range(1, n - L + 1):
        # compute rolling hash in O(1) time
        h = (h * a - nums[start - 1] * aL + nums[start + L - 1]) % modulus
        if h in seen:
            return start
        seen.add(h)
    return -1

n = int(input())    
S = input().strip()

# convert string to array of integers
# to implement constant time slice
nums = [ord(S[i]) - ord('a') for i in range(n)]
# base value for the rolling hash function
a = 26
# modulus value for the rolling hash function to avoid overflow
modulus = 2**32

# binary search, L = repeating string length
left, right = 1, n
while left <= right:
    L = left + (right - left) // 2
    if search(L, a, modulus, n, nums) != -1:
        left = L + 1
    else:
        right = L - 1
        
start = search(left - 1, a, modulus, n, nums)
rep = S[start: start + left - 1]
rep2 = rep[::-1]
l = S.index(rep)
r = n - S[::-1].index(rep2) - 1
if r - l < 2 * len(rep):
        ans = (r - l + 1) // 2
        if ans % 2 == 1:
                ans -= 1
else:
        ans = min(r - l, len(rep))
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = list(x for x in input())
l = [0] * n

for i in range(n):
  for j in range(i+1, n):
    if s[i] == s[j]:
      l[i] = l[i-1] + 1
      l[j] = l[j-1] + 1
print(max(l))

Submission status: Wrong Answer

Solution code:
alpha2num = lambda c: ord(c) - ord('a') + 1

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

ans = ''
len_ans = 0

alpha = 'abcdefghijklmnopqrstuvwxyz'
alpha = list(alpha)

l = [0] * 27
c = []

#for i in alpha:
#    tmp = [j for j, x in enumerate(S) if x == i]
#    if len(tmp) >= 2:
#        for j in range(len(tmp)):
#            l.append(tmp[j])



for i in range(len(alpha)):
    tmp = [j for j, x in enumerate(S) if x == alpha[i]]
    if len(tmp) >= 2:
        l[i+1] = (len(tmp))
        for j in range(len(tmp)):
            c.append(tmp[j])
c.sort()

#print(l)
#print(c)

t = [0] * 27

ans = []

for i in range(N):
    t = [0] * 27
    for j in range(i, N):
        if t[alpha2num(S[j])] + 1 <= l[alpha2num(S[j])]//2:
            t[alpha2num(S[j])] += 1
        else: 
            ans.append(''.join(S[i:j]))
            break

#print(ans)
ans2 = [x for x in set(ans) if ans.count(x) > 1]
#print(ans2) 


ans = 0
for i in range(len(ans2)):
    tmp = len(ans2[i])
    ans = max(ans, tmp)

print(ans)

Submission status: Wrong Answer

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

X = N // 2
ans = 0
for i in range(X):
    LONG = X - i
    for i in range(N-LONG+1):
        FRONT=''
        MIDDLE=''
        BACK=''
        for j in range(N):
            if j < i:
                FRONT += S[j]
            elif j >= i and j < i+LONG:
                MIDDLE += S[j]
            elif j >= i+LONG:
                BACK += S[j]
        if MIDDLE in FRONT or MIDDLE in BACK:
            ans = LONG
            
    if LONG != 0:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
n1 = int(input())
s1 = input()

r1 = 0
for i1 in range (n1):
    for i2 in range(((n1 - i1) // 2) - r1):
        t2 = r1 + i2
        if s1[i1:i1 + t2] in s1[i1 + t2:] and s1[i1:i1 + t2] != "":
            r1 += 1
            continue
        else:
            break
print(r1)

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-1), 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-1), 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:
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[i+j+k:i+k+k+j]
                if l == l2:
                    print(k)
                    exit()

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
flag = True
if n%2 == 0:
  for i in range(n//2):
    for j in range(n-2*(n//2-i)-1):
      if s[n//2-i+j:].count(s[j:n//2-i+j]) >=1:
        print(n//2-i+1)
        flag = False
        break
    else:
      continue
    break
else:
  for i in range(n//2):
    for j in range(n-2*(n//2-i)-1):
      if s[n//2-i+j:].count(s[j:n//2-i+j]) >=1:
        print(n//2-i+1)
        flag = False
        break
    else:
      continue
    break
if flag:
  print(0)

Submission status: Wrong Answer

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

ans = 0
for i in range(N):
    for j in range(1, N):
        if s[i:i+j] in s[i+j+1:]:
            tmp = j
            if tmp > ans:
                ans = tmp

print(ans)

Submission status: Wrong Answer

Solution code:
import math
import re

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

Cha = []

C = 0

for i in range(math.floor(N / 2)):
    Cha.append(S[:math.floor(N/2)+1-i])


for i,c  in zip(range(math.floor(N / 2),N),Cha):

    M = re.match(c,S[i])

    if M:
        C = len(c)
        break

    else:
        continue

print(C)

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)<=ans:
        break
    for j in range(i+1,i+(n-i)//2+3):
        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)

print(ans)

Submission status: Wrong Answer

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


def search(L, a, modulus, n, nums):
    """
    Rabin-Karp with polynomial rolling hash.
    Search a substring of given length
    that occurs at least 2 times.
    @return start position if the substring exits and -1 otherwise.
    """
    # compute the hash of string S[:L]
    h = 0
    for i in range(L):
        h = (h * a + nums[i]) % modulus
            
    # already seen hashes of strings of length L
    seen = {h} 
    # const value to be used often : a**L % modulus
    aL = pow(a, L, modulus) 
    for start in range(1, n - L + 1):
        # compute rolling hash in O(1) time
        h = (h * a - nums[start - 1] * aL + nums[start + L - 1]) % modulus
        if h in seen:
            return start
        seen.add(h)
    return -1

n = int(input())    
S = input().strip()

# convert string to array of integers
# to implement constant time slice
nums = [ord(S[i]) - ord('a') for i in range(n)]
# base value for the rolling hash function
a = 26
# modulus value for the rolling hash function to avoid overflow
modulus = 2**32

# binary search, L = repeating string length
left, right = 1, n
while left <= right:
    L = left + (right - left) // 2
    if search(L, a, modulus, n, nums) != -1:
        left = L + 1
    else:
        right = L - 1
        
start = search(left - 1, a, modulus, n, nums)
rep = S[start: start + left - 1]
rep2 = rep[::-1]
l = S.index(rep)
r = n - S[::-1].index(rep2) - 1
if r - l < 2 * len(rep):
        ans = (r - l + 1) // 2
else:
        ans = min(r - l, len(rep))
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:
from collections import defaultdict

def sort_bucket(s, bucket, order):
    d = defaultdict(list)
    for i in bucket:
        key = s[i + order // 2:i + order]
        d[key].append(i)
    result = []
    for k, v in sorted(d.items()):
        if len(v) > 1:
            result += sort_bucket(s, v, 2 * order)
        else:
            result.append(v[0])
    return result

def suffix_array_ManberMyers(s): 
    return sort_bucket(s, (i for i in range(len(s))), 1)
    
def lcp_array(s, sa):
    # http://codeforces.com/blog/entry/12796
    n = len(s)
    k = 0
    lcp = [0] * n
    rank = [0] * n
    for i in range(n):
        rank[sa[i]] = i
        
    for i in range(n):
        if rank[i] == n-1:
            k = 0
            continue
        j = sa[rank[i] + 1]
        while i + k < n and j + k < n and s[i + k] == s[j + k]:
            k += 1
        lcp[rank[i]] = k;
        if k:
            k -= 1
            
    return lcp
  
n = int(input())
s = input()
sa = suffix_array_ManberMyers(s)
e = lcp_array(s, sa)
print(min(max(e), len(s) // 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, 6):
        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:
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 + 9), solve(n, s, 999999883)))

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 copy
import sys

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

onaji = {}

max_len = 0

for i, s in enumerate(S):
    if s not in onaji:
        onaji[s] = []

    onaji[s].append(i)

for count in range(N // 2 + 2):
    # print(onaji)
    cp_onaji = copy.copy(onaji)
    for s in cp_onaji:
        if len(onaji[s]) <= 1:
            onaji.pop(s)

    if len(onaji) == 0:
        break

    next_onaji = {}
    for s in onaji:
        indice = onaji[s]
        for i in indice:
            if i+count + 1 > len(S):
                break

            moji = S[i:i+count+1]

            if moji not in next_onaji:
                next_onaji[moji] = []

            if len(next_onaji[moji]) == 0:
                next_onaji[moji].append(i)

            if next_onaji[moji][0] + count < i:
                next_onaji[moji].append(i)

    onaji = next_onaji

    max_len += 1

print(max(0, max_len-1))

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
S = input()
ans = 0
for i in reversed(range(math.ceil(N / 2))):
  for j in range(N):
    if (j + i) <= N and S.count(S[j:j+i]) >= 2:
      ans = i
      print(ans)
      exit()

print(ans)

Submission status: Wrong Answer

Solution code:
#coding:utf-8
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]


    MOD = 10**9+7
    N = II()
    S = input()

    hashes = [[0]* (N//2) for _ in range(N)]
    for i in range(N-1,-1,-1):
        hashes[i][0] = ord(S[i])
        for j in range(1,min(N//2,N-i)):
            hashes[i][j] = (hashes[i][j-1] * 26 + ord(S[i+j]))%MOD
    
    from collections import defaultdict

    for j in range(N//2-1,-1,-1):
        d = defaultdict(int)
        for i in range(N):

            if d[hashes[i][j]] != 0:
                i2,j2 = d[hashes[i][j]]
                if S[i:i+j] == S[i2:i2+j2]:
                    

                # TODO check

                    print(j+1)
                    return
            else:
                d[hashes[i][j]] = (i,j)




    print(0)


if __name__ == '__main__':
    main()

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), solve(n, s, 999999883)))

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
    f = s[0]
    c = 1
    for i in range(1, n):
        if s[i] == f:
            c += 1
        else:
            f = s[i]
            ans = max(ans, c//2)

    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())
t=input()
s=set()
a=-1
for i in range(n):
  for j in range(i+1,n+1):
    m=t[i:j]
    if m in s:a=max(a,j-i)
    else:s.add(t[i:j])
print(a)

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]]
        print(ad)
        for k, v in ad.items():
            td[s[k:k+ll-1]] += [[k, k+ll-1]]
        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:
N = int(input())
St = input()
ans = 0

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

#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] == St[j]:
      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+1])
print(ans)

Submission status: Wrong Answer

Solution code:
l = int(input())
str = input()


def analyze(s):
    max = 0
    d = {}
    for i in range(len(s)//2+3):
        for j in range(i, i+len(s)//2+3):
            if j > len(s):
                break
            p = s[i:j]
            if p in d:
                l = len(d[p])
                if l > max:
                    max = l
            d[p] = p
    return max


r = analyze(str)
print(r)

Submission status: Wrong Answer

Solution code:
n = int(input())

s = input()

index = list(range(n))
ans = 0

while True:
    target_char_index = index[0]
    target_char = s[target_char_index]
    index.remove(target_char_index)
    same_char_index = []
    for i in index:
        if s[i] == target_char:
            same_char_index.append(i)
            index.remove(i)
    # print('same_char_index', same_char_index, target_char)
    if len(same_char_index) >= 1:
        i = 1
        same_length = 1
        # same_char_index = index
        while True:
            # any(lambda x: s[i] == s[x + i], same_char_index)
            same_char_index = list(filter(lambda x: x + i <= n - 1 and x + i in index and s[target_char_index + i] == s[x + i], same_char_index))
            # print(list(same_char_index))
            if len(list(same_char_index)) == 0:
                break
            for v in same_char_index:
                index.remove(v + i)
            i += 1
            same_length += 1
            # print('target_char', target_char)
            # print('same_length', same_length)
            # print('index', index)
            # print('')

        ans = max(ans, same_length)
    if len(index) == 0:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
"""
N = int(input())
A, B = map(int,input().split())
A = list(map(int,input().split())) ## 横一列
A = [int(input()) for _ in range(N)] ## 縦一列
lst = [list(map(int,input().split())) for i in range(M)] ## 二次元
"""

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

N = int(5e3)
S = 'a' *N

ans = 0
for circ in range(1, N):
  cnt = 0
  solver = [0]
  for i in range(N-circ):
    if S[i] == S[i+circ]:
      cnt += 1
    else:
      solver.append(cnt)
      cnt = 0
  else:
    solver.append(cnt)
  ans = max(ans, min(circ, max(solver)))

print(ans)




"""
ans = 0
for i in range(N-1):
  if i+1+ans >= N:
    break
  lst = [0]
  for j in range(i+1+ans,N):
    cnt = 0
    if S[i] == S[j]:
      cnt += 1
      for k in range(1,min(j-i, N-j)):
        if S[i+k] == S[j+k]:
          cnt += 1
        else:
          break
    lst.append(cnt)
    #print(i, j, cnt)
  ans = max(ans, max(lst))
  
print(ans)
"""

Submission status: Wrong Answer

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

if N == 2:
  if text[0] == text[1]:
    print(1)
  else:
    print(0)
elif N == 1:
  print(0)
else:
  from collections import defaultdict
  sub_dict = defaultdict(set)
  for i in range(N-3):
    substring = text[i:i+2]
    for j in range(i+2, N-1):
      if text[j:j+2] == substring:
        sub_dict[substring]=(i, 2)

  max = 2
  #print(sub_dict)
  sub_dict_next = defaultdict(set)
  while True:
    flg = 0
    for i in sub_dict:
      wn, num = sub_dict[i]
      substring = text[wn:wn+num+1]
      for j in range(wn+num+1, N-num):
        if text[j:j+num+1] == substring:
          #print(substring, wn, num+1)
          sub_dict_next[substring] = (wn, num+1)
          flg = 1
          max=num+1
    if flg == 0:
      break
    else:
      sub_dict = sub_dict_next
      sub_dict_next = defaultdict(set)
  print(max)