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:
def Zalgorithm(s):
    z = [0 for _ in range(len(s))]
    z[0] = len(s)
    i, j = 1, 0
    while i < len(s):
        while i+j < len(s) and s[j] == s[i+j]:
            j += 1
        z[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < len(s) and k+z[k] < j:
            z[i+k] = z[k]
            k += 1
        i += k
        j -= k
    return z

n = int(input())
s = input().strip()
ans = 0
for i in range(len(s)):
    zarr = Zalgorithm(s[i:])
    for j in range(len(zarr)):
        ans = max(ans, min(j, zarr[j]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import Counter
n = int(input())
s = input()
count = 0
for le in range(1, n-1):
    mojiretu = Counter()
    for i in range(n-le+1):
        j = i+le
        if 0 < mojiretu[s[i:j]] <= i:
            count = le
            break
        else:
            mojiretu[s[i:j]] = j
print(count)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
n=int(input())
s=input()
count=0
for le in range(1,n-1):
    mojiretu=defaultdict(int)
    for i in range(n-le+1):
        j=i+le
        if 0<mojiretu[s[i:j]]<=i:
            count=max(count,le)
            break
        else:mojiretu[s[i:j]]=j
print(count)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
n=int(input())
s=input()
count=0
for le in range(1,n-1):
    mojiretu=defaultdict(int)
    for i in range(n-le+1):
        j=i+le
        if mojiretu[s[i:j]]:
            if mojiretu[s[i:j]]<=i:
                count=max(count,j-i)
        else:mojiretu[s[i:j]]=j
# while True:
#     for i in range(n)
print(count)

Submission status: Time Limit Exceeded

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

def KMPSearch(pat, txt): 
    M = len(pat) 
    N = len(txt) 
  
    # create lps[] that will hold the longest prefix suffix  
    # values for pattern 
    lps = [0]*M 
    j = 0 # index for pat[] 

    ans = []

  
    # Preprocess the pattern (calculate lps[] array) 
    computeLPSArray(pat, M, lps) 
  
    i = 0 # index for txt[] 
    while i < N: 
        if pat[j] == txt[i]: 
            i += 1
            j += 1
  
        if j == M: 
            ans.append(i-j)
            j = lps[j-1] 
  
        # mismatch after j matches 
        elif i < N and pat[j] != txt[i]: 
            # Do not match lps[0..lps[j-1]] characters, 
            # they will match anyway 
            if j != 0: 
                j = lps[j-1] 
            else: 
                i += 1
    return ans
  
def computeLPSArray(pat, M, lps): 
    len = 0 # length of the previous longest prefix suffix 
  
    lps[0] # lps[0] is always 0 
    i = 1
  
    # the loop calculates lps[i] for i = 1 to M-1 
    while i < M: 
        if pat[i]== pat[len]: 
            len += 1
            lps[i] = len
            i += 1
        else: 
            # This is tricky. Consider the example. 
            # AAACAAAA and i = 7. The idea is similar  
            # to search step. 
            if len != 0: 
                len = lps[len-1] 
  
                # Also, note that we do not increment i here 
            else: 
                lps[i] = 0
                i += 1

def has_k(k):
    for i in range(N-k+1):
        pat = S[i:i+k]
        idx = KMPSearch(pat,S)
        if len(idx) >- 2 and idx[0] + k <= idx[-1]:
            return True
    return False

ans = 0
jump = N
while jump > 0:
    while ans + jump <= N//2 and has_k(ans+jump):
        ans+=jump
    jump //= 2

print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(N//2):
  for j in range(i+1, N):
#    print(i,j,S[j:],S[i:j],end = "")
    if S[i:j] in S[j:]:
      ans = max(ans, j-i)
print(ans)

Submission status: Time Limit Exceeded

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


    def check(l):
        if l == 0:
            return True
        for i in range(n-l*2+1):
            for j in range(i+l, n-l+1):
                cnt = 0
                for k in range(l):
                    if s[i+k] == s[j+k]:
                        cnt += 1
                    else:
                        break

                if cnt == l:
                    # print(l, i, j, cnt,)
                    return True

        return False


    lb = 0
    ub = n // 2 + 1
    # for i in range(ub+1):
    #     print(i, check(i))

    while ub - lb > 1:
        mid = (ub + lb) // 2
        if check(mid):
            lb = mid
        else:
            ub = mid

    print(lb)

main()

Submission status: Time Limit Exceeded

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

dp = [[0] * (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 = input()

ans = 0
for i in range(N-1):
    for j in range(i+1, N):
        if S[i] == S[j]:
            if i != 0:
                if S[i-1] == S[j-1]:
                    continue
            equal = 1
            for k in range(1, min(j-i, N-j)):
                if S[i+k] == S[j+k]:
                    equal += 1
                else:
                    break
            ans = max(ans, equal)

print(ans)

Submission status: Time Limit Exceeded

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

hantei = False
ans = 0

isleft = True
kosu_original = N//4
for i in range(N-kosu_original+1):
    temp = S[i:i+kosu_original]
    # print("比較する文字列1:", temp)
    # print("比較する文字列2:",S[0:i] + "|" + S[i+kosu_original:],"\n")
    if temp in S[0:i] + "|" + S[i+kosu_original:]:
        # print("Trueの時\n-----------------")
        ans = kosu_original
        isleft = False
        break

if isleft:
    for kosu in range(kosu_original-1, 0, -1):
        if hantei:
            break

        for i in range(N-kosu+1):
            if hantei:
                break
            else:
                temp = S[i:i+kosu]
                # print("比較する文字列1:", temp)
                # print("比較する文字列2:",S[0:i] + "|" + S[i+kosu:],"\n")
            if temp in S[0:i] + "|" + S[i+kosu:]:
                # print("Trueの時\n-----------------")
                ans = kosu
                hantei = True
                break
else:
    for kosu in range(N//2, kosu_original, -1):
        if hantei:
            break

        for i in range(N-kosu+1):
            if hantei:
                break
            else:
                temp = S[i:i+kosu]
                # print("比較する文字列1:", temp)
                # print("比較する文字列2:",S[0:i] + "|" + S[i+kosu:],"\n")
            if temp in S[0:i] + "|" + S[i+kosu:]:
                # print("Trueの時\n-----------------")
                ans = kosu
                hantei = True
                break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
St = []
for i in range(N):
  St += [ord(S[i])-97]
  
St.reverse()
ans = 0
#初期化
dp=[[0 for i in range(N+1)] for j in range(N+1)]

#DP:dp[i][j] Sのi文字目以降とj文字目以降の最大マッチング
for i in range(N):
  for j in range(i):
    if (St[i] == St[j]): 
      dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1)
      ans = max(ans, min(dp[i+1][j+1], i-j))
    if i-j <= dp[i+1][j+1]:
      break
      
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
St = []
for i in range(N):
  St += [ord(S[i])-97]
  
#初期化
dp=[[0 for i in range(N+1)] for j in range(N+1)]

ans = 0
#DP:dp[i][j] Sのi文字目以降とj文字目以降の最大マッチング
for i in range(N-1,-1,-1):
  for j in range(N-1, i-1, -1):
    if (St[i] == St[j]): 
      dp[i][j] = max(dp[i][j], dp[i+1][j+1] + 1)
      ans = max(ans, min(dp[i][j], j-i))
    if j-i <= dp[i][j]:
      break
      
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
St = []
for i in range(N):
  St += [ord(S[i])-97]
  
#初期化
dp=[[0 for i in range(N+1)] for j in range(N+1)]

ans = 0
#DP:dp[i][j] Sのi文字目以降とj文字目以降の最大マッチング
for i in range(N-1,-1,-1):
  for j in range(N-1, i-1, -1):
    if (St[i] == St[j]): 
      dp[i][j] = max(dp[i][j], dp[i+1][j+1] + 1)
      ans = max(ans, min(dp[i][j], j-i))
      
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
St = []
for i in range(N):
  St += [ord(S[i])-97]
  
#初期化
dp=[[0 for i in range(N+1)] for j in range(N+1)]

ans = 0
#DP:dp[i][j] Sのi文字目以降とj文字目以降の最大マッチング
for i in range(N-1,-1,-1):
  for j in range(N-1, i-1, -1):
    if (S[i] == S[j]): 
      dp[i][j] = max(dp[i][j], dp[i+1][j+1] + 1);
      ans = max(ans, min(dp[i][j], j-i));
      
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
St = []
for i in range(N):
  St += [ord(S[i])-97]
  
St.reverse()
#初期化
dp=[[0 for i in range(N+1)] for j in range(N+1)]

#DP:dp[i][j] Sのi文字目以降とj文字目以降の最大マッチング
for i in range(N):
  for j in range(i):
    dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1])
    if St[i] == St[j] :
      dp[i+1][j+1] = min(max(dp[i+1][j+1], dp[i][j]+1), i-j)
      
print(max(sum(dp, [])))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input().strip()
assert n == len(s)

maxlen = 0
for offset in range(1, n):
  t = s[offset:]
  d = 0
  for (a, b) in zip(s, t):
    if a == b:
      d += 1
    else:
      d = 0
    if maxlen < d and d <= offset:  # (d > offset) のとき共通部分文字列が重なってる
      maxlen = d

print(maxlen)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
St = []
for i in range(N):
  St += [ord(S[i])-97]
  
#初期化
dp=[[0 for i in range(N+1)] for j in range(N+1)]

#DP:dp[i][j] Sのi文字目以降とj文字目以降の最大マッチング
for i in range(N-1,-1,-1):
  for j in range(N-1, i-1, -1):
    dp[i][j] = max(dp[i][j+1],dp[i+1][j])
    if St[i] == St[j]:
      dp[i][j] = min(max(dp[i][j], dp[i+1][j+1]+1), j-i)
      
print(max(sum(dp, [])))

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

# ローリングハッシュで一致する文字列があるか確認
def rolling_hash_search(S, T):

    ans = []
    slen = len(S)
    tlen = len(T)
    # 例外処理
    if slen < tlen:
        return False
    MOD = 2 ** 64
    b = 10 ** 8 + 7
    a = 1
    for i in range(tlen):
        a *= b
        a %= MOD
    
    # 先頭のローリングハッシュ
    s_hash = 0
    for i in range(tlen):
        s_hash = s_hash * b + S[i]
        s_hash %= MOD
    t_hash = 0
    for i in range(tlen):
        t_hash = t_hash * b + T[i]
        t_hash %= MOD
    
    # Sの始点を1つずつ進めながらハッシュ値をチェック
    for i in range(slen-tlen+1):
        if s_hash == t_hash:
            return True
        if i+tlen < slen:
            s_hash = s_hash * b - S[i] * a + S[tlen+i]
            s_hash %= MOD
    return False

def calc(m):
    for i in range(N-m*2+1):
        S1 = S[i:i+m]
        S2 = S[i+m:]
        # 文字列S2に文字列S1が含まれているか
        if rolling_hash_search(S2, S1):
            return True
    return False

print(bisearch_max(0, N, calc))

Submission status: Time Limit Exceeded

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

#初期化
dp=[[0 for i in range(N+1)] for j in range(N+1)]

#DP:dp[i][j] Sのi文字目以降とj文字目以降の最大マッチング
for i in range(N-1,-1,-1):
  for j in range(N-1, i-1, -1):
    dp[i][j] = max(dp[i][j+1],dp[i+1][j])
    if St[i] == St[j]:
      dp[i][j] = min(max(dp[i][j], dp[i+1][j+1]+1),j-i)
      
ans = 0
for i in range(N+1):
  ans = max(ans, max(dp[i]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
dp=[[0]*n for _ in range(n)]
ans=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]=dp[i+1][j+1]+(i+1+dp[i+1][j+1]!=j+1) if j<n-1 else 1
    ans=max(ans,max(dp[i]))
print(ans)

Submission status: Time Limit Exceeded

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

#初期化
dp=[[0 for i in range(N+1)] for j in range(N+1)]

#DP:dp[i][j] Sのi文字目以降とj文字目以降の最大マッチング
for i in range(N-1,-1,-1):
  for j in range(N-1, i-1, -1):
    dp[i][j] = max(dp[i][j+1],dp[i+1][j])
    if St[i] == St[j]:
      dp[i][j] = min(max(dp[i][j], dp[i+1][j+1]+1),j-i)
      

print(max(sum(dp, [])))

Submission status: Time Limit Exceeded

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

algo = []
for i in range(n):
    algo.extend(z_algo(s[i:n])[1:])

ans = 0
for i in range(n):
    if n//2-i in algo:
        ans = n//2-i
        break
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()

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

# ローリングハッシュで一致する文字列があるか確認
def rolling_hash_search(S, T):

    ans = []
    slen = len(S)
    tlen = len(T)
    # 例外処理
    if slen < tlen:
        return False
    MOD = 2 ** 64
    b = 10 ** 8 + 7
    a = 1
    for i in range(tlen):
        a *= b
        a %= MOD
    
    # 先頭のローリングハッシュ
    s_hash = 0
    for i in range(tlen):
        s_hash = s_hash * b + ord(S[i])
        s_hash %= MOD
    t_hash = 0
    for i in range(tlen):
        t_hash = t_hash * b + ord(T[i])
        t_hash %= MOD
    
    # Sの始点を1つずつ進めながらハッシュ値をチェック
    for i in range(slen-tlen+1):
        if s_hash == t_hash:
            return True
        if i+tlen < slen:
            s_hash = s_hash * b - ord(S[i]) * a + ord(S[tlen+i])
            s_hash %= MOD
    return False

def calc(m):
    for i in range(N-m*2+1):
        S1 = S[i:i+m]
        S2 = S[i+m:]
        # 文字列S2に文字列S1が含まれているか
        if rolling_hash_search(S2, S1):
            return True
    return False

print(bisearch_max(0, N, calc))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
l=0
r=n//2
while r-l>=1:
    m=(r+l+1)//2
    list=[]
    flg=False
    for i in range(n-m+1):
        t=s[i:i+m]
        if t in list:
            if t in s[:i]:
                flg=True
                break
        else:
            list.append(t)
    if flg:
        l=m
    else:
        r=m-1
print(l)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
l=0
r=n//2
while r-l>=1:
    m=(r+l+1)//2
    list=[]
    flg=False
    for i in range(n-m+1):
        t=s[i:i+m]
        if t in list:
            if t in s[s.index(t)+m:]:
                flg=True
                break
        else:
            list.append(t)
    if flg:
        l=m
    else:
        r=m-1
print(l)

Submission status: Time Limit Exceeded

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

def mojicount(s,n):
    moji = []
    kaisuu = []
    basho = []
    for i in range(len(s)-n+1):
        if s[i:i+n] not in moji:
            moji.append(s[i:i+n])
            kaisuu.append(1)
            basho.append([i])
        else:
            for j in range(len(moji)):
                if s[i:i+n] == moji[j]:
                    kaisuu[j] += 1
                    basho[j].append(i)
                    break
    p = 0
    for i in range(len(basho)):
        if max(basho[i]) - min(basho[i]) + 1 > n:
            p += 1
            break
    if p >= 1:
        return(n)
    else:
        return(0)
        
for i in range(N//2):
    ans = mojicount(S,N//2-i)
    if ans != 0:
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
 
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
 
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return sys.stdin.readline()[:-1]
 
def main():
    n = II()
    s = S()
    inf = n + 2
    m = [[0 for i in range(n)] for i in range(n)]
    first = [[inf for i in range(n)] for i in range(n)]
    # set 1st index value
    lcs = 0
    for i, c in enumerate(s):
        # print(c, s[0])
        if c == s[0]:
            m[i][0] = 1
            first[i][0] = i
            if i != 0:
                lcs = 1
    for i in range(1, n):
        for j in range(1, n):
            if i <= j:
                continue
            if s[i] == s[j]:
                if first[i-1][j-1] > j:
                    m[i][j] = m[i-1][j-1] + 1
                    lcs = max(m[i][j], lcs)
                    if first[i-1][j-1] == inf:
                        first[i][j] = i
                    else:
                        first[i][j] = first[i-1][j-1]
            else:
                m[i][j] = 0
 
    # print(m)
    print(lcs)
 
 
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

max_length = 0
for i in range(N):
    for j in range(N):
        if i < j:
            length = min(j - i, dp[i][j])
            max_length = max(length, max_length)

print(max_length)

Submission status: Time Limit Exceeded

Solution code:
n,s=open(0);a=i=j=0
while j<1e7:f=s[i:j]in s[j:];a=max(a,j*f-i);j+=f;i+=f^1
print(a)

Submission status: Time Limit Exceeded

Solution code:
n,s=open(0);a=i=j=0
while j<3e7:f=s[i:j]in s[j:];a=max(a,j*f-i);j+=f;i+=f^1
print(a)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
n,s=open(0)
n=int(n)
a=0
for i in range(n):
  t=0
  for v,w in zip(s,s[i:n]):
    t=-~t*(v==w)
    if t>i:break
    if t>a:a=t
print(a)

Submission status: Time Limit Exceeded

Solution code:
def z_algorithm(s):
    n = len(s)
    prefix = [0] * n
    j = 0
    ret = 0
    for i in range(1, n):
        if i + prefix[i - j] < j + prefix[j]:
            prefix[i] = prefix[i - j]
        else:
            k = max(0, j + prefix[j] - i)
            while i + k < n and s[k] == s[i + k]:
                k += 1
            prefix[i] = k
            ret = max(ret, min(i, k))
            j = i
    return ret


n = int(input())
s = input()
print(max(z_algorithm(s[i:]) for i in range(n - 1)))

Submission status: Time Limit Exceeded

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

dp = [[0 for j in range(N+10)] for i in range(N+10)]

for i in range(N-1, -1, -1):
    for j in range(N-1, -1, -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
        ans = max(ans, min(dp[i][j], j-i))

print(ans)

Submission status: Time Limit Exceeded

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

m = 0
for i in range(N):
  s = S[i:]
  Z = [0]
  c = 0
  for j in range(1, len(s)):
    if c > 0 and j + Z[j-c] < c + Z[c]:
      Z.append(Z[j-c])
    else:
      l = max(0, c+Z[c]-j)
      while l < j and j+l < len(s) and s[l] == s[j+l]:
        l += 1
      Z.append(l)
      c = j
  m = max(m, *Z)

print(m)

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

def rolling_hash_search(S, T):

    slen = len(S)
    tlen = len(T)
    b = 10 ** 8 + 7
    a = 1
    for i in range(tlen):
        a *= b
    
    s_hash = 0
    for i in range(tlen):
        s_hash = s_hash * b + ord(S[i])
    t_hash = 0
    for i in range(tlen):
        t_hash = t_hash * b + ord(T[i])
    
    for i in range(slen-tlen+1):
        if s_hash == t_hash:
            return True
        if i+tlen < slen:
            s_hash = s_hash * b - ord(S[i]) * a + ord(S[i+tlen])
    
    return False

def calc(m):
    for i in range(N-m*2+1):
        S1 = S[i:i+m]
        S2 = S[i+m:]
        # 文字列S2に文字列S1が含まれているか
        if rolling_hash_search(S2, S1):
            return True
    return False

print(bisearch_max(0, N, calc))

Submission status: Time Limit Exceeded

Solution code:
def strTint(s):
    return ord(s)-96

alpha = {}
for i in range(97,97+26):
    alpha[chr(i)] = i - 96

def main():
    N = int(input())
    S = input()
    #N = 5000
    #S = "a"*N
    import time
    star = time.time()
    
    b = 27
    mod1 = 10**9+7
    mod2 = 10**9+9
    D = {}
    for i in range(N):
        H = strTint(S[i])
        H1 = H%mod1
        #H2 = H%mod2
        if not H1 in D:
            D[H1] = [1,i,i]
        for j in range(i+1,min(i+N//2+2,N)):
            H1 = (H1*b + strTint(S[j]))%mod1
            if not H1 in D:
                D[H1] = [j-i+1,i,i]
            else:
                D[H1][-1] = i
    
    ans = 0
    for i in D:
        L = D[i][0]
        tmp = 0
        if D[i][1] + L <= D[i][-1] and ans < L:
            ans = L
    g = time.time()
    #print(g-star)
    print(ans)
    
main()

Submission status: Time Limit Exceeded

Solution code:
import collections
n=int(input())
s=input()
ans=0
d=collections.defaultdict(int)
for i in range(n):
  t=0
  for j in range(i,n):
    t+=(ord(s[j])-96)*(27**(j-i))
    if 0<d[t]<i and j-i+1>ans:
      ans=j-i+1
    elif d[t]==0 and i+2*(j-i+1)<=n:
      d[t]=j
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
n=int(input())
s=input()
ans=0
d=collections.defaultdict(int)
for i in range(n):
  t=0
  for j in range(i,n):
    t+=(ord(s[j])-96)*(100**(j-i))
    if 0<d[t]<i and j-i+1>ans:
      ans=j-i+1
    elif d[t]==0 and i+2*(j-i+1)<=n:
      d[t]=j
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def z_algorithm(s):
    n = len(s)
    prefix = [0] * n
    j = 0
    ret = 0
    for i in range(1, n):
        if i + prefix[i - j] < j + prefix[j]:
            prefix[i] = prefix[i - j]
        else:
            k = max(0, j + prefix[j] - i)
            while i + k < n and s[k] == s[i + k]:
                k += 1
            prefix[i] = k
            ret = min(i, k)
            j = i
    return ret


n = int(input())
s = input()
print(max(z_algorithm(s[i:]) for i in range(n - 1)))

Submission status: Time Limit Exceeded

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

max_length = 0

for i in range(N):
    for length in range(N - i):
        if S[i:i+length] in S[i+length:]:
            if length > max_length:
                max_length = length

print(max_length)

Submission status: Time Limit Exceeded

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


n = int(input())
s = input()
print(max(max(map(min, zip(range(n - i), z_algorithm(s[i:])))) for i in range(n - 1)))

Submission status: Time Limit Exceeded

Solution code:
def strTint(s):
    return ord(s)-96
def main():
    N = int(input())
    S = input()
    #N = 5000
    #S = "a"*N
    import time
    star = time.time()
    
    b = 27
    mod1 = 10**9+7
    mod2 = 10**9+9
    D = {}
    for i in range(N):
        H = strTint(S[i])
        H1 = H%mod1
        H2 = H%mod2
        if not (H1,H2) in D:
            D[(H1,H2)] = [1,i,i]
        for j in range(i+1,min(i+N//2+2,N)):
            H1 = (H1*b + strTint(S[j]))%mod1
            H2 = (H2*b + strTint(S[j]))%mod2
            if not (H1,H2) in D:
                D[(H1,H2)] = [j-i+1,i,i]
            else:
                D[(H1,H2)][-1] = i
    
    ans = 0
    for i in D:
        L = D[i][0]
        tmp = 0
        if D[i][1] + L <= D[i][-1] and ans < L:
            ans = L
    g = time.time()
    #print(g-star)
    print(ans)
    
main()

Submission status: Time Limit Exceeded

Solution code:
def e():
    n=int(input())
    s=input()
    ans=0

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


print(e())

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(n):
  for j in range(i, n):
    if s[i:j+1] in s[j+1:]:
      ans = max(ans, len(s[i:j+1]))
    else:
      break
print(ans)

Submission status: Time Limit Exceeded

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

lenS = len(s)
#print(lenS)
ans = 0
tempAns = 0
for i in reversed(range(1,lenS//2+1)):
	for j in range(0,n-i+1):
		tempS1 = s[j:j+i]
		#print(tempS)
		tempS2 = s[j+i:]
		if (tempS1 in tempS2):
			ans = i
			break
			#print(s[j+i+k-1:j+2*i+k-1], i, j, k)
	if (ans > 0):
		break
print(ans)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
def z_arr(s):
    """An advanced computation of Z-values of a string."""
    # From https://ivanyu.me/blog/2013/10/15/z-algorithm/
 
    Z = [0] * len(s)
    Z[0] = len(s)
 
    rt = 0
    lt = 0
 
    for k in range(1, len(s)):
        if k > rt:
            # If k is outside the current Z-box, do naive computation.
            n = 0
            while n + k < len(s) and s[n] == s[n+k]:
                n += 1
            Z[k] = n
            if n > 0:
                lt = k
                rt = k+n-1
        else:
            # If k is inside the current Z-box, consider two cases.
 
            p = k - lt  # Pair index.
            right_part_len = rt - k + 1
 
            if Z[p] < right_part_len:
                Z[k] = Z[p]
            else:
                i = rt + 1
                while i < len(s) and s[i] == s[i - k]:
                    i += 1
                Z[k] = i - k
 
                lt = k
                rt = i - 1
    return Z
 
if __name__=="__main__":
    n=int(input())
    s=input()
    ans=0
    for i in range(len(s)):
        A=z_arr(s[i:])
        for a in range(len(A)):
            if A[a]<=a:
                ans=max(ans, A[a])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:


def calc(s):
    max_n = 0
    for i in range(1, len(s)):
        count = 0
        for n in range(0, i):
            # n <=> i+n
            if i+n >= len(s):
                break
            c1 = s[n]
            c2 = s[i+n]

            # print("%d,%d" % (n, i+n))
            # print("%s, %s" % (c1, c2))
            if c1 == c2:
                count += 1
            else:
                break
        if max_n < count:
            max_n = count
    return max_n


_ = input()
str = input()

max = 0
for i in range(len(str)):
    n = calc(str[i:len(str)])
    if max < n:
        max = n

print(max)