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: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
S = input()

def bisearch_max(mn, mx, func):
    """ 条件を満たす最大値を見つける二分探索 """

    ok = mn
    ng = mx
    while ok+1 < ng:
        mid = (ok+ng) // 2
        if func(mid):
            # 上を探しに行く
            ok = mid
        else:
            # 下を探しに行く
            ng = mid
    return ok

class RollingHash:

    MOD = 2 ** 64
    b = 10 ** 8 + 7

    def __init__(self, S):
        # 各文字を数値に変換しておく
        S = [ord(s)-97 for s in S]

        self.len = len(S)
        self.pow = [1] * (self.len+1)
        for i in range(self.len):
            self.pow[i+1] = self.pow[i] * self.b
            self.pow[i+1] %= self.MOD
        # ハッシュの生成
        self.hash = [0] * (self.len+1)
        for i in range(self.len):
            self.hash[i+1] = self.hash[i] * self.b + S[i]
            self.hash[i+1] %= self.MOD
    
    # 区間[i,j)のハッシュ値を取得
    def get(self, l, r):
        return (self.hash[r] - self.hash[l] * self.pow[r-l]) % self.MOD

def calc(m):
    for i in range(N-m*2+1):
        a_hash = rh.get(i, i+m)
        for j in range(i+m, N-m+1):
            b_hash = rh.get(j, j+m)
            if a_hash == b_hash:
                return True
    return False

rh = RollingHash(S)
print(bisearch_max(0, N, calc))

Submission status: Time Limit Exceeded

Solution code:
if __name__ == "__main__":
    N = int(input())
    S = input()

    dp = [[0] * 5005 for i in range(5005)]

    for i in range(N, 0, -1):
        for j in range(N, 0, -1):
            if S[i-1] != S[j-1]:
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i+1][j+1] + 1

    result = 0
    for i in range(N):
        for j in range(N):
            if i >= j:
                continue
            now = min(dp[i][j], j-i)
            result = max([now, result])

    print(result)

Submission status: Time Limit Exceeded

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

yes = 0
no = n // 2 + 1
while abs(yes - no) > 1:
	center = (yes + no) // 2
	for i in range(n - 2 * center + 1):
		tempS = s[i:i+center]
		if (tempS in s[i+center:]):
			yes = center
			#print(tempS)
			break
	if (yes != center):
		no = center
print(yes)

Submission status: Time Limit Exceeded

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

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

for i in range(N-1,-1,-1):
    for j in range(N-1,-1,-1):
        # print(i,j)
        if S[i] == S[j]:
            dp[i][j] = dp[i+1][j+1] + 1 

# print(dp)
ans = 0
for i in range(N):
    for j in range(N):
       val = min(abs(i-j),dp[i][j])
       ans = max(val,ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque

N = int(input())
S = input()

strList = defaultdict(deque)

for left in range(N):
    sub = [S[left]]
    strList[''.join(sub)].append(left)
    for right in range(left + 1, N):
        sub.append(S[right])
        strList[''.join(sub)].append(left)

ans = 0
for sub, leftList in strList.items():
    leng = len(sub)
    if leftList[0] + leng <= leftList[-1]:
        ans = max(ans, leng)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque

N = int(input())
S = input()

strList = defaultdict(deque)

for left in range(N):
    sub = S[left]
    strList[sub].append(left)
    for right in range(left + 1, N):
        sub += S[right]
        strList[sub].append(left)

ans = 0
for sub, leftList in strList.items():
    leng = len(sub)
    if leftList[0] + leng <= leftList[-1]:
        ans = max(ans, leng)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque

N = int(input())
S = input()

strList = defaultdict(deque)

for leng in range(N // 2 + 1):
    for left in range(N - leng + 1):
        sub = S[left: left + leng]
        strList[sub].append(left)

ans = 0
for sub, leftList in strList.items():
    leng = len(sub)
    if leftList[0] + leng <= leftList[-1]:
        ans = max(ans, leng)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

N = int(input())
S = input()

strList = defaultdict(list)

for leng in range(N // 2 + 1):
    for left in range(N - leng + 1):
        sub = S[left: left + leng]
        strList[sub].append(left)

ans = 0
for sub, leftList in strList.items():
    leng = len(sub)
    if leftList[0] + leng <= leftList[-1]:
        ans = max(ans, leng)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

N = int(input())
S = input()

strList = defaultdict(list)

for leng in range(N):
    for left in range(N - leng + 1):
        sub = S[left: left + leng]
        strList[sub].append(left)

ans = 0
for sub, leftList in strList.items():
    leng = len(sub)
    if leftList[0] + leng <= leftList[-1]:
        ans = max(ans, leng)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

N = int(input())
S = input()

strList = defaultdict(list)

for leng in range(N):
    for left in range(N - leng + 1):
        sub = S[left: left + leng]
        strList[sub].append(left)

ans = 0
for sub, leftList in strList.items():
    leng = len(sub)
    leftList.sort()
    if leftList[0] + leng <= leftList[-1]:
        ans = max(ans, leng)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
S = input()
dp = np.zeros((N+1)*(N+1)).reshape(N+1, N+1)
max = 0
for i, si in enumerate(S):
  for j, sj in enumerate(S):
      if(i != j and si == sj):
          tmp = dp[i][j]+1
          dp[i+1][j+1] = tmp
          if(tmp > max and abs(i-j+1) > tmp):
              max = tmp
print(int(max))

Submission status: Time Limit Exceeded

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

    for i in range(N):
        s2 = S[i+1:N]
        for j in range(i+1-index):
            s1 = S[index+j:i+1]
            if len(s1) < ans:
                break
            if s1 in s2:
                index = index+j
                ans = len(s1)
                break
        if len(s2) <= ans:
            break

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

dp = [[0] * (n+1) for _ in range(n+1)]
ans = 0

for i in range(n):
    for j in range(i,n):
        if s[i] == s[j]:
            dp[i+1][j+1] = dp[i][j] + 1
            ans = max(ans, min(j-i, dp[i+1][j+1]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:

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

    dp = [[0 for _ in range(N+10)] for _ in range(N+10)]
    ans = 0
    for i in reversed(range(N)):
        for j in reversed(range(i+1,N)):
            if S[i] != S[j]:
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i+1][j+1] + 1
            if i >= j: continue
            tmp = min(dp[i][j], j-i)
            ans = max(ans, tmp)


    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

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

    dp = [[0 for _ in range(N+10)] for _ in range(N+10)]
    ans = 0
    for i in reversed(range(N)):
        for j in reversed(range(N)):
            if S[i] != S[j]:
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i+1][j+1] + 1
            if i >= j: continue
            tmp = min(dp[i][j], j-i)
            ans = max(ans, tmp)


    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

dp = [[0 for _ in range(N+10)] for _ in range(N+10)]
ans = 0
for i in reversed(range(N)):
    for j in reversed(range(N)):
        if S[i] != S[j]:
            dp[i][j] = 0
        else:
            dp[i][j] = dp[i+1][j+1] + 1
        if i >= j: continue
        tmp = min(dp[i][j], j-i)
        ans = max(ans, tmp)


print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
S = input()
m = n//2
l,r = 0,n-1
ans = 0
while l<=r:
    m = (l + r) // 2
#    print("m = ", m)
    for i in range(n-m) :
        # 切り取る
        sub = S[i :i + m]
#        print("sub=", sub)
#        print("i=", i)
        fl = False
        Se = set()
        for j in range(i+m,n - m + 1) :
            sub2 = S[j :j + m]
            Se.add(sub2)
#            print("j=", j, Se)
        if sub in Se:
            fl = True
            l = m+1
            ans = l-1
#            print(l-1,"にて共通部分有")
            break
    else:
        r = m-1
#        print(r+1,"にて共通部分無")
print(ans)

Submission status: Time Limit Exceeded

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, -1, -1):
    for j in range(N-1, i, -1):
        if S[i] == S[j]:
            dp[i][j] = dp[i+1][j+1]+1

ans = 0
for i in range(N):
    for j in range(i+1, N):
        now = min(dp[i][j], j-i)
        ans = max(ans, now)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
S = input()
m = n//2
l,r = 0,n-1
ans = 0
while l<=r:
    m = (l + r) // 2
#    print("m = ", m)
    for i in range(n-m) :
        # 切り取る
        sub = S[i :i + m]
#        print("sub=", sub)
#        print("i=", i)
        fl = False
        Se = set()
        for j in range(i+m,n - m + 1) :
            sub2 = S[j :j + m]
            Se.add(sub2)
#            print("j=", j, Se)
        if sub in Se:
            fl = True
            l = m+1
            ans = l-1
#            print(l-1,"にて共通部分有")
            break
    else:
        r = m-1
#        print(r+1,"にて共通部分無")
print(ans)

Submission status: Time Limit Exceeded

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, -1, -1):
    for j in range(N-1, -1, -1):
        if S[i] == S[j]:
            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: Time Limit Exceeded

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

# 最長共通接頭辞問題(Z-Algorithm)
# 文字列SとS[i:]の最長共通接頭辞を各iについて求める
# 参考：https://codeforces.com/blog/entry/3107
# 図がわかりやすい:https://snuke.hatenablog.com/entry/2014/12/03/214243


def Z_Algorithm(S):
    N = len(S)
    R = 0 # Rはi文字目まで読んだ時、接頭辞の右端のうち一番右側にくるようなもの
    L = 0 # Lはその範囲の左端
    Z = [0 for _ in range(N)] # 答えとなる最長接頭辞の長さ
    Z[0] = N

    for i in range(1, N):
        if i > R:
            # iが前のRより右側ならS[i:]とSのみで考える
            L = i
            R = i
            while (R < N and S[R-L] == S[R]):
                R += 1
            Z[i] = R - L
            R -= 1
        else:
            k = i - L
            if Z[k] < R - i + 1:
                # はみ出さないなら前のがそのまま使える。R,Lはそのまま
                Z[i] = Z[k]
            else:
                # はみ出したら伸ばしてく
                L = i
                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):
    Z = Z_Algorithm(S[i:])
    for j, z in enumerate(Z):
        ans = max(ans, min(z, j))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
S = input()
# 各文字を数値に変換しておく
S = [ord(s)-97 for s in S]

def bisearch_max(mn, mx, func):
    """ 条件を満たす最大値を見つける二分探索 """

    ok = mn
    ng = mx
    while ok+1 < ng:
        mid = (ok+ng) // 2
        if func(mid):
            # 上を探しに行く
            ok = mid
        else:
            # 下を探しに行く
            ng = mid
    return ok

class RollingHash:

    MOD = 2 ** 64
    b = 10 ** 8 + 7

    def __init__(self, S):
        self.len = len(S)
        self.pow = [1] * (self.len+1)
        for i in range(self.len):
            self.pow[i+1] = self.pow[i] * self.b
            self.pow[i+1] %= self.MOD
        # ハッシュの生成
        self.hash = [0] * (self.len+1)
        for i in range(self.len):
            self.hash[i+1] = self.hash[i] * self.b + S[i]
            self.hash[i+1] %= self.MOD
    
    # 区間[i,j)のハッシュ値を取得
    def get(self, l, r):
        return (self.hash[r] - self.hash[l] * self.pow[r-l]) % self.MOD

def calc(m):
    for i in range(N-m*2+1):
        a_hash = rh.get(i, i+m)
        for j in range(i+m, N-m+1):
            b_hash = rh.get(j, j+m)
            if a_hash == b_hash:
                return True
    return False

rh = RollingHash(S)
print(bisearch_max(0, N, calc))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
 
m = [[0] * n for _ in range(n)]
lcs = 0

for j in range(1, n):
    if s[j] == s[0]:
        m[0][j] = 1
        lcs = 1

for i in range(1, n-1):
    for j in range(i+1, n):
        if s[i] == s[j]:
            m[i][j] = min(m[i-1][j-1] + 1, j - i)
            lcs = max(m[i][j], lcs)
        else:
            m[i][j] = 0

print(lcs)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
S = input()
# 各文字を数値に変換しておく
S = [ord(s)-97 for s in S]

def bisearch_max(mn, mx, func):
    """ 条件を満たす最大値を見つける二分探索 """

    ok = mn
    ng = mx
    while ok+1 < ng:
        mid = (ok+ng) // 2
        if func(mid):
            # 上を探しに行く
            ok = mid
        else:
            # 下を探しに行く
            ng = mid
    return ok

class RollingHash:

    MOD = 2 ** 64
    b = 10 ** 8 + 7

    def __init__(self, S):
        self.len = len(S)
        self.pow = [1] * (self.len+1)
        for i in range(self.len):
            self.pow[i+1] = self.pow[i] * self.b
            self.pow[i+1] %= self.MOD
        # ハッシュの生成
        self.hash = [0] * (self.len+1)
        for i in range(self.len):
            self.hash[i+1] = self.hash[i] * self.b + S[i]
            self.hash[i+1] %= self.MOD
    
    # 区間[i,j)のハッシュ値を取得
    def get(self, l, r):
        return (self.hash[r] - self.hash[l] * self.pow[r-l]) % self.MOD

def calc(m):
    for i in range(N-m*2+1):
        for j in range(i+m, N-m+1):
            if rh.get(i, i+m) == rh.get(j, j+m):
                return True
    return False

rh = RollingHash(S)
print(bisearch_max(0, N, calc))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)

def main():
    n=int(input())
    s=input()
    pre=[set() for _ in range(26)]
    nx=[set() for _ in range(n)]
    oa=ord("a")
    for i in range(n-1,-1,-1):
        ci=ord(s[i])-oa
        nx[i]|=pre[ci]
        pre[ci].add(i)
    #print(pre)
    #print(nx)
    ans=0
    for i in range(n):
        for ii in nx[i]:
            for di in range(1,n):
                if (not ii+di in nx[i+di]) or (i+di==ii):
                    L=di
                    break
            ans=max(ans,L)
    print(ans)
main()

Submission status: Time Limit Exceeded

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)
    print(ans)

main()

Submission status: Time Limit Exceeded

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

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

for i in range(N):
    if S[i] == S[0]:
        dp[0][i] = 1
        dp[i][0] = 1
ans = 0
for i in range(1,N):
    for j in range(1,N):
        if S[i] == S[j]:
            dp[i][j] = dp[i-1][j-1]+1
        else:
            dp[i][j] = 0
        if abs(i-j) >= dp[i][j]:
            ans = max(ans, dp[i][j])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[34]:


import numpy as np
N = int(input())
S = input()
"""
5
ababa
2

13
strangeorange
5
"""


# In[41]:


dp = np.zeros((N+1, N+1), dtype=np.uint32)


# In[43]:


max_cont = 0
for i in range(N)[::-1]:
    for j in range(i+1, N)[::-1]:
        if S[i] == S[j]:
            dp[i,j] = min(dp[i+1, j+1]+1, j-i)
            max_cont = max(max_cont, dp[i, j])
        else:
            continue


# In[44]:


print(max_cont)


# In[ ]:

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[20]:


N = int(input())
S = input()
"""
5
ababa
2

13
strangeorange
5
"""


# In[29]:


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


# In[30]:


max_cont = 0
for i in range(N)[::-1]:
    for j in range(i+1, N)[::-1]:
        if S[i] == S[j]:
            dp[i][j] = min(dp[i+1][j+1]+1, j-i)
            max_cont = max(max_cont, dp[i][j])
        else:
            continue


# In[31]:


print(max_cont)


# In[ ]:

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[20]:


N = int(input())
S = input()
"""
5
ababa
2

13
strangeorange
5
"""


# In[25]:


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


# In[26]:


max_cont = 0
for i in range(N)[::-1]:
    for j in range(N)[::-1]:
        if i < j:
            if S[i] == S[j]:
                dp[i][j] = min(dp[i+1][j+1]+1, j-i)
                max_cont = max(max_cont, dp[i][j])
            else:
                continue
        else:
            continue


# In[27]:


print(max_cont)


# In[ ]: