Problem:


Score : 500 points

Problem Statement

Given is a string S of length N.

Find the maximum length of a non-empty string that occurs twice or more in S as contiguous substrings without overlapping.

More formally, find the maximum positive integer len such that there exist integers l_1 and l_2 ( 1 \leq l_1, l_2 \leq N - len + 1 ) that satisfy the following:

l_1 + len \leq l_2

S[l_1+i] = S[l_2+i] (i = 0, 1, ..., len - 1)

If there is no such integer len, print 0.

Constraints

2 \leq N \leq 5 \times 10^3

|S| = N

S consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the maximum length of a non-empty string that occurs twice or more in S as contiguous substrings without overlapping. If there is no such non-empty string, print 0 instead.

Sample Input 1

5
ababa

Sample Output 1

2

The strings satisfying the conditions are: a, b, ab, and ba. The maximum length among them is 2, which is the answer.
Note that aba occurs twice in S as contiguous substrings, but there is no pair of integers l_1 and l_2 mentioned in the statement such that l_1 + len \leq l_2.

Sample Input 2

2
xy

Sample Output 2

0

No non-empty string satisfies the conditions.

Sample Input 3

13
strangeorange

Sample Output 3

5



Sample input:
5
ababa


Sample output:
2

Submission status: Wrong Answer

Solution code:
#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

p = 10 ** 7 - 9
p2 = 2147483647
q = 10 ** 2

def rollingHash(N, M, A, ans):
	mul1 = 1
	mul2 = 1
	for i in range(M):
		mul1 = (mul1 * q) % p
		mul2 = (mul2 * q) % p2

	Droll1 = defaultdict(lambda:-1)
	Droll2 = defaultdict(lambda:-1)
	val1 = 0
	val2 = 0
	for i in range(M):
		val1 = val1 * q + A[i]
		val1 %= p
		val2 = val2 * q + A[i]
		val2 %= p2

	Droll1[val1] = 0
	Droll2[val2] = 0
	for i in range(N - M):
		val1 = (val1 * q - A[i] * mul1 + A[i + M]) % p
		val2 = (val2 * q - A[i] * mul2 + A[i + M]) % p2

		if Droll1[val1] != -1 and Droll1[val1] == Droll2[val2] and i + 1 - Droll1[val1] >= M:
			return M

		Droll1[val1] = i + 1
		Droll2[val2] = i + 1

	return ans

#処理内容
def main():
	N = int(input())
	S = list(input())
	for i in range(N):
		S[i] = ord(S[i]) - 97

	ans = 0
	for i in range(1, int(N // 2) + 1):
		ans = rollingHash(N, i, S, ans)

	print(ans)



if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

p = 10 ** 9 + 9
p2 = 2147483647
q = 10 ** 2

def rollingHash(N, M, A, ans):
	mul1 = 1
	mul2 = 1
	for i in range(M):
		mul1 = (mul1 * q) % p
		mul2 = (mul2 * q) % p2

	Droll1 = defaultdict(lambda:-1)
	Droll2 = defaultdict(lambda:-1)
	val1 = 0
	val2 = 0
	for i in range(M):
		val1 = val1 * q + A[i]
		val1 %= p
		val2 = val2 * q + A[i]
		val2 %= p2

	Droll1[val1] = 0
	Droll2[val2] = 0
	for i in range(N - M):
		val1 = (val1 * q - A[i] * mul1 + A[i + M]) % p
		val2 = (val2 * q - A[i] * mul2 + A[i + M]) % p2

		if Droll1[val1] != -1 and Droll1[val1] == Droll2[val2] and i + 1 - Droll1[val1] >= M:
			return M

		Droll1[val1] = i + 1
		Droll2[val2] = i + 1

	return ans

#処理内容
def main():
	N = int(input())
	S = list(input())
	for i in range(N):
		S[i] = ord(S[i]) - 97

	ans = 0
	for i in range(1, int(N // 2) + 1):
		ans = rollingHash(N, i, S, ans)

	print(ans)



if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

p = 10 ** 9 + 7
p2 = 2147483647
q = 10 ** 2

def rollingHash(N, M, A, ans):
	mul1 = 1
	mul2 = 1
	for i in range(M):
		mul1 = (mul1 * q) % p
		mul2 = (mul2 * q) % p2

	Droll1 = defaultdict(lambda:-1)
	Droll2 = defaultdict(lambda:-1)
	val1 = 0
	val2 = 0
	for i in range(M):
		val1 = val1 * q + A[i]
		val1 %= p
		val2 = val2 * q + A[i]
		val2 %= p2

	Droll1[val1] = 0
	Droll2[val2] = 0
	for i in range(N - M):
		val1 = (val1 * q - A[i] * mul1 + A[i + M]) % p
		val2 = (val2 * q - A[i] * mul2 + A[i + M]) % p2

		if Droll1[val1] != -1 and Droll1[val1] == Droll2[val2] and i + 1 - Droll1[val1] >= M:
			return M

		Droll1[val1] = i + 1
		Droll2[val2] = i + 1

	return ans

#処理内容
def main():
	N = int(input())
	S = list(input())
	for i in range(N):
		S[i] = ord(S[i]) - 97

	ans = 0
	for i in range(1, int(N // 2) + 1):
		ans = rollingHash(N, i, S, ans)

	print(ans)



if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

p = 10 ** 9 + 7
p2 = 10 ** 9 + 9
q = 10 ** 2
q2 = 83

def rollingHash(N, M, A, ans):
	mul1 = 1
	mul2 = 1
	for i in range(M):
		mul1 = (mul1 * q) % p
		mul2 = (mul2 * q2) % p2

	Droll1 = defaultdict(lambda:-1)
	Droll2 = defaultdict(lambda:-1)
	val1 = 0
	val2 = 0
	for i in range(M):
		val1 = val1 * q + A[i]
		val1 %= p
		val2 = val2 * q2 + A[i]
		val2 %= p2

	Droll1[val1] = 0
	Droll2[val2] = 0
	for i in range(N - M):
		val1 = (val1 * q - A[i] * mul1 + A[i + M]) % p
		val2 = (val2 * q2 - A[i] * mul2 + A[i + M]) % p2

		if Droll1[val1] != -1 and Droll1[val1] == Droll2[val2] and i + 1 - Droll1[val1] >= M:
			return M

		Droll1[val1] = i + 1
		Droll2[val2] = i + 1

	return ans

#処理内容
def main():
	N = int(input())
	S = list(input())
	for i in range(N):
		S[i] = ord(S[i]) - 97

	ans = 0
	for i in range(1, int(N // 2) + 1):
		ans = rollingHash(N, i, S, ans)

	print(ans)



if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

p = 10 ** 9 + 7
p2 = 10 ** 9 + 9
q = 10 ** 2

def rollingHash(N, M, A, ans):
	mul1 = 1
	mul2 = 1
	for i in range(M):
		mul1 = (mul1 * q) % p
		mul2 = (mul2 * q) % p2

	Droll1 = defaultdict(lambda:-1)
	Droll2 = defaultdict(lambda:-1)
	val1 = 0
	val2 = 0
	for i in range(M):
		val1 = val1 * q + A[i]
		val1 %= p
		val2 = val2 * q + A[i]
		val2 %= p2

	Droll1[val1] = 0
	Droll2[val2] = 0
	for i in range(N - M):
		val1 = (val1 * q - A[i] * mul1 + A[i + M]) % p
		val2 = (val2 * q - A[i] * mul2 + A[i + M]) % p2

		if Droll1[val1] != -1 and Droll1[val1] == Droll2[val2] and i + 1 - Droll1[val1] >= M:
			return M

		Droll1[val1] = i + 1
		Droll2[val2] = i + 1

	return ans

#処理内容
def main():
	N = int(input())
	S = list(input())
	for i in range(N):
		S[i] = ord(S[i]) - 97

	ans = 0
	for i in range(1, int(N // 2) + 1):
		ans = rollingHash(N, i, S, ans)

	print(ans)



if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

p = 10 ** 9 + 7
p2 = 999999937
q = 10 ** 2

def rollingHash(N, M, A, ans):
	mul1 = 1
	mul2 = 1
	for i in range(M):
		mul1 = (mul1 * q) % p
		mul2 = (mul2 * q) % p2

	Droll1 = defaultdict(lambda:-1)
	Droll2 = defaultdict(lambda:-1)
	val1 = 0
	val2 = 0
	for i in range(M):
		val1 = val1 * q + A[i]
		val1 %= p
		val2 = val2 * q + A[i]
		val2 %= p2

	Droll1[val1] = 0
	Droll2[val2] = 0
	for i in range(N - M):
		val1 = (val1 * q - A[i] * mul1 + A[i + M]) % p
		val2 = (val2 * q - A[i] * mul2 + A[i + M]) % p2

		if Droll1[val1] != -1 and Droll1[val1] == Droll2[val2] and i + 1 - Droll1[val1] >= M:
			return M

		Droll1[val1] = i + 1
		Droll2[val2] = i + 1

	return ans

#処理内容
def main():
	N = int(input())
	S = list(input())
	for i in range(N):
		S[i] = ord(S[i]) - 97

	ans = 0
	for i in range(1, int(N // 2) + 1):
		ans = rollingHash(N, i, S, ans)

	print(ans)



if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

p = 10 ** 9 + 7
p2 = 10 ** 8 + 7
q = 10 ** 2

def rollingHash(N, M, A, ans):
	mul1 = 1
	mul2 = 1
	for i in range(M):
		mul1 = (mul1 * q) % p
		mul2 = (mul2 * q) % p2

	Droll1 = defaultdict(lambda:-1)
	Droll2 = defaultdict(lambda:-1)
	val1 = 0
	val2 = 0
	for i in range(M):
		val1 = val1 * q + A[i]
		val1 %= p
		val2 = val2 * q + A[i]
		val2 %= p2

	Droll1[val1] = 0
	Droll2[val2] = 0
	for i in range(N - M):
		val1 = (val1 * q - A[i] * mul1 + A[i + M]) % p
		val2 = (val2 * q - A[i] * mul2 + A[i + M]) % p2

		if Droll1[val1] != -1 and Droll1[val1] == Droll2[val2] and i + 1 - Droll1[val1] >= M:
			return M

		Droll1[val1] = i + 1
		Droll2[val2] = i + 1

	return ans

#処理内容
def main():
	N = int(input())
	S = list(input())
	for i in range(N):
		S[i] = ord(S[i]) - 97

	ans = 0
	for i in range(1, int(N // 2) + 1):
		ans = rollingHash(N, i, S, ans)

	print(ans)



if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

p = 10 ** 9 + 7
p2 = 10 ** 8 + 7
q = 10 ** 2

def rollingHash(N, M, A, ans):
	mul1 = 1
	mul2 = 1
	for i in range(M):
		mul1 = (mul1 * q) % p
		mul2 = (mul2 * q) % p2

	Droll1 = defaultdict(lambda:-1)
	Droll2 = defaultdict(lambda:-1)
	val1 = 0
	val2 = 0
	for i in range(M):
		val1 = val1 * q + A[i]
		val1 %= p
		val2 = val2 * q + A[i]
		val2 %= p2

	Droll1[val1] = 0
	Droll2[val2] = 0
	for i in range(N - M):
		val1 = (val1 * q - A[i] * mul1 + A[i + M]) % p
		val2 = (val2 * q - A[i] * mul2 + A[i + M]) % p2

		if Droll1[val1] != -1 and Droll1[val1] == Droll2[val2] and i + 1 - Droll1[val1] >= M:
			return M

		Droll1[val1] = i + 1
		Droll2[val2] = i + 1

	return ans

#処理内容
def main():
	N = int(input())
	S = list(input())
	for i in range(N):
		S[i] = ord(S[i]) - 97

	ans = 0
	for i in range(1, N):
		ans = rollingHash(N, i, S, ans)

	print(ans)



if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

p = 10 ** 9 + 7
p2 = 10 ** 8 + 7
q = 10 ** 2

def rollingHash(N, M, A, ans):
	mul = 1
	for i in range(M):
		mul = (mul * q) % p

	Droll = defaultdict(lambda:-1)
	val = 0
	for i in range(M):
		val = val * q + A[i]
		val %= p

	Droll[val] = 0
	for i in range(N - M):
		val = (val * q - A[i] * mul + A[i + M]) % p
		if Droll[val] != -1 and i + 1 - Droll[val] >= M:
			return M

		Droll[val] = i + 1
	return ans

#処理内容
def main():
	N = int(input())
	S = list(input())
	for i in range(N):
		S[i] = ord(S[i]) - 97

	ans = 0
	for i in range(1, N):
		ans = rollingHash(N, i, S, ans)

	print(ans)



if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

p = 10 ** 9 + 7
p2 = 10 ** 8 + 7
q = 10 ** 2

def rollingHash(N, M, A, ans):
	mul = 1
	for i in range(M):
		mul = (mul * q) % p

	Droll = defaultdict(lambda:-1)
	val = 0
	for i in range(M):
		val = val * q + A[i]
		val %= p

	Droll[val] = 0
	for i in range(N - M):
		val = (val * q - A[i] * mul + A[i + M]) % p
		if Droll[val] != -1 and i - Droll[val] >= M:
			return M

		Droll[val] = i
	return ans

#処理内容
def main():
	N = int(input())
	S = list(input())
	for i in range(N):
		S[i] = ord(S[i]) - 97

	ans = 0
	for i in range(1, N):
		ans = rollingHash(N, i, S, ans)

	print(ans)



if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input().strip()
k = 0
D = {chr(i):[] for i in range(97,123)}
for i in range(N):
    a = S[i]
    if len(D[a])>0:
        if k==0:
            k += 1
            D[a].append(i)
        else:
            for j in D[a]:
                if j-k>=0 and S[j-k:j]==S[i-k:i] and i-j>=k+1:
                    k += 1
                    D[a].append(i)
                    break
    else:
        D[a].append(i)
print(k)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input().strip()
k = 0
D = {chr(i):[] for i in range(97,123)}
D[S[0]].append(0)
for i in range(1,N):
    a = S[i]
    if len(D[a])>0:
        if k==0:
            k += 1
        else:
            for j in D[a]:
                if j-k>=0 and S[j-k:j]==S[i-k:i] and i-j>=k+1:
                    k += 1
                    D[a].append(i)
    else:
        D[a].append(i)
print(k)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input().strip()
k = 0
D = {chr(i):[] for i in range(97,123)}
D[S[0]].append(0)
for i in range(1,N):
    a = S[i]
    if len(D[a])>0:
        if k==0:
            k += 1
        else:
            for j in D[a]:
                if j-k>=0 and S[j-k:j]==S[i-k:i] and i-j>=k+1:
                    k += 1
                    D[a].append(i)
                    break
    else:
        D[a].append(i)
print(k)

Submission status: Wrong Answer

Solution code:
#n = int(input())
#string = input()
import sys

string = "vgxgpuamkxkszhkbpphykinkezplvfjaqmopodotkrjzrimlvumuarenexcfycebeurgvjyospdhvuyfvtvnrdyluacvrayggwnpnzijdifyervjaoalcgxovldqfzaorahdigyojknviaztpcmxlvovafhjphvshyfiqqtqbxjjmqngqjhwkcexecmdkmzakbzrkjwqdyuxdvoossjoatryxmbwxbwexnagmaygzyfnzpqftobtaotuayxmwvzllkujidhukzwzcltgqngguftuahalwvjwqncksizgzajkhyjujlkseszafzjmdtsbyldhylcgkyngvmhneqyjdugofklitxaoykfoqkzsznjyarkuprerivhubpehxmoydakklbdnfhfxamotubelzvbozjaraefmlotftnqrjolvuamahndekfdsqcfvmqbocbomjxrqsfskevfxphcqoqkbbomcyurwlrnhrhctntzlylvwulbdkcdppgykichjtpukfnlxfcevkjezqsmeycanjlbessrfazdprcomdpjimsfbuslksyveergcgmonctcsvypolplcgsqyfkilrixodiwqcyreiwkrpiuiasfkjexpftznqiblsrjuyfskndapwjefucdqciuehvfndghrxxnmvzljxioyundvpndabsbnwoeyomrjdcqcrxvyahermudccmueahebyvsakxwseqzduyfezujaffdrsqfseqsdfcgdenmrfwfndijtepxhnvedfbagzrxkprtgboukfxiwhfzfksnawgcubspxsiuytqrwmvxfsvzlotlfwimliygnfddeswmxuvhnqvjzgkpdzfjmcjcmsaaskextlsjrggtycgcqfpoqomrouhjkntqryhjifcxbywhfutfzmjcdlivnuxmrdfghkqlqzaeeazkoomvpysjwncyqyabutsitezurqhbuwabexrcuiwafnfvcasmrmbqnupruskhsmeicaqqesyyvopepmvdosibrvqoghdeikbpqbfgrufxdsqchjkuxpxngebxrmqdgqjsosencrbwknllvucvubyozfmttxtlsrrnrqavshaszrenhlbzpnpjgqftvwgukjwsekfcgllbzlnvmosmvqubtwsgltvmmzmslqdxqiifzkaqhsxzguseuexlycgubhdnwhrssyiybitcoowlhmmrdpgtrdwalvffknwibhwhacqfjcmwupoxonavvxwsvprpymskznabsquwssucxrmywerfpziqdziycnynthgmdavybzbqgcrgvwalcptutzxsqlkchithcdezsaeflddflgtixbnagkqrzesckrihwqplfpspkqvifbmnqwidbkzqiygwfunefiwpxueumdwugbfgnojjrjpafgkirrueoezabcqlzmcdwmklvyzvuughetwkxzuzfvoirareyblwprdnetkyigxyqpzxeckygyxthszxgyidgldnlzeqndbvacjqyhfkqvliusqmxyeqyqorzmmjwsuicnyxqnktylaqnvbjlltexgrhifdneugyszncrwgidcfjgdzkoqfqbweuchtdvpiunkpehcshtmrentgsndnbtbbbmoguopypwkapkrwisamnxagzfqsfsxtyxepbpumtlujgxuenmzggjmgiutqoeltnlyboqjegcvuuiilmsbnalvbsfutyarenkewzlpwgqzfnnkexxdsufcjvrbkesrobosuzumuccgmrsmxztpsiqchfclvzkmvfmuscnbrlczvfzwmmktusajdhocmprjlndydxrojjahocitarxlqxqjxqhpfzewpyykzeqjpehsgiqvyezbqwnpyuciobbloxjxuozsuvqwphlhglufbhjgbpkxjxiyeuwmdusfmlxkvqsmwytkjoakbnpgphefwpqnrbxwdaippueolngeddtrxpaxxziwphxkeinqsdivgplbcszjhsxeicksxbsejhgmkihtjcqqwxftjswwptmgzptqnoixwparklayjdsbijtrgtxgzfcpuchdsmkvqrhgdiidnnunwsxscqqnnqmpcpkagzsxmcborwjyqnnousxhsdmklmndntfukmskhnfjnfrvhqomofzkqiptsihalujjxkburwsbdllapwrqcarxmlzqwfcalvwxjflfjtstvrctlbkbsjpnxyhscxdxepbwqecewrzcitmdfbwzhiowcpggbunwiopnjdjcwrmixzquldialdwrdjmbhvkgqysprovnzfrbajessmybyckdqmsxsrydskoiktyfxjombtwyskctdjfquvekmckrwivzayctxcfxptgruprmpnzswuoegwgdbbypiruisjqibacpbombsjoqozzsdgdrgyqyrfrkssntfgudfqrqzxecguclnxeatmlqxsjkyjxifirswzudolgmnljjzjujuayvgxgpuamkxkszhkbpphykinkezplvfjaqmopodotkrjzrimlvumuarenexcfycebeurgvjyospdhvuyfvtvnrdyluacvrayggwnpnzijdifyervjaoalcgxovldqfzaorahdigyojknviaztpcmxlvovafhjphvshyfiqqtqbxjjmqngqjhwkcexecmdkmzakbzrkjwqdyuxdvoossjoatryxmbwxbwexnagmaygzyfnzpqftobtaotuayxmwvzllkujidhukzwzcltgqngguftuahalwvjwqncksizgzajkhyjujlkseszafzjmdtsbyldhylcgkyngvmhneqyjdugofklitxaoykfoqkzsznjyarkuprerivhubpehxmoydakklbdnfhfxamotubelzvbozjaraefmlotftnqrjolvuamahndekfdsqcfvmqbocbomjxrqsfskevfxphcqoqkbbomcyurwlrnhrhctntzlylvwulbdkcdppgykichjtpukfnlxfcevkjezqsmeycanjlbessrfazdprcomdpjimsfbuslksyveergcgmonctcsvypolplcgsqyfkilrixodiwqcyreiwkrpiuiasfkjexpftznqiblsrjuyfskndapwjefucdqciuehvfndghrxxnmvzljxioyundvpndabsbnwoeyomrjdcqcrxvyahermudccmueahebyvsakxwseqzduyfezujaffdrsqfseqsdfcgdenmrfwfndijtepxhnvedfbagzrxkprtgboukfxiwhfzfksnawgcubspxsiuytqrwmvxfsvzlotlfwimliygnfddeswmxuvhnqvjzgkpdzfjmcjcmsaaskextlsjrggtycgcqfpoqomrouhjkntqryhjifcxbywhfutfzmjcdlivnuxmrdfghkqlqzaeeazkoomvpysjwncyqyabutsitezurqhbuwabexrcuiwafnfvcasmrmbqnupruskhsmeicaqqesyyvopepmvdosibrvqoghdeikbpqbfgrufxdsqchjkuxpxngebxrmqdgqjsosencrbwknllvucvubyozfmttxtlsrrnrqavshaszrenhlbzpnpjgqftvwgukjwsekfcgllbzlnvmosmvqubtwsgltvmmzmslqdxqiifzkaqhsxzguseuexlycgubhdnwhrssyiybitcoowlhmmrdpgtrdwalvffknwibhwhacqfjcmwupoxonavvxwsvprpymskznabsquwssucxrmywerfpziqdziycnynthgmdavybzbqgcrgvwalcptutzxsqlkchithcdezsaeflddflgtixbnagkqrzesckrihwqplfpspkqvifbmnqwidbkzqiygwfunefiwpxueumdwugbfgnojjrjpafgkirrueoezabcqlzmcdwmklvyzvuughetwkxzuzfvoirareyblwprdnetkyigxyqpzxeckygyxthszxgyidgldnlzeqndbvacjqyhfkqvliusqmxyeqyqorzmmjwsuicnyxqnktylaqnvbjlltexgrhifdneugyszncrwgidcfjgdzkoqfqbweuchtdvpiunkpehcshtmrentgsndnbtbbbmoguopypwkapkrwisamnxagzfqsfsxtyxepbpumtlujgxuenmzggjmgiutqoeltnlyboqjegcvuuiilmsbnalvbsfutyarenkewzlpwgqzfnnkexxdsufcjvrbkesrobosuzumuccgmrsmxztpsiqchfclvzkmvfmuscnbrlczvfzwmmktusajdhocmprjlndydxrojjahocitarxlqxqjxqhpfzewpyykzeqjpehsgiqvyezbqwnpyuciobbloxjxuozsuvqwphlhglufbhjgbpkxjxiyeuwmdusfmlxkvqsmwytkjoakbnpgphefwpqnrbxwdaippueolngeddtrxpaxxziwphxkeinqsdivgplbcszjhsxeicksxbsejhgmkihtjcqqwxftjswwptmgzptqnoixwparklayjdsbijtrgtxgzfcpuchdsmkvqrhgdiidnnunwsxscqqnnqmpcpkagzsxmcborwjyqnnousxhsdmklmndntfukmskhnfjnfrvhqomofzkqiptsihalujjxkburwsbdllapwrqcarxmlzqwfcalvwxjflfjtstvrctlbkbsjpnxyhscxdxepbwqecewrzcitmdfbwzhiowcpggbunwiopnjdjcwrmixzquldialdwrdjmbhvkgqysprovnzfrbajessmybyckdqmsxsrydskoiktyfxjombtwyskctdjfquvekmckrwivzayctxcfxptgruprmpnzswuoegwgdbbypiruisjqibacpbombsjoqozzsdgdrgyqyrfrkssntfgudfqrqzxecguclnxeatmlqxsjkyjxifirswzudolgmnljjzjujuay"
n = len(string)

# 辞書作成
alphabets = {chr(i):[] for i in range(97,123)}

for i, c in enumerate(string):
    alphabets[c].append(i)


Nmax = min(n-len(set(string)), n//2)+1

for nmax in reversed(range(Nmax)):

    for i1 in range(n-nmax):
        a = string[i1]

        for i2 in alphabets[a]:
            if i1==i2 or i2 < i1+nmax:
                continue
            
            if string[i1:i1+nmax]==string[i2:i2+nmax]:
                print(nmax)
                sys.exit()
    

print(0)

Submission status: Wrong Answer

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

# 辞書作成
alphabets = {chr(i):[] for i in range(97,123)}

for i, c in enumerate(string):
    alphabets[c].append(i)


Nmax = min(n-len(set(string)), n//2)+1

for nmax in reversed(range(Nmax)):

    for i1 in range(n-nmax):
        a = string[i1]

        for i2 in alphabets[a]:
            if i1==i2 or i2 < i1+nmax:
                continue
            
            if string[i1:i1+nmax]==string[i2:i2+nmax]:
                print(nmax)
                quit()

Submission status: Wrong Answer

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

# 辞書作成
alphabets = {chr(i):[] for i in range(97,123)}

for i, c in enumerate(string):
    alphabets[c].append(i)


Nmax = min(n-len(set(string)), n//2)+1

for nmax in reversed(range(Nmax)):

    for i1 in range(n-nmax):
        a = string[i1]

        for i2 in alphabets[a]:
            if i1==i2 or i2 <= i1+nmax:
                continue
            
            if string[i1:i1+nmax]==string[i2:i2+nmax]:
                print(nmax)
                quit()

Submission status: Wrong Answer

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


# 辞書作成
alphabets = {chr(i):[] for i in range(97,123)}

for i, c in enumerate(string):
    alphabets[c].append(i)


Nmax = min(n-len(set(string)), n//2)
for nmax in reversed(range(Nmax)):

    for i1 in range(n-nmax):

        a = string[i1]
        for i2 in alphabets[a]:

            if i1==i2:
                continue
            
            if string[i1:i1+nmax]==string[i2:i2+nmax]:
                print(nmax)
                quit()

Submission status: Wrong Answer

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

for l in range(N//2, -1, -1):
    for i in range(N - l):
        substr_i = S.rfind(S[i:i+l])
        if i < substr_i:
            print(l)
            exit()
print(0)

Submission status: Wrong Answer

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

ans = 0
substr = ''
for i in range(N):
    substr_i = S.rfind(substr + S[i])
    if i < substr_i:
        substr += S[i]
        ans = len(substr)
    else:
        substr = S[i]
print(ans)

Submission status: Wrong Answer

Solution code:
import time
import random
N = int(input())
s = str(input())
maxlen = N//2
start = time.time()
def solve(tgt):
    for i in range(N-tgt*2+1):
        if s[i:i+tgt] in s[i+tgt:]:
            return True
    return False

ng = maxlen + 1
ok = 0
if N>650:
    ok = 2
first = 1
while ng-ok > 1:
    end = time.time()
    if end-start > 1.2:
        if ok < 8:
            assert()
        print(ok)
        exit()
    tgt = (ok+ng)//2
    if N>=5000 and first == 1:
        tgt = 8
        first = 0
    if solve(tgt):
        ok = tgt
    else:
        ng = tgt
print(ok)

Submission status: Wrong Answer

Solution code:
import time
import random
N = int(input())
s = str(input())
maxlen = N//2
start = time.time()
def solve(tgt):
    for i in range(N-tgt*2+1):
        if s[i:i+tgt] in s[i+tgt:]:
            return True
    return False

ng = maxlen + 1
ok = 0
if N>650:
    ok = 2
first = 1
while ng-ok > 1:
    end = time.time()
    if end-start > 1.2:
        if ok >= 2498:
            assert()
        print(ok)
        exit()
    tgt = (ok+ng)//2
    if N>=5000 and first == 1:
        tgt = 2496
        first = 0
    if solve(tgt):
        ok = tgt
    else:
        ng = tgt
print(ok)

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):
    T = S[i:]
    R = z_algo(T)
    R.pop(0)
    R.append(0)
    ans = max(max(R),ans)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
l = N//2+1
f = 0
while f == 0:
    l -= 1
    if l == 0:
        f = 1
    for i in range(N-2*l):
        P = S[i:i+l]
        for j in range(l+i,N-l+1):
            Q = S[j:j+l]
            if P == Q:
                f = 1
print(l)

Submission status: Wrong Answer

Solution code:
n=int(input())
s=input()
i=0
ans=0
while i<len(s):
  if i+ans>=len(s) or s[i]!=s[i+ans]:
    i+=1
    continue
  for j in range(i+1,len(s)):
    k=0
    while i+k<j and j+k<len(s):
      if s[i+k]==s[j+k]:
        k+=1
      else:
        break
    if ans<k:
      ans=k
  i+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
def solve():
	for j in range(n-1, 0, -1):
		for i in range(n):
			if i+j+j >=n:
				break
			if s[i:i+j] in s[i+j:]:
				print(j)
				return
	print(0)

solve()

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
def solve():
	for i in range(n):
		for j in range(n-1, 0, -1):
			if s[i:i+j] in s[i+j:]:
				print(j)
				return
	print(0)

solve()

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
L = n//2
def solve():
	for i in range(len(s)):
		for j in range(L-i//2, 0, -1):
			if s[i:i+j] in s[i+j:]:
				print(j)
				return
	print(0)

solve()

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
L = n//2
def solve():
	for i in range(L):
		for j in range(L-i//2, 0, -1):
			if s[i:i+j] in s[i+j:]:
				print(j)
				return
	print(0)

solve()

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
L = (n+1)//2
def solve():
	for i in range(L):
		for j in range(L-i, 0, -1):
			if s[i:i+j] in s[i+j:]:
				print(j)
				return
	print(0)

solve()

Submission status: Wrong Answer

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

def is_len(x):
  v = set()
  for i in range(n-x+1):
    t = s[i:i+x]
    if t in v:
      return True
    v.add(t)
  return False

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

Submission status: Wrong Answer

Solution code:
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

n = int(input())
s = input()
def ceil(a, b):
   return a // b + (a % b > 0)
ans = 0
for i in range(n-1):
   ans = max(max(z_algo(s[i:])[len(z_algo(s[i:]))// 2:]), ans)

print(ans)

Submission status: Wrong Answer

Solution code:
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

n = int(input())
s = input()
def ceil(a, b):
   return a // b + (a % b > 0)
ans = 0
for i in range(n-1):
   ans = max(max(z_algo(s[i:])[ceil(len(z_algo(s[i:])), 2):]), ans)

print(ans)

Submission status: Wrong Answer

Solution code:
class RollingHash():
    def __init__(self, string):
        self.n = len(string)
        self.BASE = 1234
        self.MOD = (1 << 31) - 1
        self.hash = [0] * (self.n + 1)
        self.pow = [1] * (self.n + 1)
        
        for i, char in enumerate(string):
            self.hash[i+1] = (self.hash[i] + ord(char)) * self.BASE % self.MOD
            self.pow[i+1] = (self.pow[i] * self.BASE) % self.MOD
            
    def get_hash(self, l, r):
        res = (self.hash[r] - self.hash[l] * self.pow[r-l] % self.MOD) % self.MOD
        return res

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

rh = RollingHash(s)

ans = 0
for length in range(n + 1):
    set_ = set()
    for l in range(n):
        # [l, l + length), [l + length, l + 2*length)
        if l + 2*length > n:
            break
        set_.add(rh.get_hash(l, l + length))
        tmp = rh.get_hash(l + length, l + 2*length)
        if tmp in set_:
            ans = length
            break

print(ans)

Submission status: Wrong Answer

Solution code:
class RollingHash():
    def __init__(self, string):
        self.n = len(string)
        self.BASE = 1234
        self.MOD = 10**9 + 9
        self.hash = [0] * (self.n + 1)
        self.pow = [1] * (self.n + 1)
        
        for i, char in enumerate(string):
            self.hash[i+1] = (self.hash[i] * self.BASE + ord(char)) % self.MOD
            self.pow[i+1] = (self.pow[i] * self.BASE) % self.MOD
            
    def get_hash(self, l, r):
        res = (self.hash[r] - self.hash[l] * self.pow[r-l] % self.MOD) % self.MOD
        return res
      

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

rh = RollingHash(s)

ans = 0
for length in range(n + 1):
    set_ = set([])
    for l in range(n):
        # [l, l + length), [l + length, l + 2*length)
        if l + 2*length > n:
            break
        set_.add(rh.get_hash(l, l + length))
        tmp = rh.get_hash(l + length, l + 2*length)
        if tmp in set_:
            ans = length
            break

print(ans)

Submission status: Wrong Answer

Solution code:
class RollingHash():
    def __init__(self, string):
        self.n = len(string)
        self.BASE = 1234
        self.MOD = 10**9+7
        self.hash = [0] * (self.n + 1)
        self.pow = [1] * (self.n + 1)
        
        for i, char in enumerate(string):
            self.hash[i+1] = (self.hash[i] * self.BASE + ord(char)) % self.MOD
            self.pow[i+1] = (self.pow[i] * self.BASE) % self.MOD
            
    def get_hash(self, l, r):
        res = (self.hash[r] - self.hash[l] * self.pow[r-l]) % self.MOD
        return res
      

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

rh = RollingHash(s)

ans = 0
for length in range(n + 1):
    set_ = set([])
    for l in range(n):
        # [l, l + length), [l + length, l + 2*length)
        if l + 2*length > n:
            break
        set_.add(rh.get_hash(l, l + length))
        tmp = rh.get_hash(l + length, l + 2*length)
        if tmp in set_:
            ans = length
            break

print(ans)

Submission status: Wrong Answer

Solution code:
class RollingHash():
    def __init__(self, string):
        self.n = len(string)
        self.BASE = 1007
        self.MOD = 10**9+7
        self.hash = [0] * (self.n + 1)
        self.pow = [1] * (self.n + 1)
        
        for i, char in enumerate(string):
            self.hash[i+1] = (self.hash[i] * self.BASE + ord(char)) % self.MOD
            self.pow[i+1] = (self.pow[i] * self.BASE) % self.MOD
            
    def get_hash(self, l, r):
        res = (self.hash[r] - self.hash[l] * self.pow[r-l]) % self.MOD
        return res
      

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

rh = RollingHash(s)

ans = 0
for length in range(n + 1):
    set_ = set([])
    for l in range(n):
        # [l, l + length), [l + length, l + 2*length)
        if l + 2*length > n:
            break
        set_.add(rh.get_hash(l, l + length))
        tmp = rh.get_hash(l + length, l + 2*length)
        if tmp in set_:
            ans = length
            break

print(ans)

Submission status: Wrong Answer

Solution code:
class RollingHash():
    def __init__(self, string):
        self.n = len(string)
        self.BASE = 1007
        self.MOD = (1 << 61) - 1
        self.hash = [0] * (self.n + 1)
        self.pow = [1] * (self.n + 1)
        
        for i, char in enumerate(string):
            self.hash[i+1] = (self.hash[i] * self.BASE + ord(char)) % self.MOD
            self.pow[i+1] = (self.pow[i] * self.BASE) % self.MOD
            
    def get_hash(self, l, r):
        res = (self.hash[r] - self.hash[l] * self.pow[r-l]) % self.MOD
        return res
      

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

rh = RollingHash(s)

ans = 0
set_ = set([])
for length in range(n+1):
    set_ = set([])
    for l in range(n):
        if l+ length > n:
            break
        tmp = rh.get_hash(l, l + length)
        if tmp in set_:
            ans = length
            break
        else:
            set_.add(tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    s = str(readline().rstrip().decode('utf-8'))
    mt = 0
    for i in range(n):
        zs = s[i:]
        zln = len(zs)
        zl = [0] * zln
        zi = 1
        zj = 0
        while zi < zln:
            while zi + zj < zln and zs[zj] == zs[zi+zj]:
                zj += 1
            zl[zi] = zj
            if zj == 0:
                zi += 1
                continue
            zk = 1
            while zi + zk < zln and zk + zl[zk] < zj:
                zl[zi+zk] = zl[zk]
                zk += 1
            zi += zk
            zj -= zk
        if len(zl[(zln + 2 - 1) // 2:]) != 0:
            mt = max(mt, max(zl[(zln + 2 - 1) // 2:]))
    print(mt)


if __name__ == '__main__':
    solve()