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 sys import stdin

N = int(stdin.readline().rstrip())
S = stdin.readline().rstrip()
ans = []

for i in range(N):
    cnt = 0
    for j in range(i):
        if i + cnt == N:
            ans.append(cnt)
            cnt = 0
            break
        if i + cnt < N and S[j] == S[i + cnt]:
            cnt += 1
            if j == i - 1:
                ans.append(cnt)
                cnt = 0
        else:
            ans.append(cnt)
            cnt = 0
            if j == i - 1:
                ans.append(cnt)
                cnt = 0

print(max(ans))

Submission status: Wrong Answer

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

def build_suffix_array(s):
  sa = []
  for i in range(len(s)):
    sa.append((s[i:],i+1))
  sa.sort()
  return sa

ans = 0
sa = build_suffix_array(S)
for i in range(N):
  s1,k1 = sa[i]
  #print('{} {}'.format(s1,k1))
  for j in range(i+1,N):
    s2,k2 = sa[j]
    #print('  {} {} (>{})'.format(s2,k2,i+k1))
    if len(s1)<=len(s2) and s1==s2[0:len(s1)] and (k2+len(s1)<=k1 or k1+len(s2)<=k2):
      ans = max(ans,len(s1))
      # i=9 k1=9 k2=3
      #print('    OK! len={}   {}  {}  {}'.format(len(s1),i,k1,k2))
      break
      # and (i+k1 <= k2 or j+k2 <= k1)
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin

N = int(stdin.readline().rstrip())
S = stdin.readline().rstrip()
ans = []

for i in range(N):
    cnt = 0
    for j in range(i):
        if i + cnt < N and S[j] == S[i + cnt]:
            cnt += 1
            if j == i - 1:
                ans.append(cnt)
        else:
            ans.append(cnt)
            cnt = 0
            if j == i - 1:
                ans.append(cnt)

print(max(ans))

Submission status: Wrong Answer

Solution code:
from sys import stdin

N = int(stdin.readline().rstrip())
S = stdin.readline().rstrip()
ans = []

for i in range(N):
    cnt = 0
    for j in range(i):
        if i + cnt < N and S[j] == S[i + cnt]:
            cnt += 1
        else:
            ans.append(cnt)
            cnt = 0
        if j == i - 1:
            ans.append(cnt)

print(max(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
dp = [[0]*(N+1) for _ in range(N+1)]
res = 0
for i in range(N-1,-1,-1):
  for j in range(N-1,i,-1):
    if S[i]==S[j]:
      dp[i][j]=max(dp[i+1][j+1]+1,dp[i][j])
    res = max(res,min(j-1,dp[i][j]))
print(res)

Submission status: Wrong Answer

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

def main():
    n=int(input())
    s=input()[::-1]
    ans=0
    for i in range(n-1):
        for j in range(i+1,n):
            d=0
            while s[i+d]==s[j+d] and j+d<n and i+d<j:
                d+=1
            ans=max(ans,d)
    print(ans)
main()

Submission status: Wrong Answer

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

yes = 0
no = n // 2 + 1
while abs(yes - no) > 1:
	center = (yes + no) // 2
	d = set()
	for i in range(center):
		d.add(s[i:i+center])
	for i in range(center, n - center + 1):
		if (s[i:i+center] in d):
			yes = center
			#print(s[i:i+center])
			break
		else:
			d.add(s[i:i+center])
	if (yes != center):
		no = center
print(yes)

Submission status: Wrong Answer

Solution code:
import sys

def main():

	input = sys.stdin.readline
	N = int(input().strip())
	S = list(input().strip())

	maxlen = 0
	
	for i in range(1,N):
		SS = S[i:N]
		Z = [0]*len(SS)
		Z[0] = len(SS)
		ZA = [0]*len(SS)
		ZA[0] = min(0,Z[0])
		rt = 0
		lt = 0

		for k in range(1,len(SS)):
			if k>rt:
				n = 0
				while n+k<len(SS) and SS[n]==SS[n+k]:
					n += 1
				Z[k] = n
				ZA[k] = min(k,Z[k])
				if n>0:
					lt = k
					rt = k+n-1
			else:
				p = k-lt
				rlen = rt-k+1

				if Z[p]<rlen:
					Z[k] = Z[p]
					ZA[k] = min(k,Z[k])
				else:
					i = rt+1
					while i<len(SS) and SS[i]==SS[i-k]:
						i += 1
					Z[k] = i-k
					ZA[k] = min(k,Z[k])
					lt = k
					rt = i-1
		
		maxlen = max(maxlen,max(ZA))

	print(maxlen)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

r = 1 #検索の右端初期位置
ans = 0
for l in range(N): #左端を1個ずつ動かして探索
    while True:
        #print(S.rfind(S[l:r+1]), S[l:r+1], l, r)  #strオブジェクト.rfindは探索する文字列を引数に入れて、右から探す。
                                                  #ヒットする場合はインデックスを、しない場合は-1を返す
        if S.rfind(S[l:r+1]) >= r+1: #繰り返し文字列の開始位置が、元の文字列の右端よりも右側であることを確認 
            r += max(1,ans) #次の右端に移る準備
            ans = max(ans, r-l) #文字列の長さとしてより長いほうを残す
        else:
            break 
print(ans)

Submission status: Wrong Answer

Solution code:
S = "abcabcbcbcabcb"
N=len(S)

r = 1 #検索の右端初期位置
ans = 0
for l in range(N): #左端を1個ずつ動かして探索
    r+=ans
    while True:
        #print(S.rfind(S[l:r+1]), S[l:r+1], l, r)  #strオブジェクト.rfindは探索する文字列を引数に入れて、右から探す。
                                                  #ヒットする場合はインデックスを、しない場合は-1を返す
        if S.rfind(S[l:r+1]) >= r+1: #繰り返し文字列の開始位置が、元の文字列の右端よりも右側であることを確認 
            r += 1 #次の右端に移る準備
            ans = max(ans, r-l) #文字列の長さとしてより長いほうを残す
        else:
            break 
print(ans)

Submission status: Wrong Answer

Solution code:
S = "abcabcbcbcabcb"
N=len(S)

r = 1 #検索の右端初期位置
ans = 0
for l in range(N): #左端を1個ずつ動かして探索
    r+=ans
    while True:
        print(S.rfind(S[l:r+1]), S[l:r+1], l, r)  #strオブジェクト.rfindは探索する文字列を引数に入れて、右から探す。
                                                  #ヒットする場合はインデックスを、しない場合は-1を返す
        if S.rfind(S[l:r+1]) >= r+1: #繰り返し文字列の開始位置が、元の文字列の右端よりも右側であることを確認 
            r += 1 #次の右端に移る準備
            ans = max(ans, r-l) #文字列の長さとしてより長いほうを残す
        else:
            break 
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    S = input()
    ans = 0

    for i in range(N):
        s1 = S[0:i+1]
        s2 = S[i+1:N]
        for j in range(i):
            s = s1[j:]
            if s in s2:
                ans = len(s)
                break
        if len(s2) < ans and len(s1) > len(s2):
            break

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# YouTube
def main():
    n = int(input())
    s = input()
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    for i, c in enumerate(s[:-1]):
        for j in range(i + 1, n):
            if c == s[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
    ans = 0
    for d in range(n // 2 + 2, 0, -1):
        if ans >= d: break
        for i in range(n - d + 1):
            a = min(d, dp[i][i + d])
            ans = max(a, ans)
    print(ans)

main()

Submission status: Wrong Answer

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

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

for i in range(N-1, 0, -1):
  for j in range(N-1, 0, -1):
    if s[i] != s[j]:
      dp[i][j] = 0
    else:
      dp[i][j] = dp[i+1][j+1] + 1
    
ans = 0
for i in range(N):
  for j in range(N):
    if i >= j:
      continue
    now = min(dp[i][j], j - i)
    ans = max(ans, now)
print(ans)

Submission status: Wrong Answer

Solution code:
# YouTube
def main():
    n = int(input())
    s = input()
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    for i, c in enumerate(s[:-1]):
        for j in range(i + 1, n):
            if c == s[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
    ans = 0
    for d in range(n // 2 + 1, 0, -1):
        if ans >= d: break
        for i in range(n - d + 1):
            a = min(d, dp[i][i + d])
            ans = max(a, ans)
            if a == d: break
    print(ans)

main()