Problem:


Score : 500 points

Problem Statement

Given is a string S of length N.

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

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

l_1 + len \leq l_2

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

If there is no such integer len, print 0.

Constraints

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

|S| = N

S consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

N
S

Output

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

Sample Input 1

5
ababa

Sample Output 1

2

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

Sample Input 2

2
xy

Sample Output 2

0

No non-empty string satisfies the conditions.

Sample Input 3

13
strangeorange

Sample Output 3

5



Sample input:
5
ababa


Sample output:
2

Submission status: Wrong Answer

Solution code:
import 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 (zln + 2 - 1) // 2 < zln:
            mt = max(mt, max(zl[(zln + 2 - 1) // 2:]))
    print(mt)


if __name__ == '__main__':
    solve()

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
        mt = max(mt, max(zl[zln // 2:]))
    print(mt)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
def main():
    class rolling_hash():
        def __init__(self, sequence, char_list=None):
            self.sequence = sequence  # 文字列
            self.seq_size = len(self.sequence)  # 文字列の長さ
            self.mod = 10**9+7  # mod
            if char_list is None:  # 使われている文字のリスト
                self.char_list = "abcdefghijklmnopqrstuvwxyz"
            else:
                self.char_list = char_list
            self.base = len(self.char_list)+1  # 文字の種類数
            self.char_dict = {j: i+1 for i,
                              j in enumerate(self.char_list)}  # 文字と数値の対応表
            self.Hash_0start = [0]*(self.seq_size+1)  # 先頭からi-1文字目までのハッシュ値
            for i in range(self.seq_size):
                self.Hash_0start[i+1] = self.Hash_0start[i] + \
                    self.char_dict[self.sequence[i]] * \
                    pow(self.base, i, self.mod)

        def calc_hash(self, l, r):  # l文字目からr-1文字目までのハッシュ値
            return ((self.Hash_0start[r] - self.Hash_0start[l])
                    * pow(self.base, l*(self.mod-2), self.mod)) % self.mod

    n = int(input())
    s = input()
    h_s = rolling_hash(s)

    def value(num):
        h_dict = {}
        for i in range(len(s)-num+1):
            j = h_s.calc_hash(i, i+num)
            if j not in h_dict.keys():
                h_dict[j] = i
            else:
                if i-h_dict[j] >= num:
                    return True
        return False

    def b_search(a, b, value):
        while a+1 < b:
            med = (a+b)//2
            if value(med):
                a = med
            else:
                b = med-1
        if a == b:
            return a
        elif a+1 == b:
            if value(b):
                return b
            else:
                return a

    print(b_search(0, len(s), value))


main()

Submission status: Wrong Answer

Solution code:
import sys
n,s =sys.stdin.read().split()
n,maxd,a,b=int(n),0,0,1
while b<=n:
    t=s[a:b]
    if t in s[b:]:
        maxd=max(maxd,b-a)
        b+=1
    else:
        a+=1
        b+=a+maxd
print(maxd)

Submission status: Wrong Answer

Solution code:
import sys
n,s =sys.stdin.read().split()
n,maxd,a,b=int(n),0,0,1
while a<n-maxd:
    t=s[a:b]
    if t in s[b:]:
        maxd=max(maxd,b-a)
        b+=1
    else:
        a+=1
        b+=a+maxd
print(maxd)

Submission status: Wrong Answer

Solution code:
import sys
n,s =sys.stdin.read().split()
n,maxd,a,b=int(n),0,0,1
while a<=n-maxd:
    t=s[a:b]
    if t in s[b:]:
        maxd=max(maxd,b-a)
        b+=1
    else:
        a+=1
        b=a+maxd+1
print(maxd)

Submission status: Wrong Answer

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


def lcs(s1, s2):
    I = len(s1)
    J = len(s2)
    dp = [[0] * (J + 1) for _ in range(I + 1)]

    for i in range(I):
        for j in range(J):
            if s1[i] == s2[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])

    return dp[I][J]


ans = 0
half = N // 2
for i in range(half):
    s1 = S[0:half + i]
    s2 = S[half + i:]
    ans = max(ans, lcs(s1, s2))
    s1 = S[0:half - i]
    s2 = S[half - i:]
    ans = max(ans, lcs(s1, s2))

    if ans >= half - i:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
print("speed test")

N=int(input())
S=input()
 
dp=[[0 for i in range(N + 1)] for j in range(N + 1)]
 
for i in range(N):
  for j in range(i + 1, N):
    if S[i] == S[j]:
      dp[i][j] = dp[i - 1][j - 1] + 1
#print(dp)
 
answer = 0
for i in range(N):
  for j in range(i + 1, N):
    if answer < dp[i][j] and j - i >= dp[i][j]:
      answer = dp[i][j]
print(answer)

Submission status: Wrong Answer

Solution code:
def main():
    import numpy as np
    n = int(input())
    alphabet = "abcdefghijklmnopqrstuvwxyz"
    d_alpha = {j: i for i, j in enumerate(alphabet)}
    s = input()
    s = np.array([d_alpha[i] for i in s], dtype=np.int8)
    m = 0
    print(m)


main()

Submission status: Wrong Answer

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

ans = 0
for i in range(N):
  j_start = ans + 1
  j_end = (N - i) // 2
  for j in range(j_start, j_end):
    base = S[i:i+j]
    if base in S[i+j:]:
      ans = max(ans, j)


print(ans)

Submission status: Wrong Answer

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

ans = 0
for dl in list(range(1, N // 2 + 1))[::-1]:
    if dl < ans: break
    cnt = 0
    ans_tmp = 0
    for l1 in range(N - dl):
        l2 = l1 + dl
        if S[l1] == S[l2]:
            # print("##", l1, l2)
            cnt += 1
        else:
            ans_tmp = max(ans_tmp, cnt)
            cnt = 0
    else:
        ans_tmp = max(ans_tmp, cnt)
    #
    # print("#", dl, ans_tmp)
    ans = max(ans, min(dl, ans_tmp))

print(ans)

Submission status: Wrong Answer

Solution code:
def main():

    def func(s):
        return ord(s)-ord('a')

    n=int(input())
    s=input()
    s=[func(s[i]) for i in range(n)]
    ans=0

    for i in range(n-1):
        if ans*2>=n-i: break
        tmp=0
        for j in range(i+ans+1,n):
            if s[j]==s[i+tmp] and i+2*tmp<j: tmp+=1
            else:
                if tmp>ans: ans=tmp
                tmp=0
        if tmp>ans: ans=tmp

    print(ans)
            

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def func(s):
    return ord(s)-ord('a')

n=int(input())
s=input()
s=[func(s[i]) for i in range(n)]
ans=0

for i in range(n-1):
    if ans>=(n-i)//2: break
    tmp=0
    for j in range(i+ans+1,n):
        if s[j]==s[i+tmp] and i+2*tmp<j: tmp+=1
        else:
            if tmp>ans: ans=tmp
            tmp=0
    if tmp>ans: ans=tmp

print(ans)

Submission status: Wrong Answer

Solution code:
def main():

    def func(s):
        return ord(s)-ord('a')

    n=int(input())
    s=input()
    s=[func(s[i]) for i in range(n)]
    ans=0

    for i in range(n-1):
        if ans>=(n-i)//2: break
        tmp=0
        for j in range(i+ans+1,n):
            if s[j]==s[i+tmp] and i+2*tmp<j: tmp+=1
            else:
                if tmp>ans: ans=tmp
                tmp=0
        if tmp>ans: ans=tmp

    print(ans)
            

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():

    def func(s):
        return ord(s)-ord('a')

    n=int(input())
    s=input()
    s=[func(s[i]) for i in range(n)]
    sign=0
    ans=0

    for i in range(n-1):
        if ans>=(n-i)//2: break

        for j in range(i+1,n):
            if s[j]==s[i+sign] and i+2*sign<j:
                sign+=1

            else:
                if sign>ans: ans=sign
                sign=0

        if sign>ans: ans=sign
        sign=0

    print(ans)
            

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    
    def func(s):
        return ord(s)-ord('a')

    n=int(input())
    s=input()
    s=[func(s[i]) for i in range(n)]
    sign=0
    ans=0

    for i in range(n-1):
        if ans>(n-i)//2: break
        for j in range(i+1,n):
            if s[j]==s[i+sign] and i+2*sign<j:
                sign+=1

    
            else:
                sign=0
                if sign>ans: ans=sign
                
        if sign>ans: ans=sign
        sign=0
    
    if sign>ans: ans=sign
    print(ans)
            

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    def func(s):
        return ord(s)-ord('a')

    n=int(input())
    s=input()
    s=[func(s[i]) for i in range(n)]
    sign=0
    ans=0
    for i in range(n-1):
        if ans>(n-i)//2: break
        for j in range(i+1,n):
            if s[j]==s[i+sign] and i+2*sign<j:
                sign+=1
                if sign>ans: ans=sign
    
            else:
                sign=0
                
        ans=max(sign,ans)
        sign=0

    ans=max(sign,ans)
    print(ans)
            

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    def func(s):
        return ord(s)-ord('a')

    n=int(input())
    s=input()
    s=[func(s[i]) for i in range(n)]
    sign=0
    ans=0
    for i in range(n-1):
        if ans>(n-i)//2: break
        for j in range(i+1,n):
            if s[j]==s[i+sign] and i+2*sign<=j:
                sign+=1
    
            else:
                ans=max(sign,ans)
                sign=0
                
        ans=max(sign,ans)
        sign=0

    ans=max(sign,ans)
    print(ans)
            

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    def func(s):
        return ord(s)-ord('a')

    n=int(input())
    s=input()
    s=[func(s[i]) for i in range(n)]
    sign=0
    ans=0
    for i in range(n-1):
        if ans>(n-i)//2: break
        for j in range(i+1,n):
            if s[j]==s[i+sign] and i+2*sign<j:
                sign+=1
    
            else:
                ans=max(sign,ans)
                sign=0
                
        ans=max(sign,ans)
        sign=0

    ans=max(sign,ans)
    print(ans)
            

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    def func(s):
        return ord(s)-ord('a')

    n=int(input())
    s=input()
    s=[func(s[i]) for i in range(n)]
    sign=0
    ans=0
    for i in range(n-1):

        for j in range(i+1,n):
            if s[j]==s[i+sign] and i+2*sign<j:
                sign+=1
    
            else:
                ans=max(sign,ans)
                sign=0
                
        ans=max(sign,ans)
        sign=0

    ans=max(sign,ans)
    print(ans)
            

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    def func(s):
        return ord(s)-ord('a')

    n=int(input())
    s=input()
    s=[func(s[i]) for i in range(n)]
    sign=0
    ans=0
    for i in range(n-1):

        for j in range(i+1,n):
            if s[j]==s[i+sign] and i+2*sign<j:
                sign+=1
    
            else:
                ans=max(sign,ans)
                sign=0
                
        ans=max(sign,ans)
        sign=0
        
    ans=max(sign,ans)
    print(s)
    print(ans)
            

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    def func(s):
        return ord(s)-ord('a')

    n=int(input())
    s=input()
    s=[func(s[i]) for i in range(n)]
    sign=0
    ans=0
    for i in range(n-1):

        for j in range(i+1,n):
            if s[j]==s[i+sign] and i+2*sign<j:
                sign+=1
    
            else:
                ans=max(sign,ans)
                sign=0

    ans=max(sign,ans)
    print(ans)
            

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    def func(s):
        return ord(s)-ord('a')

    n=int(input())
    s=input()
    s=[func(s[i]) for i in range(n)]
    sign=0
    ans=0
    for i in range(n-1):

        for j in range(i+1,n):
            if s[j]==s[i+sign] and i+2*sign<j:
                sign+=1
    
            else:
                ans=max(sign,ans)
                sign=0
                
        if ans>(n-i)/2: break
    ans=max(sign,ans)
    print(ans)
            

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    def func(s):
        return ord(s)-ord('a')

    n=int(input())
    s=input()
    s=[func(s[i]) for i in range(n)]
    sign=0
    ans=0
    for i in range(n-1):

        for j in range(i+1,n):
            if s[j]==s[i+sign] and i+2*sign<j:
                sign+=1
    
            else:
                ans=max(sign,ans)
                sign=0
        if ans>(n-i)//2: break
    ans=max(sign,ans)
    print(ans)
            

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    def func(s):
        return ord(s)-ord('a')

    n=int(input())
    s=input()
    s=[func(s[i]) for i in range(n)]
    sign=0
    ans=0
    for i in range(n-1):
        if ans>(n-i)//2: break
        for j in range(i+1,n):
            if s[j]==s[i+sign] and i+2*sign<j:
                sign+=1
    
            else:
                ans=max(sign,ans)
                sign=0
    ans=max(sign,ans)
    print(ans)
            

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    def func(s):
        return ord(s)-ord('a')

    n=int(input())
    s=input()
    s=[func(s[i]) for i in range(n)]
    sign=0
    ans=0

    for i in range(n-1):        
        for j in range(i+1,n):
            if s[j]==s[i+sign] and i+2*sign<j:
                sign+=1

            else:
                if sign>ans: ans=sign
                sign=0
                if ans>n-j: break
        
        if sign>ans: ans=sign
        sign=0

    ans=max(sign,ans)
    print(ans)
        

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    def func(s):
        return ord(s)-ord('a')

    n=int(input())
    s=input()
    s=[func(s[i]) for i in range(n)]
    sign=0
    ans=0
    for i in range(n-1):
        for j in range(i+1,n):
            if s[j]==s[i+sign] and i+2*sign<j:
                sign+=1

            else:
                if sign>ans: ans=sign
                sign=0
        
        if sign>ans: ans=sign
        sign=0

    print(ans)
        

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    def func(s):
        return ord(s)-ord('a')

    n=int(input())
    s=input()
    s=[func(s[i]) for i in range(n)]
    sign=0
    ans=0
    for i in range(n-1):

        if ans>(n-i)/2: break

        for j in range(i+1,n):
            if s[j]==s[i+sign] and i+2*sign<j:
                sign+=1

            else:
                if sign>ans: ans=sign
                sign=0
        
        if sign>ans: ans=sign
        sign=0

    print(ans)
        

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    def func(s):
        return ord(s)-ord('a')

    n=int(input())
    s=input()
    s=[func(s[i]) for i in range(n)]
    sign=0
    ans=0
    for i in range(n-1):

        if ans>(n-i)/2: break

        for j in range(i+1,n):
            if s[j]==s[i+sign] and i+2*sign<j:
                sign+=1

            else:
                if sign>ans: ans=sign
                sign=0
            if ans>n-j-sign: break
        
        if sign>ans: ans=sign
        sign=0

    print(ans)
        

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    def func(s):
        return ord(s)-ord('a')

    n=int(input())
    s=input()
    s=[func(s[i]) for i in range(n)]
    sign=0
    ans=0
    for i in range(n-1):
        
        if ans>(n-i)//2: break

        for j in range(i+1,n):
            if s[j]==s[i+sign] and i+2*sign<j:
                sign+=1

            else:
                if sign>ans: ans=sign
                sign=0
                if ans>n-j: break
        
        if sign>ans: ans=sign
        sign=0

    ans=max(sign,ans)
    print(ans)
        

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    def func(s):
        return ord(s)-ord('a')
    n=int(input())
    s=input()
    s=[func(s[i]) for i in range(n)]
    sign=0
    ans=0
    for i in range(n-1):
        if ans>(n-i)//2: break
        for j in range(i+1,n):
            if s[j]==s[i+sign] and i+2*sign<j:
                sign+=1

            else:
                ans=max(sign,ans)
                sign=0
                if ans>n-j: break

    ans=max(sign,ans)
    print(ans)
        

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    def func(s):
        return ord(s)-ord('a')
    n=int(input())
    s=input()
    s=[func(s[i]) for i in range(n)]
    sign=0
    ans=0
    for i in range(n-1):
        for j in range(i+1,n):
            if s[j]==s[i+sign] and i+2*sign<j:
                sign+=1

            else:
                ans=max(sign,ans)
                sign=0
                
    ans=max(sign,ans)
    print(ans)
        

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

res = 0
for k in range(1, N):
    cnt = 0
    for i in range(N - k):
        if i + k < N and S[i + k] == S[i]:
            cnt += 1
            cnt = min(k, cnt)
            res = max(cnt, res)

print(res)

Submission status: Wrong Answer

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

res = 0
for k in range(1, N):
    cnt = 0
    for i in range(N - k):
        if i + k < N and S[i + k] == S[i]:
            cnt += 1
        cnt = min(k, cnt)
        res = max(cnt, res)

print(res)

Submission status: Wrong Answer

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

dp = [0]*n

for i in range(1, n):
  if s[0:i-dp[i-1]-1].find(s[i-dp[i]:i+1]) >= 0:
    dp[i] = dp[i-1]+1
  else:
    dp[i] = dp[i-1]

print(dp[-1])

Submission status: Wrong Answer

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

dp = [0]*n

for i in range(1, n):
  if s[i-dp[i]:i+1] in s[0:i-dp[i-1]-1]:
    dp[i] = dp[i-1]+1
  else:
    dp[i] = dp[i-1]

print(dp[-1])

Submission status: Wrong Answer

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

ng = N//2 + 1
ok = 0

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

while abs(ok-ng) > 1:
    mid = (ok+ng) // 2
    if isok(mid):
        ok = mid
    else:
        ng = mid
        
print(ok)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
ans = 0
for l in range(n):
    ss = s[l:]
    length = n - l
    i, j = 1, 0
    a = [0 for _ in range(length)]
    while i < length:
        while i + j < length and ss[j] == ss[i + j]:
            j += 1
        a[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < length and k + a[k] < j:
            a[i + k] = a[k]
            k += 1
        i += k
        j -= k
    amax = max(a)
    ans = max(ans, min(n // 2, amax))
print(ans)

Submission status: Wrong Answer

Solution code:
# 2019-11-18 17:34:23(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# import re
# import heapq
# import array
# from scipy.misc import comb # (default: exact=False)
# import numpy as np 


def main():
    n, s = sys.stdin.read().split()
    n = int(n)

    res = 0
    l, r = 0, 1
    while r <= l + (n - l) // 2:
        t = s[l:r]
        if t in s[r:]:
            ans = max(res, r - l)
            r += 1
        else:
            l += 1
            if l == r:
                r += 1
    print(res)

if __name__ == "__main__":
    main()

# しゃくとり法的なやつ

Submission status: Wrong Answer

Solution code:
S=input()
a=[0 for x in range(len(S))]

def zal(s):
  a[0]=len(s)
  i,j=1,0
  while i < a[0]:
    while i+j < a[0] and s[j]==s[i+j]:
      j+=1
    a[i]=j
    if j==0:
      i+=1
    else:
      k=1
      while i+k < a[0] and k+a[k] < j:
        a[i+k]=a[k]
        k+=1
      i+=k
      j-=k
  m=0
  for i in range(1,a[0]):
    if i >= a[i]:
      m=max(m,a[i])
  return m

m,i=0,0
while i < len(S)-1:
  m = max(m,zal(S[i:]))
  i += 1

print(m)

Submission status: Wrong Answer

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

A = [[0]*n]*n
for i in range(n-1):
    for j in range(i+1,n):
        if s[i] == s[j]:
            A[i][j] = 1
M = 0
for j in range (1,n):
    M_j = 0
    for k in range(j,n):
        if A[k-j][k]==1:
            M_j += 1
        else:
            M_j = 0
    M_j = min(M_j,j)
    M = max(M,M_j)

print(M)

Submission status: Wrong Answer

Solution code:
n=int(input())
s=input()
ans=0
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

for i in range(n):
    l=z_algo(s[i:])
    l.sort()
    if len(l)>1:
        ans=max(ans,l[-2])
print(ans)

Submission status: Wrong Answer

Solution code:
#import sys
#read = sys.stdin.buffer.read
#input = sys.stdin.buffer.readline
#inputs= sys.stdin.buffer.readlines
#rstrip().decode('utf-8')

#import math
#import numpy as np
#import operator
#import bisect
#from heapq import heapify,heappop,heappush
#from math import gcd
#from fractions import gcd
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from itertools import accumulate
#from itertools import groupby
#from itertools import permutations
#from itertools import combinations
#from scipy.sparse import csr_matrix
#from scipy.sparse.csgraph import floyd_warshall
#from scipy.sparse.csgraph import csgraph_from_dense
#from scipy.sparse.csgraph import dijkstra
#sys.setrecursionlimit(10**7)

#map(int,input().split())

def main():
	n=int(input())
	s=input()
	
	cnt=0
	ans=0
	l2=1
	for l1 in range(n-1):
		l2=l1+1
		while l2<n:
			if s[l1]!=s[l2]:
				l2+=1
			else:
				cnt=1
				x=l1+1
				y=l2+1
				while x<l2 and y<n:
					if s[x]==s[y]:
						cnt+=1
						x+=1
						y+=1
					else:
						break
				l2=max(y-1,l2+1)
				ans=max(ans,cnt)
	print(ans)


if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
#import sys
#read = sys.stdin.buffer.read
#input = sys.stdin.buffer.readline
#inputs= sys.stdin.buffer.readlines
#rstrip().decode('utf-8')

#import math
#import numpy as np
#import operator
#import bisect
#from heapq import heapify,heappop,heappush
#from math import gcd
#from fractions import gcd
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from itertools import accumulate
#from itertools import groupby
#from itertools import permutations
#from itertools import combinations
#from scipy.sparse import csr_matrix
#from scipy.sparse.csgraph import floyd_warshall
#from scipy.sparse.csgraph import csgraph_from_dense
#from scipy.sparse.csgraph import dijkstra
#sys.setrecursionlimit(10**7)

#map(int,input().split())

def main():
	n=int(input())
	s=input()
	
	cnt=0
	ans=0
	l2=1
	for l1 in range(n-1):
		l2=l1+1
		while l2<n:
			if s[l1]!=s[l2]:
				l2+=1
			else:
				cnt=1
				x=l1+1
				y=l2+1
				while x<l2 and y<n:
					if s[x]==s[y]:
						cnt+=1
						x+=1
						y+=1
					else:
						break
				l2=y
				ans=max(ans,cnt)
	print(ans)


if __name__ == '__main__':
	main()

Submission status: Wrong Answer

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

N = int(input())
S = input()[:-1]


def solve():
    dp = [[0]*(N+1) for _ in range(N+1)]
    for l_1, c_1 in zip(range(1, N+1), S):
        for l_2, c_2 in zip(range(l_1+1, N+1), S[l_1+1:]):
            if c_1 == c_2:
                dp[l_1][l_2] = max(dp[l_1][l_2], dp[l_1-1][l_2-1]+1
                                   if l_1 + dp[l_1-1][l_2-1] < l_2 else 0)
    print(max([max(v) for v in dp]))


solve()

Submission status: Wrong Answer

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


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

    dp = [0] * N
    for i, s in enumerate(S):
        if i == 0:
            continue
        before_ans = dp[i-1]
        tmp_ans = S[-(before_ans+1):]
        if tmp_ans in S[:-(before_ans+1)]:
            dp[i] = before_ans + 1
        else:
            dp[i] = before_ans
    print(dp[-1])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

MOD = 104729

def verify(startIndex, index, length):
    want = 0
    for i in range(startIndex, startIndex + length):
        want += ord(S[i]) * pow(256, i-startIndex)
        want %= MOD
    cur = 0
    for i in range(index, index + length):
        cur += ord(S[i]) * pow(256, i - index)

    if cur == want: return True
    for j in range(index + length, N):
        cur -= ord(S[j - length])
        cur //= 256
        cur += ord(S[j]) * pow(256, length - 1)
        cur %= MOD
        if cur == want: return True
    return False

def check(length):
    for i in range(N):
        if i + 2 * length > N: continue
        if verify(i, i+length, length):
            return True
    return False

def binarySearch(lo, hi):
    if lo >= hi:
        return lo
    mid = lo + (hi - lo + 1) // 2
    if check(mid):
        return binarySearch(mid, hi)
    else:
        return binarySearch(lo, mid - 1)

print(binarySearch(0, N//2))

Submission status: Wrong Answer

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

MOD = int(pow(10, 9)) + 7

def verify(startIndex, index, length):
    want = 0
    for i in range(startIndex, startIndex + length):
        want += ord(S[i]) * pow(256, i-startIndex)
        want %= MOD
    cur = 0
    for i in range(index, index + length):
        cur += ord(S[i]) * pow(256, i - index)

    if cur == want: return True
    for j in range(index + length, N):
        cur -= ord(S[j - length])
        cur //= 256
        cur += ord(S[j]) * pow(256, length - 1)
        cur %= MOD
        if cur == want: return True
    return False

def check(length):
    for i in range(N):
        if i + 2 * length > N: continue
        if verify(i, i+length, length):
            return True
    return False

def binarySearch(lo, hi):
    if lo >= hi:
        return lo
    mid = lo + (hi - lo + 1) // 2
    if check(mid):
        return binarySearch(mid, hi)
    else:
        return binarySearch(lo, mid - 1)

print(binarySearch(0, N//2))

Submission status: Wrong Answer

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


def main():
    N = int(input())
    S = input().strip()
    before = "-1"
    tmp = 0
    ans = 0

    for k in range(N):
        now_S = S[k:]
        ans_length = [-1] * (len(now_S)+1)
        j = -1
        for i, c in enumerate(now_S):
            left_end = now_S[j]
            right_end = c
            while j >= 0 and left_end != right_end:
                j = ans_length[j]
                left_end = now_S[j]
            j += 1
            ans_length[i+1] = j
        #print(ans_length)
        for i, length in enumerate(ans_length):
            tmp_max_length = i // 2
            #print(tmp_max_length, length)
            if length <= tmp_max_length:
                ans = max(ans, length)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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


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

    ans = 0
    for k in range(N):
        now_S = S[k:]
        ans_length = [-1] * (len(now_S)+1)
        j = -1
        for i, c in enumerate(now_S):
            left_end = now_S[j]
            right_end = c
            while j >= 0 and left_end != right_end:
                j = ans_length[j]
                left_end = now_S[j]
            j += 1
            ans_length[i+1] = j

        for i, length in enumerate(ans_length):
            tmp_max_length = i // 2
            if length <= tmp_max_length:
                ans = max(ans, length)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def z_algo(n,s):
    x=[0]*n
    j=0
    for i in range(1,n):
        if i+x[i-j]<j+x[j]:
            x[i]=x[i-j]
        else:
            k=max(0,j+x[j]-i)
            while i+k<n and s[k]==s[i+k]:
                k+=1
            x[i]=k
            j=i
    return max(x)

ans=0
for i in range(n):
    ans=max(ans,z_algo(n-i,s[i:]))

print(ans if ans<=n//2 else n//2)