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:
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(11):
    m = (l + r) // 2
    if can(m):
        l = m
    else:
        r = m
print(l)

Submission status: Wrong Answer

Solution code:
def solve():
    N = int(input())
    S = input()
    next_end = 1
    max_length = 0
    for start in range(N-1):
        for end in range(next_end, N):
            text = S[start:end]
            if text in S[end:]:
                max_length = len(text)
                continue
            else:
                if start + 1 == end:
                    next_end = end + 1
                else:
                    next_end = end
            break
    
    print(max_length)

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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

sa = [i for i in range(N+1)]
rank = [ord(c) for c in S] + [-1]

k = -1
key = lambda i: (rank[i], rank[i+k] if i+k <= N else -1)

def construct_sa():
    global k,rank
    k = 1
    tmp = [0] * (N+1)
    while k <= N:
        sa.sort(key=key)
        tmp[sa[0]] = 0
        for i in range(1,N+1):
            tmp[sa[i]] = tmp[sa[i-1]] + (key(sa[i-1]) < key(sa[i]))
        rank = [r for r in tmp]
        k *= 2

construct_sa()


def exist_twice(s):
    n = len(s)
    l,r = 0,N
    while r-l > 1:
        m = (l+r)//2
        if S[sa[m]:sa[m]+n] < s:
            l = m
        else:
            r = m
    return r+1 <= N and S[sa[r]:sa[r]+n] == S[sa[r+1]:sa[r+1]+n] == s

def is_ok(l):
    if l<=0: return True
    if l>=N: return False
    for i in range(N-l+1):
        if exist_twice(S[i:i+l]):
            return True
    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 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.8:
      print(2500)
      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:
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):
        tmp = (s[i:i+mid], mid)
        idx = bisect_left(suffix, tmp)
        flag = True
        while(flag):
            tgt = suffix[idx]
            # print(tgt)
            if tmp[0] == tgt[0]:
                if tgt[1] >= i + mid:
                    return True
                else:
                   idx += 1
            else:
                flag = False

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

suffix = []

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

suffix.sort()

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

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

Submission status: 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()

    for i in range(N//2,0,-1):
        for j in range(N-2*i):
            test = s[j:j+i]
            for k in range(j+i,N-i+1):
                if test == s[k:k+i]:
                    return i
    return 0

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

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(cnv[:l])
        for w in cnv[l:]:
            if w in appeared:
                return l
            appeared.add(w)

        vec = vec[1:]

    return 0


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

Submission status: Wrong Answer

Solution code:
n=int(input())
s=input()
now=0
now2=1
plus=0
answer=0
swit=0
while now<2:
    while now2<n:
        if swit==0:
            if s[now]==s[now2]:
                swit=1
                plus=1
            else:
                now2+=1
        if swit==1:
            if now2+plus<n:
                if s[now+plus]==s[now2+plus] and now+plus<now2:
                    plus+=1
                    if plus>=answer:
                        answer=plus
                else:
                    now2+=1
                    plus=0
            else:
                now2+=1
                plus=0
        if now2+answer>=n+1:
            break
    now+=1
    now2=now+max(answer-1, 1)
    if now+answer>=n+1:
        break
    #print(now, now2)
 
print(answer)

Submission status: Wrong Answer

Solution code:
n=int(input())
s=input()
import sys
for l in range(n//2,0,-1):
	t=[[s[i]+s[i+l-1],i] for i in range(n-l+1)]
	t.sort()
	last=t[0][0]
	lasti=t[0][1]
	for i in range(1,len(t)):
		if t[i][0]==last:
			if lasti+l<=t[i][1]:
				if s[lasti:lasti+l]==s[t[i][1]:t[i][1]+l]:
					print(l)
					sys.exit()
		else:
			last=t[i][0]
			lasti=t[i][1]
print(0)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
pm = 0
ans = 0
for i in range(N):
  for j in range(1,N):
    if S[i]!=S[j]:
      pm = 0
      continue
    x = i+pm
    y = j+pm
    while x<j and y<N and S[x]==S[y]:
      x += 1
      y += 1
      pm += 1
#    print(pm,i,j)
    if pm>ans:
      ans = pm
print(ans)

Submission status: Wrong Answer

Solution code:
def lrs(str):
    n = len(str)
    LCSRe = [[0 for x in range(n + 1)]
             for y in range(n + 1)]
    res = ""
    res_length = 0
    index = 0
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            if (str[i - 1] == str[j - 1] and
                    LCSRe[i - 1][j - 1] < (j - i)):
                LCSRe[i][j] = LCSRe[i - 1][j - 1] + 1

                if (LCSRe[i][j] > res_length):
                    res_length = LCSRe[i][j]
                    index = max(i, index)

            else:
                LCSRe[i][j] = 0


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

    return res


if __name__ == "__main__":
    a = int(input())
    s = input()

Submission status: Wrong Answer

Solution code:
n=int(input())
s=input()
now=0
now2=1
plus=0
answer=0
swit=0
while now<2:
    while now2<n:
        if swit==0:
            if s[now]==s[now2]:
                swit=1
                plus=1
            else:
                now2+=1
        if swit==1:
            if now2+plus<n:
                if s[now+plus]==s[now2+plus] and now+plus<now2:
                    plus+=1
                    if plus>=answer:
                        answer=plus
                else:
                    now2+=1
                    plus=0
            else:
                now2+=1
                plus=0
        if now2+answer>=n+1:
            break
    now+=1
    now2=now+answer
    if now+answer>=n+1:
        break
    #print(now, now2)
 
print(answer)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return sys.stdin.readline()[:-1]

def main():
    n = II()
    s = S()
    m = [[0 for i in range(n)] for i in range(n)]
    first = [[INF for i in range(n)] for i in range(n)]
    # set 1st index value
    lcs = 0
    for i, c in enumerate(s[1:]):
        if c == s[0]:
            m[i][0] = 1
            first[i][0] = i
            lcs = 1
    for i in range(1, n):
        for j in range(1, n):
            if i <= j:
                continue
            if s[i] == s[j]:
                if first[i-1][j-1] > j:
                    m[i][j] = m[i-1][j-1] + 1
                    if first[i-1][j-1] == INF:
                        first[i][j] = i
                    else:
                        first[i][j] = first[i-1][j-1]
                    lcs = max(m[i][j], lcs)
            else:
                m[i][j] = 0
    print(lcs)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n=int(input())
    s=input()
    m=0
    for i in range(1,n):
        cnt=0
        t=s[i:]
        for j in range(len(t)):
            if s[j]==t[j]:
                cnt=min(cnt+1,i)
            else:
                cnt=0
        m=max(cnt,m)
    print(m)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
S=input()
a=0
ans=0
while a<=n-2:
    x=S[a]
    maxcnt=0
    for j in range(a+1,n):
        if S[j]==x:
            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)
            maxcnt=max(maxcnt,cnt)
    a+=maxcnt+1
print(ans)

Submission status: Wrong Answer

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

ans = 0
for i in range(N-1):
    for j in range(1+ans, N-ans):
        for l in range(ans, min(j-i, N-j)):
            if S[i:i+l] == S[j:j+l]:
                ans = max(ans, l+1)
            else:
                break

print(ans)

Submission status: Wrong Answer

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


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

def main():
    left = 0
    right = N//2+1

    for _ in range(11):
        mid = left + (right-left)//2
        if not isok(mid):
            right = mid
        else:
            left = mid

    print(left)

if __name__ == "__main__":
    main()

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 = len(t)-1
    if l >= ans:
        for j in range(len(t)-1, -1, -1):
            r = j + i
            if s[j] == t[j] and l < r:
                count += 1
            else:
                break
        ans = max(count,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
MOD = 10000000000000061
def hsh(s):
    tot = 0
    pw = 1
    for c in s:
        tot = (tot*256 + ord(c))%MOD
        pw = (pw*256)%MOD
    return tot, pw

def ok(L, S):
    h, pw = hsh(S[:L])
    D = {}
    D[h] = 0
    for i in range(len(S) - L):
        h = ((h*256 - pw*ord(S[i])) + ord(S[i+L]))%MOD
        if h in D:
            if D[h] + L <= i: return True
        else:
            D[h] = i
    return False


raw_input()
S = raw_input()
lo = 0
hi = len(S)//2

while lo < hi:
    mid = (lo + hi + 1)//2
    ans = ok(mid, S)
    if ans:
        lo = mid
    else:
        hi = mid - 1
print(lo)

Submission status: Wrong Answer

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

ok, ng = 0, (n+1)//2
while ng-ok > 1:
	x = (ok+ng)//2
	possible = False
	for i in range(n-2*x+1):
		match = []
		for j in range(i+x, n):
			#print(x, i, j)
			new_match = []
			for m in match:
				if s[j] == s[i+m]:
					if m == x-1:
						possible = True
						break
					else:
						new_match.append(m+1)
			if s[j] == s[i]:
				if x == 1:
					possible = True
					break
				new_match.append(1)
			if possible:
				break
			match = new_match
			#print(x, match)
		if possible:
			break
	if possible:
		ok = x
	else:
		ng = x
print(ok)

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 = len(t)-1
    if l > ans:
        for j in range(len(t)-1, -1, -1):
            r = j + i
            if s[j] == t[j] and l < r:
                count += 1
            else:
                break
        ans = max(count,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
s=input()
l,r=n//2+1,0
while l-r>1:
    t=(l+r)//2
    p=s[:t]
    q=[p]
    for i in range(t,n):
        q.append(q[-1][1:]+s[i])
    if n-t+1>len(list(set(q))):
        r=t
    else:
        l=t
print(r)

Submission status: Wrong Answer

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

    for j in range(ml, 0, -1):
        d = collections.defaultdict(list)
        for i in range(n - j + 1):
            d[s[i:i+j]] += [[i, i+j]]
        for k, v in d.items():
            if len(v) > 1:
                print(len(k))
                exit()


if __name__ == '__main__':
    slove()

Submission status: Wrong Answer

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

dic=defaultdict(int)
for i in range(n-1):
    for j in range(i+1,n+1):
        dic[s[i:j]]+=1

ans=0
for key,value in dic.items():
    if value <2:
        continue
    if value >=2:
        if len(key) > ans:
            ans=len(key)
print(ans)

Submission status: Wrong Answer

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

sa = [i for i in range(N+1)]
rank = [ord(c) for c in S] + [-1]

k = -1
key = lambda i: (rank[i], rank[i+k] if i+k <= N else -1)

def construct_sa():
    global k,rank
    k = 1
    tmp = [0] * (N+1)
    while k <= N:
        sa.sort(key=key)
        tmp[sa[0]] = 0
        for i in range(1,N+1):
            tmp[sa[i]] = tmp[sa[i-1]] + (key(sa[i-1]) < key(sa[i]))
        rank = [r for r in tmp]
        k *= 2

construct_sa()

def exist_twice(s):
    n = len(s)
    if n*2 > N:
        return False
    l,r = 0,N
    while r-l > 1:
        m = (l+r)//2
        if S[sa[m]:sa[m]+n] < s:
            l = m
        else:
            r = m
    return r+1 <= N and S[sa[r]:sa[r]+n] == S[sa[r+1]:sa[r+1]+n] == s

for l in range(N//2, 0, -1):
    for i in range(N-l-1):
        if exist_twice(S[i:i+l]):
            print(l)
            exit()
print(0)

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]:
                print(j, k)
                return True
    return False


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

Submission status: Wrong Answer

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

L = []

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

L.sort()
ans = 0

for i in range(len(L)-1):
    temp = 0
    a = list(L[i][0])
    b = list(L[i+1][0])
    for j in range(min(len(a), len(b), abs(L[i][1] - L[i+1][1]))):
        if a[j] == b[j]:
            temp += 1
    ans = max(temp, ans)

print(ans)

Submission status: Wrong Answer

Solution code:
MOD = 18285670562881
def hsh(s):
    tot = 0
    pw = 1
    for c in s:
        tot = (tot*256 + ord(c))%MOD
        pw = (pw*256)%MOD
    return tot, pw

def ok(L, S):
    h, pw = hsh(S[:L])
    D = {}
    D[h] = 0
    for i in range(len(S) - L):
        h = ((h*256 - pw*ord(S[i])) + ord(S[i+L]))%MOD
        if h in D:
            if D[h] + L <= i: return True
        else:
            D[h] = i
    return False


raw_input()
S = raw_input()
lo = 0
hi = len(S)//2

while lo < hi:
    mid = (lo + hi + 1)//2
    ans = ok(mid, S)
    if ans:
        lo = mid
    else:
        hi = mid - 1
print(lo)

Submission status: Wrong Answer

Solution code:
n=int(input())
s=input()
l,r=n//2+1,0
while l-r>1:
    t=(l+r)//2
    p=s[:t]
    q=[p]
    for i in range(t+1,n):
        q.append(p[1:]+s[i])
    if n-t+1>=len(list(set(q))):
        r=t
    else:
        l=t
print(r)

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']
    dic = dict(zip(alp,[[] for _ in range(26)]))

    for i in range(LS):
        dic[S[i]].append(i)
    ans = 0
    for k in dic.keys():
        if len(dic[k]) >= 2:
            ans += len(dic[k])//2
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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


def solve(N: int, S: str):
    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)
    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:
# -*- coding: utf-8 -*-                                                         
tmp = input()
my_str = input()

start = 0
end = 1
max_len = 0

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

print(max_len)

Submission status: Wrong Answer

Solution code:
import re

input()
s = input()
#print(s)
m = re.findall(r'(.+).*?\1', s)
#print(m)
#print(m.groups())
print(len(max(m, key=len)) if m else 0)

Submission status: Wrong Answer

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

start = 0
end = 1
max_len = 0

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

print(max_len)

Submission status: Wrong Answer

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

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

A=[]
from collections import deque
NOW=deque(S)

LEN=len(S)
for i in range(LEN):

    A.append((list(NOW),i))
    NOW.popleft()

A.sort()
#print(A)

ANS=0
for i in range(1,len(A)):
    if A[i-1][0][:ANS]!=A[i][0][:ANS]:
        continue

    for j in range(ANS,min(len(A[i][0]),len(A[i-1][0]),abs(A[i-1][1]-A[i][1]))):
        if A[i-1][0][j]==A[i][0][j]:
            ANS+=1

print(ANS)

Submission status: Wrong Answer

Solution code:
from collections import Counter

def get_substrings(length, string):
    substrings = [''.join(string[i:i+length]) for i in range(len(string)-length+1)]
    return substrings

N = int(input())
S = input()
ans = 0
for i in range(N//2 + 1, 0, -1):
    substrings = Counter(get_substrings(i, S))
    if substrings.most_common(1)[0][1] >= 2:
        ans = i
        break
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
l, r = 0, n
while l + 1 != r:
    flg = 1
    m = (l + r) // 2
    cnt = 0
    for j in range(n - m * 2 + 1):
        for i in range(n - m - j):
            if s[i] == s[i + m + j]:
                cnt += 1
            else:
                cnt = 0
            if cnt >= m:
                break
        else:
            continue
        break
    else:
        flg = 0
    if flg:
        l = m
    else:
        r = m
print(l)

Submission status: Wrong Answer

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

start = 0
end = 1
max_len = 0

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

print(max_len)

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']
    dic = dict(zip(alp,[[] for _ in range(26)]))

    for i in range(LS):
        dic[S[i]].append(i)
    ans = 0
    for k in dic.keys():
        if len(dic[k]) >= 2:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
s=input()
now=0
now2=1
plus=0
nowp=0
nowa=0
answer=0
swit=0
while now<n:
    while now2<n:
        if swit==0:
            if s[now]==s[now2]:
                swit=1
                plus=1
                nowp=1
            else:
                now2+=1
        if swit==1:
            if now2+plus<n:
                if s[now+plus]==s[now2+plus] and now+plus<now2:
                    plus+=1
                    nowp+=1
                    if plus>=answer:
                        answer=plus
                    if nowp>=nowa:
                        nowa=nowp
                else:
                    now2+=1
                    plus=0
                    nowp=0
            else:
                now2+=1
                plus=0
                nowp=0
    now+=max(nowa,1)
    now2=now+1
    nowa=0
    nowp=0

print(answer)

Submission status: Wrong Answer

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

L = []

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

L.sort()
ans = 0

for i in range(len(L)-1):
    temp = 0
    a = L[i][0]
    b = L[i+1][0]
    for j in range(min(len(a), len(b), abs(L[i][1] - L[i+1][1]))):
        if a[j] == b[j]:
            temp += 1
    ans = max(temp, ans)

print(ans)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    s = input()
    if s == "Sunny":
        print("Cloudy")
    elif s == "Cloudy":
        print("Rainy")
    else:
        print("Sunny")
    return

#B
def B():
    s = S()
    for i in range(len(s)):
        if i%2:
            if s[i] not in ["L","U","D"]:
                print("No")
                return
        else:
            if s[i] not in ["R","U","D"]:
                print("No")
                return
    print("Yes")
    return

#C
def C():
    n,k,q = LI()
    a = IR(q)
    f = [k-q]*(n)
    for i in range(q):
        ai = a[i]-1
        f[ai] += 1
    for i in f:
        if i <= 0:
            print("No")
        else:
            print("Yes")
    return

#D
def D():
    n,m = LI()
    a = LI()
    q = []
    for i in range(n):
        heappush(q,-a[i])
    for i in range(m):
        x = heappop(q)
        x *= -1
        x >>= 1
        heappush(q,-x)
    print(-sum(q))
    return

#E
def E():
    n = I()
    s = S()
    l = 0
    r = n
    M = 10**64+1
    b = 26
    alp = list("abcdefghijklmnopqrstuvwxyz")
    f = {}
    for i in alp:
        f[i] = ord(i)-ord("a")
    pb = [pow(b,i,M) for i in range(n+1)]
    while r-l > 1:
        m = (l+r)>>1
        d = defaultdict(lambda : float("inf"))
        hash = 0
        for i in s[:m]:
            hash *= b
            hash += f[i]
            hash %= M
        d[hash] = 0
        t = pb[m]
        for i in range(n-m):
            si = s[i]
            hash *= b
            hash -= t*f[si]
            hash += f[s[i+m]]
            hash %= M
            if d[hash]+m <= i:
                l = m
                break
            if i < d[hash]:
                d[hash] = i
        else:
            r = m
    print(l)
    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    E()

Submission status: Wrong Answer

Solution code:
n=int(input())
s=input()
m=n//2
for i in range(n//2):
    for j in range(n-m):
        tmp1=s[j:j+m]
        for k in range(n-j-2*m+1):
            tmp2=s[j+m+k:j+m*2+k]
            if tmp1==tmp2:
                print(m)
                exit()
print(0)

Submission status: Wrong Answer

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

import numpy as np

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

MOD = 10**9 + 7
base = 1234

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

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

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

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

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

answer = left
print(answer)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    s = input()
    if s == "Sunny":
        print("Cloudy")
    elif s == "Cloudy":
        print("Rainy")
    else:
        print("Sunny")
    return

#B
def B():
    s = S()
    for i in range(len(s)):
        if i%2:
            if s[i] not in ["L","U","D"]:
                print("No")
                return
        else:
            if s[i] not in ["R","U","D"]:
                print("No")
                return
    print("Yes")
    return

#C
def C():
    n,k,q = LI()
    a = IR(q)
    f = [k-q]*(n)
    for i in range(q):
        ai = a[i]-1
        f[ai] += 1
    for i in f:
        if i <= 0:
            print("No")
        else:
            print("Yes")
    return

#D
def D():
    n,m = LI()
    a = LI()
    q = []
    for i in range(n):
        heappush(q,-a[i])
    for i in range(m):
        x = heappop(q)
        x *= -1
        x >>= 1
        heappush(q,-x)
    print(-sum(q))
    return

#E
def E():
    n = I()
    s = S()
    l = 0
    r = n
    M = 10**64+1
    b = 26
    alp = list("abcdefghijklmnopqrstuvwxyz")
    f = {}
    for i in alp:
        f[i] = ord(i)-ord("a")
    pb = [pow(b,i,mod) for i in range(n+1)]
    while r-l > 1:
        m = (l+r)>>1
        d = defaultdict(lambda : float("inf"))
        hash = 0
        for i in s[:m]:
            hash *= b
            hash += f[i]
            hash %= M
        d[hash] = 0
        t = pb[m]
        for i in range(n-m):
            si = s[i]
            hash *= b
            hash -= t*f[si]
            hash += f[s[i+m]]
            hash %= M
            if d[hash]+m <= i:
                l = m
                break
            if i < d[hash]:
                d[hash] = i
        else:
            r = m
    print(l)
    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    E()

Submission status: Wrong Answer

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

    for l in range(n // 2, 0, -1):
        t = 0
        exist = set()
        m = pow(d, l, MOD)
        for c in s[:l]:
            t = (t * d + c) % MOD
        exist.add(t)
        for c0, c1 in zip(s, s[l:]):
            t = (t * d - c0 * m + c1) % MOD
            exist.add(t)
        if len(exist) != n - l + 1:
            return l

    return 0


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