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 = list(map(str, input().strip()))
seed = 13331
mod = 10 ** 9 + 7
lsd = [1] * 6000
hs = [1] * 6000
hs[0] = ord(s[0]) - ord('a')
for i in range(1, n):
    lsd[i] = lsd[i - 1] * seed % mod
    hs[i] = (hs[i - 1] * seed + ord(s[i]) - ord('a')) % mod


def check(x):
    from collections import defaultdict
    g = defaultdict(int)
    for i in range(n - x + 1):
        if i:
            t = (hs[i + x - 1] - hs[i - 1] * lsd[x]) % mod
        else:
            t = hs[i + x - 1]
        # print(i,t)
        if not g[t]:
            g[t] = i+1
        elif g[t] + x - 1 <= i:
            return True
    return False



l = 0
r = n
while l < r - 1:
    m = (l + r) // 2
    if check(m):
        l = m
    else:
        r = m - 1

if check(r):
    print(r)
else:
    print(l)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = list(map(str, input().strip()))
seed = 13131
mod = 10 ** 9 + 7
lsd = [1] * 6000
hs = [1] * 6000
hs[0] = ord(s[0]) - ord('a')
for i in range(1, n):
    lsd[i] = lsd[i - 1] * seed % mod
    hs[i] = (hs[i - 1] * seed + ord(s[i]) - ord('a')) % mod


def check(x):
    from collections import defaultdict
    g = defaultdict(int)
    for i in range(n - x + 1):
        if i:
            t = (hs[i + x - 1] - hs[i - 1] * lsd[x]) % mod
        else:
            t = hs[i + x - 1]
        # print(i,t)
        if not g[t]:
            g[t] = i+1
        elif g[t] + x - 1 <= i:
            return True
    return False



l = 0
r = n
while l < r - 1:
    m = (l + r) // 2
    if check(m):
        l = m
    else:
        r = m - 1

if check(r):
    print(r)
else:
    print(l)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from itertools import *
INF = 10**10

CHRtoINT = defaultdict(int)
atoz = [chr(i) for i in range(97,97+26)]
for i, c in enumerate(atoz):
    CHRtoINT[c] = i

N, S = int(input()), input()
b=26
m=10**9+7
l, r = 0, N//2+1
while l+1 < r:
    x = (l+r)//2
    OK = 0
    dic = defaultdict(int)
    B, hash, b_inv = pow(b, x-1, m), 0, pow(b, m-2, m)
    t = B
    for c in S[:x]:
        hash = (hash + CHRtoINT[c] * t) % m
        t = t * b_inv % m
    dic[hash] = 0
    B *= b
    for i, c in enumerate(S[:-x]):
        hash = (hash * b - CHRtoINT[c] * B + CHRtoINT[S[i+x]]) % m
        if hash in dic:
            if i+1-dic[hash] >= x:
                OK = 1
                break
        else:
            dic[hash] = i+1
    if OK:
        l = x
    else:
        r = x
print(l)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from itertools import *
INF = 10**10

CHRtoINT = defaultdict(int)
atoz = [chr(i) for i in range(97,97+26)]
for i, c in enumerate(atoz):
    CHRtoINT[c] = i

N, S = int(input()), input()
b=26
m=67280421310721
l, r = 0, N//2+1
while l+1 < r:
    x = (l+r)//2
    OK = 0
    dic = defaultdict(int)
    B, hash = pow(b, x-1, m), 0
    t = B
    for c in S[:x]:
        hash = (hash + CHRtoINT[c] * t) % m
        t //= b
    dic[hash] = 0
    B *= b
    for i, c in enumerate(S[:-x]):
        hash = (hash * b - CHRtoINT[c] * B + CHRtoINT[S[i+x]]) % m
        if hash in dic:
            if i+1-dic[hash] >= x:
                OK = 1
                break
        else:
            dic[hash] = i+1
    if OK:
        l = x
    else:
        r = x
print(l)

Submission status: Wrong Answer

Solution code:

base = 10007
mod1 = int(1e9 + 7)
mod2 = int(1e9 + 9)


class RollingHash:
    def __init__(self, str):
        self.s = str
        self.len = len(str)
        self.mod1_table = [pow(base, i, mod1) for i in range(self.len + 2)]
        self.mod2_table = [pow(base, i, mod2) for i in range(self.len + 2)]
        self.inv1_table = [pow(self.mod1_table[i], mod1 - 2, mod1) for i in range(self.len + 2)]
        self.inv2_table = [pow(self.mod2_table[i], mod2 - 2, mod2) for i in range(self.len + 2)]
        self.elm = [0]
        for i in range(self.len):
            pass

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def z_alg(S):
    N = len(S)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A

n = int(input())
s = input()
ans = 0
for i in range(n):
    data = z_alg(s[i:])
    for x in data[1:]:
        ans = max(ans,x-max(0,2*x-n))

print(ans)

Submission status: Wrong Answer

Solution code:
def z_alg(S):
    N = len(S)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A

n = int(input())
s = input()
ans = 0
for i in range(n):
    data = z_alg(s[i:])
    for j,x in enumerate(data[1:]):
        ans = max(ans,x-max(0,2*x-n))

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
m = 0
for i in range(N//2):
        for r in range(i+1,(N-i)//2):
                if S[i:r] in (S[r:N]):
                        m = max(m,len(S[i:r]))               
print(m)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = list(map(str, input().strip()))
seed = 133331
mod = 10 ** 9 + 7
lsd = [1] * 6000
hs = [1] * 6000
hs[0] = ord(s[0]) - ord('a')
for i in range(1, n):
    lsd[i] = lsd[i - 1] * seed % mod
    hs[i] = (hs[i - 1] * seed + ord(s[i]) - ord('a')) % mod


def check(x):
    from collections import defaultdict
    g = defaultdict(int)
    for i in range(n - x + 1):
        if i:
            t = (hs[i + x - 1] - hs[i - 1] * lsd[x]) % mod
        else:
            t = hs[i + x - 1]
        # print(i,t)
        if not g[t]:
            g[t] = i+1
        elif g[t] + x - 1 <= i:
            return True
    return False



l = 0
r = n
while l < r - 1:
    m = (l + r) // 2
    if check(m):
        l = m
    else:
        r = m - 1

if check(r):
    print(r)
else:
    print(l)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = list(map(str, input().strip()))
seed = 13331
mod = 10 ** 9 + 7

lsd = [1] * 6000
hs = [1] * 6000
hs[0] = ord(s[0]) - ord('a')
for i in range(1, n):
    lsd[i] = lsd[i - 1] * seed % mod
    hs[i] = (hs[i - 1] * seed + ord(s[i]) - ord('a')) % mod


def check(x):
    from collections import defaultdict
    g = defaultdict(int)
    for i in range(n - x + 1):
        if i:
            t = (hs[i + x - 1] - hs[i - 1] * lsd[x]) % mod
        else:
            t = hs[i + x - 1]
        # print(i,t)
        if not g[t]:
            g[t] = i+1
        elif g[t] + x - 1 <= i:
            return True
    return False



l = 0
r = n
while l < r - 1:
    m = (l + r) // 2
    if check(m):
        l = m
    else:
        r = m - 1

if check(r):
    print(r)
else:
    print(l)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = list(map(str, input().strip()))
seed = 13331
mod = 10 ** 9 + 7

lsd = [1] * 6000
hs = [1] * 6000
hs[0] = ord(s[0]) - ord('a')
for i in range(1, n):
    lsd[i] = lsd[i - 1] * seed % mod
    hs[i] = (hs[i - 1] * seed + ord(s[i]) - ord('a')) % mod


def check(x):
    from collections import defaultdict
    g = defaultdict(int)
    for i in range(n - x + 1):
        if i:
            t = (hs[i + x - 1] - hs[i - 1] * lsd[x]) % mod
        else:
            t = hs[i + x - 1]
        if not g[t]:
            g[t] = i
        elif g[t] + x - 1 < i:
            return True
    return False


l = 0
r = n
while l < r - 1:
    m = (l + r) // 2
    # print(m)
    if m == 0:
        m = 1
    if check(m):
        l = m
    else:
        r = m - 1

if (check(r)):
    print(r)
else:
    print(l)

Submission status: Wrong Answer

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

def search(n):
    if n == 0:
        return False
    for i in range(N):
        for j in range(i+n, N):
            if j+n <= N:
                if S[i:i+n] == S[j:j+n]:
                    return True
    return False

l = 1
r = N//2+1

while l<r:
    mid = (l+r)//2
    print(l,r)
    if search(mid):
        l = mid+1
    else:
        r = mid

print(l-1)

Submission status: Wrong Answer

Solution code:
from functools import cmp_to_key

n = int(input())
s = input()
k = 1
rank = [0] * (n+1)
tmp = [0] * (n+1)
sa = [''] * (n+1)

def compare_sa(i,j):
	if rank[i] != rank[j]:
		return -1 if rank[i] < rank[j] else 1
	else:
		if i + k <= n:
			ri = rank[i+k]
		else:
			ri = -1
		if j + k <= n:
			rj = rank[j+k]
		else:
			rj = -1
		return -1 if ri < rj else 1


for i in range(n+1):
	sa[i] = i
	if i < n:
		rank[i] = ord(s[i])
	else:
		rank[i] = -1

while k <= n:

	sa = sorted(sa,key=cmp_to_key(compare_sa))

	tmp[sa[0]] = 0

	for i in range(1,n+1):
		if compare_sa(sa[i-1],sa[i]) == -1:
			tmp[sa[i]] = tmp[sa[i-1]] + 1
		else:
			tmp[sa[i]] = tmp[sa[i-1]]

	for i in range(n+1):
		rank[i] = tmp[i]

	k *= 2

#saはインデックス、sorted_listは実際の文字列
sorted_list = []
for i in range(n+1):
	sorted_list.append(s[sa[i]:])
#print(sa)
#print(sorted_list)

"""
#文字列検索
T = ['ab','abra','abc','abracadabra','abracadabraaa','brabra','bra']
for t in T:
	start = bisect.bisect_left(sorted_list,t)
	end = bisect.bisect_left(sorted_list,t[:-1]+chr(ord(t[-1])+1))
	if start == end:
		print(t+'は存在しません')
	else:
		print(t+'は存在します')

#lcp配列の作成
def getLCP(i,j):
	h = 0
	while i+h < n and j+h < n:
		if s[j+h] != s[i+h]:
			break
		h+=1
	return h

#lcp配列の最大値=最長の共通部分文字列のインデックス
#ans = sorted_list[ lcp.index(max(lcp)) ]
#ans = ans[:max(lcp)]
#print(ans)

ans = 0
for i in range(0,n):
	for j in range(i+1,n):
		lcp = min(getLCP(i,j),j-i)
		ans = max(ans,lcp)

print(ans)
"""

#lcp配列の作成
lcp = []
for i in range(1,n+1):
	h = 0
	while sa[i]+h < n and sa[i-1]+h < n:
		if s[sa[i-1]+h] != s[sa[i]+h]:
			break
		h+=1
			
	lcp.append(min(h,sa[i],sa[i-1]))

#print(lcp)
#lcp配列の最大値=最長の共通部分文字列のインデックス
ans = max(lcp)
print(ans)

Submission status: Wrong Answer

Solution code:
from functools import cmp_to_key

n = int(input())
s = input()
k = 1
rank = [0] * (n+1)
tmp = [0] * (n+1)
sa = [''] * (n+1)

def compare_sa(i,j):
	if rank[i] != rank[j]:
		return -1 if rank[i] < rank[j] else 1
	else:
		if i + k <= n:
			ri = rank[i+k]
		else:
			ri = -1
		if j + k <= n:
			rj = rank[j+k]
		else:
			rj = -1
		return -1 if ri < rj else 1


for i in range(n+1):
	sa[i] = i
	if i < n:
		rank[i] = ord(s[i])
	else:
		rank[i] = -1

while k <= n:

	sa = sorted(sa,key=cmp_to_key(compare_sa))

	tmp[sa[0]] = 0

	for i in range(1,n+1):
		if compare_sa(sa[i-1],sa[i]) == -1:
			tmp[sa[i]] = tmp[sa[i-1]] + 1
		else:
			tmp[sa[i]] = tmp[sa[i-1]]

	for i in range(n+1):
		rank[i] = tmp[i]

	k *= 2

#saはインデックス、sorted_listは実際の文字列
sorted_list = []
for i in range(n+1):
	sorted_list.append(s[sa[i]:])
print(sa)
print(sorted_list)

"""
#文字列検索
T = ['ab','abra','abc','abracadabra','abracadabraaa','brabra','bra']
for t in T:
	start = bisect.bisect_left(sorted_list,t)
	end = bisect.bisect_left(sorted_list,t[:-1]+chr(ord(t[-1])+1))
	if start == end:
		print(t+'は存在しません')
	else:
		print(t+'は存在します')

#lcp配列の作成
def getLCP(i,j):
	h = 0
	while i+h < n and j+h < n:
		if s[j+h] != s[i+h]:
			break
		h+=1
	return h

#lcp配列の最大値=最長の共通部分文字列のインデックス
#ans = sorted_list[ lcp.index(max(lcp)) ]
#ans = ans[:max(lcp)]
#print(ans)

ans = 0
for i in range(0,n):
	for j in range(i+1,n):
		lcp = min(getLCP(i,j),j-i)
		ans = max(ans,lcp)

print(ans)
"""

#lcp配列の作成
lcp = []
for i in range(1,n+1):
	h = 0
	while sa[i]+h < n and sa[i-1]+h < n:
		if s[sa[i-1]+h] != s[sa[i]+h]:
			break
		h+=1
			
	lcp.append(min(h,sa[i],sa[i-1]))

print(lcp)
#lcp配列の最大値=最長の共通部分文字列のインデックス
ans = max(lcp)
print(ans)

Submission status: Wrong Answer

Solution code:
from functools import cmp_to_key

n = int(input())
s = input()
k = 1
rank = [0] * (n+1)
tmp = [0] * (n+1)
sa = [''] * (n+1)

def compare_sa(i,j):
	if rank[i] != rank[j]:
		return -1 if rank[i] < rank[j] else 1
	else:
		if i + k <= n:
			ri = rank[i+k]
		else:
			ri = -1
		if j + k <= n:
			rj = rank[j+k]
		else:
			rj = -1
		return -1 if ri < rj else 1


for i in range(n+1):
	sa[i] = i
	if i < n:
		rank[i] = ord(s[i])
	else:
		rank[i] = -1

while k <= n:

	sa = sorted(sa,key=cmp_to_key(compare_sa))

	tmp[sa[0]] = 0

	for i in range(1,n+1):
		if compare_sa(sa[i-1],sa[i]) == -1:
			tmp[sa[i]] = tmp[sa[i-1]] + 1
		else:
			tmp[sa[i]] = tmp[sa[i-1]]

	for i in range(n+1):
		rank[i] = tmp[i]

	k *= 2

#saはインデックス、sorted_listは実際の文字列
sorted_list = []
for i in range(n+1):
	sorted_list.append(s[sa[i]:])
#print(sa)
#print(sorted_list)

"""
#文字列検索
T = ['ab','abra','abc','abracadabra','abracadabraaa','brabra','bra']
for t in T:
	start = bisect.bisect_left(sorted_list,t)
	end = bisect.bisect_left(sorted_list,t[:-1]+chr(ord(t[-1])+1))
	if start == end:
		print(t+'は存在しません')
	else:
		print(t+'は存在します')

#lcp配列の作成
def getLCP(i,j):
	h = 0
	while i+h < n and j+h < n:
		if s[j+h] != s[i+h]:
			break
		h+=1
	return h

#lcp配列の最大値=最長の共通部分文字列のインデックス
#ans = sorted_list[ lcp.index(max(lcp)) ]
#ans = ans[:max(lcp)]
#print(ans)

ans = 0
for i in range(0,n):
	for j in range(i+1,n):
		lcp = min(getLCP(i,j),j-i)
		ans = max(ans,lcp)

print(ans)
"""

#lcp配列の作成
lcp = []
for i in range(1,n+1):
	h = 0
	while sa[i]+h < n and sa[i-1]+h < n:
		if s[sa[i-1]+h] != s[sa[i]+h]:
			break
		h+=1
	if h >= n//2:
		h = h//2 -1
			
	lcp.append(h)

#print(lcp)
#lcp配列の最大値=最長の共通部分文字列のインデックス
ans = max(lcp)
print(ans)

Submission status: Wrong Answer

Solution code:
from functools import cmp_to_key

n = int(input())
s = input()
k = 1
rank = [0] * (n+1)
tmp = [0] * (n+1)
sa = [''] * (n+1)

def compare_sa(i,j):
	if rank[i] != rank[j]:
		return -1 if rank[i] < rank[j] else 1
	else:
		if i + k <= n:
			ri = rank[i+k]
		else:
			ri = -1
		if j + k <= n:
			rj = rank[j+k]
		else:
			rj = -1
		return -1 if ri < rj else 1


for i in range(n+1):
	sa[i] = i
	if i < n:
		rank[i] = ord(s[i])
	else:
		rank[i] = -1

while k <= n:

	sa = sorted(sa,key=cmp_to_key(compare_sa))

	tmp[sa[0]] = 0

	for i in range(1,n+1):
		if compare_sa(sa[i-1],sa[i]) == -1:
			tmp[sa[i]] = tmp[sa[i-1]] + 1
		else:
			tmp[sa[i]] = tmp[sa[i-1]]

	for i in range(n+1):
		rank[i] = tmp[i]

	k *= 2

#saはインデックス、sorted_listは実際の文字列
sorted_list = []
for i in range(n+1):
	sorted_list.append(s[sa[i]:])
#print(sa)
#print(sorted_list)

"""
#文字列検索
T = ['ab','abra','abc','abracadabra','abracadabraaa','brabra','bra']
for t in T:
	start = bisect.bisect_left(sorted_list,t)
	end = bisect.bisect_left(sorted_list,t[:-1]+chr(ord(t[-1])+1))
	if start == end:
		print(t+'は存在しません')
	else:
		print(t+'は存在します')

#lcp配列の作成
def getLCP(i,j):
	h = 0
	while i+h < n and j+h < n:
		if s[j+h] != s[i+h]:
			break
		h+=1
	return h

#lcp配列の最大値=最長の共通部分文字列のインデックス
#ans = sorted_list[ lcp.index(max(lcp)) ]
#ans = ans[:max(lcp)]
#print(ans)

ans = 0
for i in range(0,n):
	for j in range(i+1,n):
		lcp = min(getLCP(i,j),j-i)
		ans = max(ans,lcp)

print(ans)
"""

#lcp配列の作成
lcp = []
for i in range(1,n+1):
	h = 0
	while sa[i]+h < n and sa[i-1]+h < n:
		if s[sa[i-1]+h] != s[sa[i]+h]:
			break
		h+=1
	if h > n/2:
		h = 0
			
	lcp.append(h)

#print(lcp)
#lcp配列の最大値=最長の共通部分文字列のインデックス
ans = max(lcp)
print(ans)

Submission status: Wrong Answer

Solution code:
from functools import cmp_to_key

n = int(input())
s = input()
k = 1
rank = [0] * (n+1)
tmp = [0] * (n+1)
sa = [''] * (n+1)

def compare_sa(i,j):
	if rank[i] != rank[j]:
		return -1 if rank[i] < rank[j] else 1
	else:
		if i + k <= n:
			ri = rank[i+k]
		else:
			ri = -1
		if j + k <= n:
			rj = rank[j+k]
		else:
			rj = -1
		return -1 if ri < rj else 1


for i in range(n+1):
	sa[i] = i
	if i < n:
		rank[i] = ord(s[i])
	else:
		rank[i] = -1

while k <= n:

	sa = sorted(sa,key=cmp_to_key(compare_sa))

	tmp[sa[0]] = 0

	for i in range(1,n+1):
		if compare_sa(sa[i-1],sa[i]) == -1:
			tmp[sa[i]] = tmp[sa[i-1]] + 1
		else:
			tmp[sa[i]] = tmp[sa[i-1]]

	for i in range(n+1):
		rank[i] = tmp[i]

	k *= 2

#saはインデックス、sorted_listは実際の文字列
sorted_list = []
for i in range(n+1):
	sorted_list.append(s[sa[i]:])
#print(sa)
#print(sorted_list)

"""
#文字列検索
T = ['ab','abra','abc','abracadabra','abracadabraaa','brabra','bra']
for t in T:
	start = bisect.bisect_left(sorted_list,t)
	end = bisect.bisect_left(sorted_list,t[:-1]+chr(ord(t[-1])+1))
	if start == end:
		print(t+'は存在しません')
	else:
		print(t+'は存在します')

#lcp配列の作成
def getLCP(i,j):
	h = 0
	while i+h < n and j+h < n:
		if s[j+h] != s[i+h]:
			break
		h+=1
	return h

#lcp配列の最大値=最長の共通部分文字列のインデックス
#ans = sorted_list[ lcp.index(max(lcp)) ]
#ans = ans[:max(lcp)]
#print(ans)

ans = 0
for i in range(0,n):
	for j in range(i+1,n):
		lcp = min(getLCP(i,j),j-i)
		ans = max(ans,lcp)

print(ans)
"""

#lcp配列の作成
lcp = []
for i in range(1,n+1):
	h = 0
	while sa[i]+h < n and sa[i-1]+h < n:
		if s[sa[i-1]+h] != s[sa[i]+h]:
			break
		h+=1
	if h > n/2:
		h = 0
			
	lcp.append(h)

print(lcp)
#lcp配列の最大値=最長の共通部分文字列のインデックス
ans = max(lcp)
print(ans)

Submission status: Wrong Answer

Solution code:
from functools import cmp_to_key

n = int(input())
s = input()
k = 1
rank = [0] * (n+1)
tmp = [0] * (n+1)
sa = [''] * (n+1)

def compare_sa(i,j):
	if rank[i] != rank[j]:
		return -1 if rank[i] < rank[j] else 1
	else:
		if i + k <= n:
			ri = rank[i+k]
		else:
			ri = -1
		if j + k <= n:
			rj = rank[j+k]
		else:
			rj = -1
		return -1 if ri < rj else 1


for i in range(n+1):
	sa[i] = i
	if i < n:
		rank[i] = ord(s[i])
	else:
		rank[i] = -1

while k <= n:

	sa = sorted(sa,key=cmp_to_key(compare_sa))

	tmp[sa[0]] = 0

	for i in range(1,n+1):
		if compare_sa(sa[i-1],sa[i]) == -1:
			tmp[sa[i]] = tmp[sa[i-1]] + 1
		else:
			tmp[sa[i]] = tmp[sa[i-1]]

	for i in range(n+1):
		rank[i] = tmp[i]

	k *= 2

#saはインデックス、sorted_listは実際の文字列
sorted_list = []
for i in range(n+1):
	sorted_list.append(s[sa[i]:])
#print(sa)
#print(sorted_list)

"""
#文字列検索
T = ['ab','abra','abc','abracadabra','abracadabraaa','brabra','bra']
for t in T:
	start = bisect.bisect_left(sorted_list,t)
	end = bisect.bisect_left(sorted_list,t[:-1]+chr(ord(t[-1])+1))
	if start == end:
		print(t+'は存在しません')
	else:
		print(t+'は存在します')

#lcp配列の作成
def getLCP(i,j):
	h = 0
	while i+h < n and j+h < n:
		if s[j+h] != s[i+h]:
			break
		h+=1
	return h

#lcp配列の最大値=最長の共通部分文字列のインデックス
#ans = sorted_list[ lcp.index(max(lcp)) ]
#ans = ans[:max(lcp)]
#print(ans)

ans = 0
for i in range(0,n):
	for j in range(i+1,n):
		lcp = min(getLCP(i,j),j-i)
		ans = max(ans,lcp)

print(ans)
"""
def getLCP(i,j):
	lcp = 0
	while i+lcp < n and j+lcp < n:
		if s[j+lcp] != s[i+lcp]:
			break
		lcp+=1
	return lcp

#lcp配列の作成
lcp = []
for i in range(1,n+1):
	h = 0
	while sa[i]+h < n and sa[i-1]+h < n:
		if s[sa[i-1]+h] != s[sa[i]+h]:
			break
		h+=1
		
	if h > n/2:
		for j in range(i,n+1):
			h = min(getLCP(i,j),j-i)
			
	lcp.append(h)
#print(lcp)
#lcp配列の最大値=最長の共通部分文字列のインデックス
ans = max(lcp)
print(ans)

Submission status: Wrong Answer

Solution code:
from functools import cmp_to_key
import math
import bisect

n = int(input())
s = input()
k = 1
rank = [0] * (n+1)
tmp = [0] * (n+1)
sa = [''] * (n+1)

def compare_sa(i,j):
	if rank[i] != rank[j]:
		return -1 if rank[i] < rank[j] else 1
	else:
		if i + k <= n:
			ri = rank[i+k]
		else:
			ri = -1
		if j + k <= n:
			rj = rank[j+k]
		else:
			rj = -1
		return -1 if ri < rj else 1


for i in range(n+1):
	sa[i] = i
	if i < n:
		rank[i] = ord(s[i])
	else:
		rank[i] = -1

while k <= n:

	sa = sorted(sa,key=cmp_to_key(compare_sa))

	tmp[sa[0]] = 0

	for i in range(1,n+1):
		if compare_sa(sa[i-1],sa[i]) == -1:
			tmp[sa[i]] = tmp[sa[i-1]] + 1
		else:
			tmp[sa[i]] = tmp[sa[i-1]]

	for i in range(n+1):
		rank[i] = tmp[i]

	k *= 2

#saはインデックス、sorted_listは実際の文字列
sorted_list = []
for i in range(n+1):
	sorted_list.append(s[sa[i]:])
#print(sa)
#print(sorted_list)

"""
#文字列検索
T = ['ab','abra','abc','abracadabra','abracadabraaa','brabra','bra']
for t in T:
	start = bisect.bisect_left(sorted_list,t)
	end = bisect.bisect_left(sorted_list,t[:-1]+chr(ord(t[-1])+1))
	if start == end:
		print(t+'は存在しません')
	else:
		print(t+'は存在します')

#lcp配列の作成
def getLCP(i,j):
	h = 0
	while i+h < n and j+h < n:
		if s[j+h] != s[i+h]:
			break
		h+=1
	return h

#lcp配列の最大値=最長の共通部分文字列のインデックス
#ans = sorted_list[ lcp.index(max(lcp)) ]
#ans = ans[:max(lcp)]
#print(ans)

ans = 0
for i in range(0,n):
	for j in range(i+1,n):
		lcp = min(getLCP(i,j),j-i)
		ans = max(ans,lcp)

print(ans)
"""

#lcp配列の作成
lcp = []
for i in range(1,n+1):
	h = 0
	while sa[i]+h < n and sa[i-1]+h < n:
		if s[sa[i-1]+h] != s[sa[i]+h]:
			break
		h+=1
	if h > n/2:
		h = math.floor(n/2)
	lcp.append(h)

#lcp配列の最大値=最長の共通部分文字列のインデックス
ans = max(lcp)
print(ans)

Submission status: Wrong Answer

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

    def z_algo(s):
        """
        param s:str
        return list of int with length len(s)
        """
        # initialization
        n=len(s)
        z=[0]*n
        z[0]=n
        # construct
        L,R=0,0
        for i in range(1,n):
            if i>R: # 過去の結果が全く使えない
                L=R=i
                while(R<n and s[R-L]==s[R]): R+=1
                z[i]=R-L
                R-=1 # 0-indexedでiと比較するため
            elif z[i-L]<R-i+1:
                z[i]=z[i-L]
            else:
                L=i
                R+=1 # Rまでは確定しているので、R+1から確認
                while(R<n and s[R-L]==s[R]): R+=1
                z[i]=R-L
                R-=1
        return z

    ans = 0
    for i in range(N-1):
        z = z_algo(S[i:])
        z = z[(len(z)+1)//2:]
        max_z = max(z)
        ans = max(ans, max_z)
    print(ans)

resolve()

Submission status: Wrong Answer

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

    def z_algo(s):
        """
        param s:str
        return list of int with length len(s)
        """
        # initialization
        n=len(s)
        z=[0]*n
        z[0]=n
        # construct
        L,R=0,0
        for i in range(1,n):
            if i>R: # 過去の結果が全く使えない
                L=R=i
                while(R<n and s[R-L]==s[R]): R+=1
                z[i]=R-L
                R-=1 # 0-indexedでiと比較するため
            elif z[i-L]<R-i+1:
                z[i]=z[i-L]
            else:
                L=i
                R+=1 # Rまでは確定しているので、R+1から確認
                while(R<n and s[R-L]==s[R]): R+=1
                z[i]=R-L
                R-=1
        return z

    ans = 0
    for i in range(N-1):
        z = z_algo(S[i:])
        z = z[(len(z)+1)//2:]
        for _z in z[(len(z)+1)//2:]:
            if _z != 0:
                ans = max(ans, _z)
                break
    print(ans)

resolve()

Submission status: Wrong Answer

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

def z_algo(s):
    """
    param s:str
    return list of int with length len(s)
    """
    # initialization
    n=len(s)
    z=[0]*n
    z[0]=n
    # construct
    L,R=0,0
    for i in range(1,n):
        if i>R: # 過去の結果が全く使えない
            L=R=i
            while(R<n and s[R-L]==s[R]): R+=1
            z[i]=R-L
            R-=1 # 0-indexedでiと比較するため
        elif z[i-L]<R-i+1:
            z[i]=z[i-L]
        else:
            L=i
            R+=1 # Rまでは確定しているので、R+1から確認
            while(R<n and s[R-L]==s[R]): R+=1
            z[i]=R-L
            R-=1
    return z

ans = 0
for i in range(N-1):
    z = z_algo(S[i:])
    z = z[(len(z)+1)//2:]
    max_z = max(z)
    ans = max(ans, max_z)
print(ans)

Submission status: Wrong Answer

Solution code:
from functools import cmp_to_key
import math
import bisect

n = int(input())
s = input()
k = 1
rank = [0] * (n+1)
tmp = [0] * (n+1)
sa = [''] * (n+1)

def compare_sa(i,j):
	if rank[i] != rank[j]:
		return -1 if rank[i] < rank[j] else 1
	else:
		if i + k <= n:
			ri = rank[i+k]
		else:
			ri = -1
		if j + k <= n:
			rj = rank[j+k]
		else:
			rj = -1
		return -1 if ri < rj else 1


for i in range(n+1):
	sa[i] = i
	if i < n:
		rank[i] = ord(s[i])
	else:
		rank[i] = -1

while k <= n:

	sa = sorted(sa,key=cmp_to_key(compare_sa))

	tmp[sa[0]] = 0

	for i in range(1,n+1):
		if compare_sa(sa[i-1],sa[i]) == -1:
			tmp[sa[i]] = tmp[sa[i-1]] + 1
		else:
			tmp[sa[i]] = tmp[sa[i-1]]

	for i in range(n+1):
		rank[i] = tmp[i]

	k *= 2

#saはインデックス、sorted_listは実際の文字列
sorted_list = []
for i in range(n+1):
	sorted_list.append(s[sa[i]:])
#print(sorted_list)

#文字列検索
"""
T = ['ab','abra','abc','abracadabra','abracadabraaa','brabra','bra']
for t in T:
	start = bisect.bisect_left(sorted_list,t)
	end = bisect.bisect_left(sorted_list,t[:-1]+chr(ord(t[-1])+1))
	if start == end:
		print(t+'は存在しません')
	else:
		print(t+'は存在します')
"""

#lcp配列の作成
lcp = []
for i in range(1,n+1):
	h = 0
	while sa[i]+h < n and sa[i-1]+h < n:
		if s[sa[i-1]+h] != s[sa[i]+h]:
			break
		if sa[i-1]+h == sa[i] or sa[i]+h == sa[i-1]:
			break
		h+=1
	lcp.append(h)

#lcp配列の最大値=最長の共通部分文字列のインデックス
#ans = sorted_list[ lcp.index(max(lcp)) ]
#ans = ans[:max(lcp)]
#print(ans)

print(max(lcp))

Submission status: Wrong Answer

Solution code:
from functools import cmp_to_key
import math
import bisect

n = int(input())
s = input()
k = 1
rank = [0] * (n+1)
tmp = [0] * (n+1)
sa = [''] * (n+1)

def compare_sa(i,j):
	if rank[i] != rank[j]:
		return -1 if rank[i] < rank[j] else 1
	else:
		if i + k <= n:
			ri = rank[i+k]
		else:
			ri = -1
		if j + k <= n:
			rj = rank[j+k]
		else:
			rj = -1
		return -1 if ri < rj else 1


for i in range(n+1):
	sa[i] = i
	if i < n:
		rank[i] = ord(s[i])
	else:
		rank[i] = -1

while k <= n:

	sa = sorted(sa,key=cmp_to_key(compare_sa))

	tmp[sa[0]] = 0

	for i in range(1,n+1):
		if compare_sa(sa[i-1],sa[i]) == -1:
			tmp[sa[i]] = tmp[sa[i-1]] + 1
		else:
			tmp[sa[i]] = tmp[sa[i-1]]

	for i in range(n+1):
		rank[i] = tmp[i]

	k *= 2

#saはインデックス、sorted_listは実際の文字列
sorted_list = []
for i in range(n+1):
	sorted_list.append(s[sa[i]:])
#print(sorted_list)

#文字列検索
"""
T = ['ab','abra','abc','abracadabra','abracadabraaa','brabra','bra']
for t in T:
	start = bisect.bisect_left(sorted_list,t)
	end = bisect.bisect_left(sorted_list,t[:-1]+chr(ord(t[-1])+1))
	if start == end:
		print(t+'は存在しません')
	else:
		print(t+'は存在します')
"""

#lcp配列の作成
lcp = []
for i in range(1,n+1):
	h = 0
	while sa[i]+h < n and sa[i-1]+h < n:
		if s[sa[i-1]+h] != s[sa[i]+h]:
			break
		if sa[i-1]+h == sa[i] or  sa[i]+h == sa[i-1]:
			break
		h+=1
	lcp.append(h)

#lcp配列の最大値=最長の共通部分文字列のインデックス
#ans = sorted_list[ lcp.index(max(lcp)) ]
#ans = ans[:max(lcp)]
#print(ans)

print(max(lcp))

Submission status: Wrong Answer

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


def check(vlen):
    part = set()
    for l1 in range(N - vlen * 2 + 1):
        part.add(S[l1:l1 + vlen])
    for l2 in range(vlen, N - vlen + 1):
        if S[l2:l2 + vlen] in part:
            return True
    return False


oklen = 0
nglen = N // 2 + 1

while nglen - oklen > 1:
    midlen = (oklen + nglen) // 2
    if check(midlen):
        oklen = midlen
    else:
        nglen = midlen
print(oklen)

Submission status: Wrong Answer

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

def z_algo(S):
    N = len(S)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A

ans = 0
for i in range(N):
    z = z_algo(S[i:])
    print(z)
    z = z[(len(z)+1)//2:]
    for _z in z:
        if _z != 0:
            ans = max(ans, _z)
            break
print(ans)

Submission status: Wrong Answer

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


def check(vlen):
    for l1 in range(N - vlen * 2 + 1):
        for l2 in range(l1 + 1, N - vlen + 1):
            if S[l1:l1 + vlen] == S[l2:l2 + vlen]:
                return True
    return False


oklen = 0
nglen = N // 2 + 1

while nglen - oklen > 1:
    midlen = (oklen + nglen) // 2
    if check(midlen):
        oklen = midlen
    else:
        nglen = midlen
print(oklen)

Submission status: Wrong Answer

Solution code:
stringCount = int(input())
targetString = input()

def z_algorithm(str):
  '''
  引数として渡された文字列の各 index(以下i) について
  「str と str[i:|str|-1] の最長共通接頭辞の長さ」を記録した配列 result を返します。
  
  計算量 : O(|S|) 
  Parameters
  ----------
  str : string
    対象文字列
  
  Returns
  -------
  result : array[int]
    strとstr[index:]の最長共通接頭辞の長さ
  
  '''
  strLength = len(str)
  result = [0] * strLength
  # 結果の一番最初は対象の文字列全体マッチする
  result[0] = strLength
  i = 1
  j = 0
  
  while i < strLength:
    while (i + j) < strLength and str[j] == str[j+i]:
      j += 1
    if j > (strLength // 2):
      result[i] = 0
    else:
      result[i] = j
    if j == 0:
      i += 1
      continue
    k = 1
    # 今回抽出した文字列内に、これまでの結果が含まれている場合は流用する
    while (i+k) < strLength and (k + result[k]) < j:
      result[i+k] = result[k]
      k += 1
    i += k
    j -= k
  return result

response = 0
for i in range(len(targetString)):
  str = targetString[i:]
  result = z_algorithm(str)
  result[0] = 0
  maxCount = max(result)
  if response < maxCount:
    response = maxCount

print(response)

Submission status: Wrong Answer

Solution code:
import sys

def main():
    def input():
        return sys.stdin.readline()[:-1]
    N = int(input())
    S = "?_" + input()
    dp = [[0 for k in range(N+1)] for l in range(N+1)]
    for k in range(1,N):
        for l in range(k+1,N+1):
            if S[k] == S[l]:
                dp[k][l] = dp[k-1][l-1] + 1
    ans = 0
    for k in range(1,N):
        for l in range(k+1,N+1):
            if l-k >= dp[k][l]:
                ans = max(ans,dp[k][l])

    print(ans)
if __name__ == '__main__':
    main()