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:
import re

n = int(input())
s = input()
l = (n//2) 
flag=0
for i in range(l, 0, -1):
    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:
n=int(input())
s=input()
x=set()
ans=0
for i in range(n//2):
	x=set()
	for j in range(n-i):
		k=s[j:j+i+1]
		if k in x:
			ans=len(k)
			break
		else:
			x.add(k)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
l, r = 0, N-1


def can(m):
    for j in range(N - 2*m + 1):
        for k in range(j + m, N - m + 1):
            if S[j:j+m] == S[k:k+m]:
                return True
    return False


for i in range(13):
    m = (l + r - 1) // 2
    if can(m):
        l = m
    else:
        r = m
    if r-l <= 1:
        break
print(l)

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
        acc = []
        for c in sss[:l]:
            t = (t * d + c) % MOD
        acc.append(t)
        appeared = set()
        for i in range(l, n):
            c0, c1 = sss[i - l], sss[i]
            t = (t * d - c0 * m + c1) % MOD
            if t in appeared:
                return l
            appeared.add(acc[i - l])
            acc.append(t)

    return 0


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

Submission status: Wrong Answer

Solution code:
if __name__ == "__main__":
    N = int(input())
    S = input()

    for i in range(N//2, 0, -1):
        for index in range(N-i*2):
            # 仮の文字列の生成
            tmp = S[:index] + '0'*i + S[index+i:]
            if tmp.find(S[index:index+i]) != -1:
                print(i)
                exit()

    print('0')

Submission status: Wrong Answer

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

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

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

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

suffix = []

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

suffix.sort()

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

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

Submission status: 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] == 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])
print(ans)

Submission status: Wrong Answer

Solution code:
def getCharNGram(n,s):
    charGram = [''.join(s[i:i+n]) for i in range(len(s)-n+1)]
    return charGram
N = int(input())
S = input()
ans = 0
from collections import Counter
for i in range(N//2,0,-1):
    l = getCharNGram(i,S)
    am = Counter(l)
    a=am.most_common(1)
    if a[0][1]>1:
      ans = i
      print(ans)
      exit()
print(ans)

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-i):
        if S[i] == S[i+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 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())

    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()
m = -(-N//2)
Sh = S[:m]
res = 0
while m > 0:
    k = 0
    s = []
    while m+k <= len(Sh):
        s.append(Sh[k:m+k])
        k += 1
    for st in s:
        if S[m:].find(st) != -1:
            res = len(st)
            break
    if res != 0:
        break 
    m -= 1
print(res)

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 s[j] == t[j] and l < r:
                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 sys import exit, stderr, stdin
input = stdin.readline
# setrecursionlimit(10**7)
import heapq
def debug(var, name="hoge"):
    print(name +":" + str(type(var)) + " = " + repr(var), file=stderr)
    return


def main():
    N = int(input())
    S = str(input()).rstrip()
    LS = len(S)
    alp = ['a', 'b', 'c', 'd', 'e', 'f', 'g',
            'h', 'i', 'j', 'k', 'l', 'm', 'n',
             'o', 'p', 'q', 'r', 's', 't', 'u',
              'v', 'w', 'x', 'y', 'z']
    s = set()
    ans = 0
    for i in range(LS):
        for j in range(i+1,LS+1):
            subs = S[i:j]
            if subs in s:
                # print(subs)
                ans = max(ans,len(subs))
            else:
                s.add(subs)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

se = set(s)
if len(se) == 1:
    print(len(s)//2)
    exit()

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

suffix.sort(key=lambda x: x[0])

ans = 0
for i in range(n-1):
    s1 = suffix[i][0]
    idx1 = suffix[i][1]
    s2 = suffix[i+1][0]
    idx2 = suffix[i+1][1]

    count = 0
    for j in range(min(len(s1), len(s2))):
        if s1[j] != s2[j]:
            break
        if idx1 + j == idx2 or idx2 + j == idx1:
            break
        count += 1
    ans = max(ans, count)

print(ans)

Submission status: Wrong Answer

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

ans=0
for i in range(n-1):
  cnt=0
  s1=s[0:n-i-1]
  s2=s[i+1:n]
  for j in range(n-i-1):
    if s1[j]==s2[j]:
      cnt+=1
      ans=max(ans,cnt)
    else:
      cnt=0
print(ans)

Submission status: Wrong Answer

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

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())

    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()
ans = 0
for i in range(1,N):
  S1 = S[:i]
  S2 = S[i:]
  tmp = 0
  M = min(i,N-i)
  for j in range(M):
    if S1[j] == S2[j]:
      tmp += 1
    else:
      ans = max(ans,tmp)
      tmp = 0
      break
  for j in range(-1,-1-M,-1):
    if S1[j] == S2[j]:
      tmp += 1
    else:
      ans = max(ans, tmp)
      break
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
import queue
import re
import math
import functools

def s_raw():
    return input().rstrip("\r")

def int_raw():
    return int(input())


def ss_raw():
    return input().split()


def ints_raw():
    return list(map(int, ss_raw()))


INF = 1 << 29


def make1d_arr(n, val=INF):
    return [val for i in range(n)]


def make2d_arr(h, w, val=INF):
    return [[val for i in range(w)]for i in range(h)]


def gcd(a, b):
    if(b == 0):
        return a
    return gcd(b, a % b)


def BFord(n,es):
    v_cost = [INF]*n
    v_cost[0] = 0
    for v in range(n*2):
        for e in es:
            frm = e[0]
            to = e[1]
            if v_cost[to] > v_cost[frm]+e[2]:
                v_cost[to] = v_cost[frm]+e[2]
                if v >= n:
                    v_cost[to] = -INF
        if v == n-1:
            prev = v_cost[:]
    v_cost = [-INF if prev[idx]!=v_cost[idx] else v_cost[idx] for idx in range(n)]
    return v_cost
    

def main():
    n = int_raw()
    S = s_raw()
    setubi = []
    for idx in range(len(S)+1):
        setubi.append([S[idx:],idx])
    setubi.sort()
    max_lens = []
    for s_idx in range(1,len(setubi)):
        cur = setubi[s_idx]
        prev = setubi[s_idx-1]
        min_cp_len = min(len(prev[0]), len(cur[0]))
        is_b =False
        for c_idx in range(min_cp_len):
            if cur[0][c_idx]!=prev[0][c_idx]:
                max_lens.append(c_idx)
                is_b =True
                break
            if min(cur[1],prev[1])+c_idx>=max(cur[1],prev[1]):
                max_lens.append(c_idx)
                is_b = True
                break
        if not is_b:
            max_lens.append(min_cp_len)
    return max(max_lens)

    


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

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    s = input()
    slist = list(s)
    sset = set(slist)
    l = []
    lap = l.append
    if len(sset) == n:
        print(0)
    else:
        for i in list(sset):
            lap([j for j,k in enumerate(slist) if k == i])
        pair = []
        pap = pair.append
        for i in l:
            for j in range(len(i)):
                for k in range(j+1,len(i)):
                    pap((j,k))
        best = 1
        for i,j in pair:
            x = i
            y = j
            c = 0
            while True:
                if not s[x] == s[y] or x >= j:
                    break
                c += 1
                x += 1
                y += 1
            best = max([c,best])
        print(best)
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs , heapq as hq
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k][0] ==  x:
        return True
    else:
        return False

def search(a,n):
    se = dict()
    for i in range(0,len(a)-n+1):
        kkk = a[i:i+n]
        kkk = "".join(kkk)
        if kkk in se:
            for j in range(len(se[kkk])):
                if se[kkk][j] <= i+n:
                    return True
            else:
                se[kkk].append(i)
        else:
            se[kkk] = [i]
    return False








n = onem()

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

Submission status: Wrong Answer

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

dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
maxLength = 0


for i1 in range(1, n+1):
  for i2 in range(i1+1, n+1):
    if s[i1 - 1] == s[i2 - 1]:
      dp[i1][i2] = 1 + dp[i1 - 1][i2 - 1]
      maxLength = max(maxLength, dp[i1][i2])
print(maxLength)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())
S = input()
d = defaultdict(lambda:[0,0])

alp = set([s for s in S])

ans = 0
for s in alp:
    d = defaultdict(lambda:[0,0])
    i = 0
    while i<N:
        while i<N:
            if s == S[i]:
                break
            i += 1
        if i == N:
            break
        j = i
        d[s][0] += 1
        if d[s][0] >= 2:
            ans = max(ans,j-i+1)
        j += 1
        while j-i+1<=N-j-1:
            s = s+S[j]
            if d[s][1] < i:
                d[s][0] += 1
                d[s][1] = j
                ans = max(ans,j-i)
            j += 1
        i += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

s = input()

k = []

for i in range(n):
  k.append(s[n-i-1:])

list.sort(k)

ans = 0
for i in range(len(k)-1):
  if(k[i+1].count(k[i]) >= 2):
    ans = max(len(k[i]),ans)

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
p = 0
def check(l):
  global p
  for i in range(p, N-2*l):
    s = S[i:i+l]
    if not S.find(s, i+l) < 0:
      p = i
      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:
N = int(input())
S = input()

ans = 0
for i in range(1, N):
    length = min(i, N - i)
    same = [(S[i - length + j] == S[i + j]) for j in range(length)]

    tmp = 0
    for same_i in same:
        if same_i:
            tmp += 1
            if tmp > ans:
                ans = tmp
        else:
            tmp = 0
print(ans)

Submission status: Wrong Answer

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

max_count = 0
i = 0
while i < n:
    flg = False
    for j in range(n):
        if i >= j:
            continue
        if s[i] == s[j]:
            count = max_count
            while True:
                if i+count <= j and s[i:i+count] == s[j:j+count]:
                    #print(count, i, s[i:i+count])
                    count += 1
                    flg = True
                else:
                    max_count = max(max_count, count-1)
                    if flg:
                        i = i + count - 1
                    break
    if not flg:
        i += 1
        
print(max_count)

Submission status: Wrong Answer

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

ans = ''
len_ans = 0

alpha = 'abcdefghijklmnopqrstuvwxyz'
alpha = list(alpha)

l = []

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])

l.sort()
#print(l)

tmp = 1
ans = []

for i in range(len(l)-1):
    if l[i+1] - 1 == l[i]:
        tmp += 1
        #print(tmp)
    else:
        ans.append(tmp)
        tmp = 1
    
    if i == len(l)-2:
        ans.append(tmp)

ans.sort(reverse=True)

if len(ans) > 0:
    ans1 = ans[0]
else:
    ans1 = 0

ans2 = 0
for i in range(len(ans) - 1):
    if ans[i+1] == ans[i]:
        ans2 = ans[i]
        break

#print(ans1, ans1//2, ans2)
print(max(ans1//2, ans2))

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)
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):
    one = raw[i-1]
    two = raw[i]
    lone = len(one)
    ltwo = len(two)
    stop = min(lone,ltwo,abs(lone-ltwo))
    if ans > stop:
      pass
    else:
      for i in range(ans,stop):
        if one[i] == two[i]:
          ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs , heapq as hq
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k][0] ==  x:
        return True
    else:
        return False

def search(a,n):
    se = dict()
    for i in range(0,len(a)-n+1):
        kkk = a[i:i+n]
        kkk = "".join(kkk)
        if kkk in se:
            for j in range(len(se[kkk])):
                if se[kkk][j] < i+n:
                    return True
            else:
                se[kkk].append(i)
        else:
            se[kkk] = [i]
    return False








n = onem()

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

Submission status: Wrong Answer

Solution code:
def solve(str):

    n = len(str)
    cl = [[0 for x in range(n + 1)]
          for y in range(n + 1)]

    res = ""
    lres = 0

    ind = 0
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):

            if (str[i - 1] == str[j - 1] and
                    cl[i - 1][j - 1] < (j - i)):
                cl[i][j] = cl[i - 1][j - 1] + 1

                if (cl[i][j] > lres):
                    lres = cl[i][j]
                    ind = max(i, ind)

            else:
                cl[i][j] = 0

    if (lres > 0):
        for i in range(ind - lres + 1,
                       ind + 1):
            res = res + str[i - 1]

    return res


if __name__ == "__main__":

    str = input()
    print(len(solve(str)))

Submission status: Wrong Answer

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

def main():
    N = int(input())
    s = input().strip()

    p = [list() for i in range(26)]
    l = [1] * N
    check = [False] * N

    for i in range(N):
        p[ord(s[i]) - ord("a")].append(i)
    
    ans = 0
    for i in range(len(p)):
        for j in range(len(p[i])-1):
            for k in range(j+1, len(p[i])):
                ans = max(ans, 1)
                t = 1
                s1 = p[i][j]
                s2 = p[i][k]
                if s2 == N-1:
                    continue
                if check[s1+1] and check[s2+1]:
                    check[s1] = True
                    check[s2] = True
                    l[s1] = l[s1+1] + 1
                    l[s2] = l[s2+1] + 1
                    ans = max(ans, l[s2])
                    continue
                while True:
                    if s1 + t < s2 and s2 + t < N:
                        if s[s1+t] == s[s2+t]:
                            t += 1
                            # print(s[s1+t])
                            ans = max(ans, t)
                        else:
                            break
                        l[s1] = t
                        l[s2] = t
                    else:
                        break
                check[s1] = True
                check[s2] = True
    # print(l)
    # print(check)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import re

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

    res = re.search(r"(.+).*(\1)", s)
    print(len(res.groups()[0]) if res else 0)

main()

Submission status: Wrong Answer

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

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

suffix.sort(key=lambda x: x[0])

ans = 0
for i in range(n-1):
    s1 = suffix[i][0]
    idx1 = suffix[i][1]
    s2 = suffix[i+1][0]
    idx2 = suffix[i+1][1]

    count = 0
    for j in range(min(len(s1), len(s2))):
        if s1[j] != s2[j]:
            break
        if idx1 + j == idx2 or idx2 + j == idx1:
            break
        count += 1
    ans = max(ans, count)

print(ans)

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)
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):
    one = raw[i-1]
    two = raw[i]
    lone = len(one)
    ltwo = len(two)
    stop = min(lone,ltwo,abs(lone-ltwo))
    if ans > stop:
      pass
    else:
      for i in range(ans,stop):
        if one[i] == two[i]:
          ans += 1
print(ans)

Submission status: Wrong Answer

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

    l = 0
    m = 0
    while l < N:                # 10^3
        k = 0
        r = l+1
        while r+k < N:
            #print(S[l], S[r], k, m)
            if S[l+k] == S[r+k]:
                #print("[1]", (l+k, r), "\tS[%d]=%c S[%d]=%c, N=%d"%(l+k, S[l+k], r+k, S[r+k], N), k, m)
                k += 1
                if l+k <= r:
                    m = max(k, m)
                else:
                    break
            elif k == 0:
                r+=1
            else:
                #print("[3]", S[l], S[r], k, m)
                m = max(k, m)
                break
        l = l + 1
    print(m)

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

Submission status: Wrong Answer

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

h = {}
res = 0
for i in range(len(S)):
  for j in range(i+1, len(S)):
    if j - i + 1 <= res:
      continue
    s = S[i:j+1]
    if s in h:
      res = j - i + 1
    else:
      h[s] = 1

print(res)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)


def solve(N: int, S: str):
    max_con = 1
    tmp = 1
    for i in range(N - 1):
        if S[i] == S[i + 1]:
            tmp += 1
        else:
            max_con = max(max_con, tmp)
            tmp = 1
    max_con = max(max_con, tmp)


    sa = []
    for i in range(N):
        sa.append([S[i:], i])
    sa.sort()
    ret = 0
    for i in range(N - 1):
        s, si = sa[i]
        t, ti = sa[i + 1]
        mx = min(len(s), len(t), abs(si - ti))
        #print(s, t, si, ti, mx)
        j = 0
        while j < mx and s[j] == t[j]:
            j += 1
        ret = max(ret, j)
    ret = max(ret, max_con // 2)
    print(ret)
    return


def solve_(N: int, S: str):
    sa = []
    for i in range(N):
        sa.append([S[i:], i])
    sa.sort()
    #print(sa)
    ret = 0
    for i in range(N - 1):
        s, si = sa[i]
        if len(s) < ret:
            continue
        tmp = 0
        for k in range(i + 1, N):
            t, ti = sa[k]
            mx = min(len(s), len(t), abs(si - ti))
            #print(s, t, si, ti, mx)
            j = 0
            while j < mx and s[j] == t[j]:
                j += 1
            if j < tmp:
                break
            tmp = j
        ret = max(ret, tmp)
    print(ret)
    return


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()
l, r = 1, N-1


def can(m):
    for j in range(N - 2*m + 1):
        for k in range(j + m, N - m + 1):
            if S[j:j+m] == S[k:k+m]:
                return True
    return False


for i in range(12):
    m = (l + r + 1) // 2
    if can(m):
        l = m
    else:
        r = m
    if r - l <= 1:
        break
print(l)

Submission status: Wrong Answer

Solution code:
import numpy as np


def solve(n, s, MOD):
    d = 26
    s = np.array([ord(c) - 97 for c in s], dtype=np.int64)
    max_l = n // 2

    vec = [1]
    for i in range(max_l - 1):
        vec.append(vec[-1] * d % MOD)
    vec.reverse()
    vec = np.array(vec, dtype=np.int64)

    for l in range(max_l, 0, -1):
        cnv = np.convolve(s, vec, 'valid') % MOD
        appeared = set()
        for i, w in enumerate(cnv[l:], start=l):
            if w in appeared:
                return l
            appeared.add(cnv[i - l])

        vec = vec[1:]

    return 0


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

Submission status: Wrong Answer

Solution code:
import re

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

ma = re.search(r'(.+).*\1',S)

if ma:
    print(len(ma.group(1)))
else:
    print(0)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())
S = input()
def match(n):
  D = defaultdict(list)
  for i in range(N + 1 - n):
    D[S[i:i + n]].append(i)
  for L in D.values():
    if len(L) > 1 and L[-1] - L[0] >= 2:
      return True
  return False
def bs(upper, lower):
  if upper - lower == 1:
    return lower
  mid = (upper + lower) // 2
  if match(mid):
    return bs(upper, mid)
  else:
    return bs(mid, lower)
print(N // 2 if match(N // 2) else bs(N // 2, 0))

Submission status: Wrong Answer

Solution code:
n=int(input())
s=input()
x=set()
ans=0
for i in range(1,n//2+1):
	x=set()
	for j in range(n-i):
		k=s[j:j+i+1]
		if k in x:
			ans=len(k)
			break
		else:
			x.add(k)
print(ans)

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 substringDp(s):
    L = len(s)
    dp = [0 for i in range(L + 1)]

    nex = [[26 for j in range(27)] for i in range(L + 1)]
    for i in range(L - 1, -1, -1):
        for j in range(26):
            nex[i][j] = nex[i + 1][j]
        nex[i][ord(s[i]) - ord("a")] = i

    dp[0] = 1
    for i in range(L):
        for j in range(26):
            if nex[i][j] >= L:
                continue
            dp[nex[i][j] + 1] += dp[i]
            dp[nex[i][j] + 1] %= MOD
    print(nex)
    ret = 0
    for i in range(L + 1):
        ret += dp[i]
        ret %= MOD

    print(ret)


def main():
    n = int(input())
    s = list(input())
    dp = [[0 for i in range(n)] for j in range(n)]

    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
            ans = max(ans, k)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import time
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return sys.stdin.readline().rstrip()
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()

def main():
  start = time.time()
  n = I()
  s = S()
  ok = 0
  ng = n//2+2
  while ok+1 < ng:
    if time.time()-start > 1.7:
      print(1)
      exit()
    flag = False
    mid = (ok+ng)//2
    for j in range(n-mid):
      if s[j+mid:].find(s[j:j+mid]) != -1:
        flag = True
        break
    if flag:
      ok = mid
    else:
      ng = mid
  print(ok)

if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd

def check(L):
    strings = {}
    for i in range(N - L):
        s= S[i:i+L+1]
        if s in strings:
            start, end = strings[s]
            #print('exists', s)
            if i > end:
                #print('True')
                return True
        strings[s] = i, i + L
    
    #print('False')
    return False


N = int(raw_input())
S= raw_input()
lo = 0
hi = N/2 + 1
for i in range(13):
    mid= (lo +hi)//2
    has_two = check(mid)
    #print('checking ', mid)
    if has_two:
        lo = mid
    else:
        hi = mid
print(hi)