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:
n = int(input())
s = input()
l = [[] for i in range(n+1)]
l[0] = ['0',0]
ans = 0
for i in range(1,n+1):
    l[i] = [s[i-1:],i]
l.sort()
for i in range(n):
    for j in range(i+1,n):
        m = min(len(l[i][0]),len(l[j][0]))
        x = l[i][0]
        y = l[j][0]
        z = 0
        while z < m:
            if x[z] != y[z]:
                break
            z += 1
        if z > l[i][1] - l[j][1]:
            z = l[i][1] - l[j][1]
        ans = max(z,ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)

class DoubleRollingHash:
    def __init__(self, seq, f=ord):
        self.n = len(seq)
        self.base1, self.base2 = 1007, 2009
        self.mod1, self.mod2 = 1000000007, 1000000009
        self.f = f # set numerizing function

        self.hash1, self.hash2 = [0]*(self.n+1), [0]*(self.n+1)
        self.power1, self.power2 = [1]*(self.n+1), [1]*(self.n+1)

        for i, e in enumerate(seq):
            self.hash1[i+1] = (self.hash1[i] * self.base1 + self.f(e)) % self.mod1
            self.hash2[i+1] = (self.hash2[i] * self.base2 + self.f(e)) % self.mod2
            self.power1[i+1] = (self.power1[i] * self.base1) % self.mod1
            self.power2[i+1] = (self.power2[i] * self.base2) % self.mod2

    # get hash value of seq[left:right]
    def get(self, l, r):
        v1 = (self.hash1[r] - self.hash1[l] * self.power1[r-l]) % self.mod1
        v2 = (self.hash2[r] - self.hash2[l] * self.power2[r-l]) % self.mod2
        return v1, v2

    # get lcp of seq[a:] and seq[b:]
    def getLCP(self, a, b):
        l = self.n - max(a, b) + 1
        left, right = 0, l
        while right - left > 1:
            mid = (left + right) // 2
            if self.get(a, a+mid) == self.get(b, b+mid): left = mid
            else: right = mid
        return left

class RollingHash:
    def __init__(self, seq, f=ord):
        self.n = len(seq)
        self.base, self.mod = 1007, pow(2, 61) - 1
        self.f = f # set numerizing function
        self.hash, self.power = [0]*(self.n+1), [1]*(self.n+1)
        for i, e in enumerate(seq):
            self.hash[i+1] = (self.hash[i] * self.base + self.f(e)) % self.mod
            self.power[i+1] = (self.power[i] * self.base) % self.mod

    # get hash value of seq[left:right]
    def get(self, l, r): return (self.hash[r] - self.hash[l] * self.power[r-l]) % self.mod

    # get lcp of seq[a:] and seq[b:]
    def getLCP(self, a, b):
        l = self.n - max(a, b) + 1
        left, right = 0, l
        while right - left > 1:
            mid = (left + right) // 2
            if self.get(a, a+mid) == self.get(b, b+mid): left = mid
            else: right = mid
        return left


# def main():
#     N = I()
#     S = SL()

#     rh = RollingHash(S)
#     ans = 0

#     def check(m):
#         d = defaultdict(lambda: -1)
#         for i in range(N-m+1):
#             v = rh.get(i, i+m)
#             if d[v] != -1:
#                 if i >= d[v] + m:
#                     return True
#             else:
#                 d[v] = i
#         return False

#     left, right = 0, N//2+1
#     while right - left > 1:
#         mid = (left + right) // 2
#         if check(mid): left = mid
#         else: right = mid

#     print(left)

def main():
    N = I()
    S = SL()

    rh = RollingHash(S)
    ans = 0

    for i in range(N):
        for j in range(i+1, N):
            ans = max(ans, min(rh.getLCP(i, j), j - i))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)

class DoubleRollingHash:
    def __init__(self, seq, f=ord):
        self.n = len(seq)
        self.base1, self.base2 = 1007, 2009
        self.mod1, self.mod2 = 1000000007, 1000000009
        self.f = f # set numerizing function

        self.hash1, self.hash2 = [0]*(self.n+1), [0]*(self.n+1)
        self.power1, self.power2 = [1]*(self.n+1), [1]*(self.n+1)

        for i, e in enumerate(seq):
            self.hash1[i+1] = (self.hash1[i] * self.base1 + self.f(e)) % self.mod1
            self.hash2[i+1] = (self.hash2[i] * self.base2 + self.f(e)) % self.mod2
            self.power1[i+1] = (self.power1[i] * self.base1) % self.mod1
            self.power2[i+1] = (self.power2[i] * self.base2) % self.mod2

    # get hash value of seq[left:right]
    def get(self, l, r):
        v1 = (self.hash1[r] - self.hash1[l] * self.power1[r-l]) % self.mod1
        v2 = (self.hash2[r] - self.hash2[l] * self.power2[r-l]) % self.mod2
        return v1, v2

    # get lcp of seq[a:] and seq[b:]
    def getLCP(self, a, b):
        l = self.n - max(a, b) + 1
        left, right = 0, l
        while right - left > 1:
            mid = (left + right) // 2
            if self.get(a, a+mid) == self.get(b, b+mid): left = mid
            else: right = mid
        return left

class RollingHash:
    def __init__(self, seq, f=ord):
        self.n = len(seq)
        self.base, self.mod = 1007, pow(2, 61) - 1
        self.f = f # set numerizing function
        self.hash, self.power = [0]*(self.n+1), [1]*(self.n+1)
        for i, e in enumerate(seq):
            self.hash[i+1] = (self.hash[i] * self.base + self.f(e)) % self.mod
            self.power[i+1] = (self.power[i] * self.base) % self.mod

    # get hash value of seq[left:right]
    def get(self, l, r): return (self.hash[r] - self.hash[l] * self.power[r-l]) % self.mod

    # get lcp of seq[a:] and seq[b:]
    def getLCP(self, a, b):
        l = self.n - max(a, b) + 1
        left, right = 0, l
        while right - left > 1:
            mid = (left + right) // 2
            if self.get(a, a+mid) == self.get(b, b+mid): left = mid
            else: right = mid
        return left

class ZAlgo:
    def __init__(self, seq):
        self.n = len(seq)
        # seq 自身と seq[i:] とが、先頭から最大で何文字一致しているか
        self.lcp = [0] * self.n
        self.lcp[0] = self.n
        i, j = 1, 0
        while i < self.n:
            while i + j < self.n and seq[j] == seq[i+j]:
                j += 1
            self.lcp[i] = j
            if j == 0:
                i += 1
                continue

            k = 1
            while i + k < self.n and k + self.lcp[k] < j:
                self.lcp[i + k] = self.lcp[k]
                k += 1
            i += k
            j -= k

    # seq[0:]とseq[i:]のLCP
    def getLCP(self, i): return self.lcp[i]

def main():
    N = I()
    S = SL()

    ans = 0

    for i in range(N):
        z = ZAlgo(S[i:])
        for j in range(N-i):
            ans = max(ans, min(z.getLCP(j), j))

    print(ans)





# def main():
#     N = I()
#     S = SL()

#     rh = RollingHash(S)
#     ans = 0

#     def check(m):
#         d = defaultdict(lambda: -1)
#         for i in range(N-m+1):
#             v = rh.get(i, i+m)
#             if d[v] != -1:
#                 if i >= d[v] + m:
#                     return True
#             else:
#                 d[v] = i
#         return False

#     left, right = 0, N//2+1
#     while right - left > 1:
#         mid = (left + right) // 2
#         if check(mid): left = mid
#         else: right = mid

#     print(left)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)

class RollingHash:
    def __init__(self, seq, f=ord):
        self.n = len(seq)
        self.base1, self.base2 = 1007, 2009
        self.mod1, self.mod2 = 1000000007, 1000000009
        self.f = f # set numerizing function

        self.hash1, self.hash2 = [0]*(self.n+1), [0]*(self.n+1)
        self.power1, self.power2 = [1]*(self.n+1), [1]*(self.n+1)

        for i, e in enumerate(seq):
            self.hash1[i+1] = (self.hash1[i] * self.base1 + self.f(e)) % self.mod1
            self.hash2[i+1] = (self.hash2[i] * self.base2 + self.f(e)) % self.mod2
            self.power1[i+1] = (self.power1[i] * self.base1) % self.mod1
            self.power2[i+1] = (self.power2[i] * self.base2) % self.mod2

    # get hash value of seq[left:right]
    def get(self, l, r):
        v1 = (self.hash1[r] - self.hash1[l] * self.power1[r-l]) % self.mod1
        v2 = (self.hash2[r] - self.hash2[l] * self.power2[r-l]) % self.mod2
        return v1, v2

    # get lcp of S[a:] and T[b:]
    def getLCP(self, a, b):
        l = self.n - max(a, b) + 1
        left, right = 0, l
        while right - left > 1:
            mid = (left + right) // 2
            if self.get(a, a+mid) == self.get(b, b+mid): left = mid
            else: right = mid
        return left


def main():
    N = I()
    S = SL()

    rh = RollingHash(S)
    ans = 0

    for i in range(N):
        for j in range(i+1, N):
            ans = max(ans, min(rh.getLCP(i, j), j - i))

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
"""
連続する部分文字列の種類は多くてN**2個ある。
N<=5000という制約から考えて、これらの連続する部分文字列に対して全探索ができる。
問題は、各部分文字列が条件を満たしているかどうかをどうやって調べるかだ。
これは、各部分文字列種ごとにどの区間で出現するかをメモしておけば良い。
dic["hogehoge"] => "hogehoge"という連続部分文字列が出現する区間をメモした配列
dic["hogehoge"] = [(0,7),(2,9),(6,13),(10,17)]　といった具合だ。
dic[hogehoge][x][1]とdic[hogehoge][x+1][1]が重複しているかを調べることで条件を満たすかどうかを判定できる。
区間(i,j)のjで昇順並びになっている必要があるが、実直にi,jでループして連続部分文字列を探索すれば、自然と昇順でメモされる。
計算量はO(N**2)で間に合う。
"""
N = int(input())
S = tuple(input())

dic = {}
#ここがTLEの原因になっている。
for i in range(N):
    for j in range(N):
        if S[i:j+1] not in dic:
            dic[S[i:j+1]] = []
        dic[S[i:j+1]].append((i,j))

ans = 0
for k,v in dic.items():
    if len(v) > 1:
        for i in range(1,len(v)):
            if v[i][0]<=v[i-1][1]:
                break
        else:
            ans = max(ans,len(k))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def Z_algorithm(s):
    n = len(s)
    Z = [0] * n  # z[i] = sum(s[0::n - i], s[i::n])
    Z[0] = n
    i, j = 1, 0
    while i < n:
        # 共通部分を見つけるパート
        while i + j < n and s[j] == s[i + j]:
            j += 1
        Z[i] = j

        if j == 0:
            i += 1
            continue
        # 計算の再利用パート
        # k + Z[k] < j なら再利用できる
        k = 1
        while k < j and k + Z[k] < j:
            Z[i + k] = Z[k]
            k += 1
        # k個先まで見たのでk個先にバトンを渡す
        i += k
        j -= k
    return Z


n, s = int(input()), input()
print(max((np.minimum(Z_algorithm(s[i:]), range(n - i))).max() for i in range(n)))

Submission status: Time Limit Exceeded

Solution code:
def Z_Algorithm(S):
    N = len(S)
    Z = [0]*N
    Z[0] = N
    
    i = 1   #左
    j = 0   #差分

    while i < N:
        while i + j < N and S[j] == S[j + i]:
            j += 1
        Z[i] = j

        if j == 0:
            i += 1
            continue

        k = 1   # 差分
        while k < j and k + Z[k] < j:
            Z[i + k] = Z[k]
            k += 1
        
        i += k
        j -= k
    
    return Z

def calc(S):
    N = len(S)
    Z = Z_Algorithm(S)

    res = 0
    for i in range(N):
        res = max(res, min(Z[i], i))
    
    return res

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

res = 0

for i in range(N):
    res = max(res, calc(S[i:]))

print(res)

Submission status: Time Limit Exceeded

Solution code:
n, s = int(input()), input()
dp = [0] * (n + 1)
ans = 0
for i in range(n):
    for j in range(n - 1, i, -1):
        if s[i] == s[j]:
            dp[j + 1] = min(dp[j] + 1, j - i)
        else:
          dp[j + 1] = 0
    ans = max(max(dp), ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

class RollingHash():
    def __init__(self, s, base1=1007, base2=2009, mod1=10**9+7, mod2=10**9+9):
        self.mod1 = mod1
        self.mod2 = mod2
        self.s = s
        n = len(s)
        self.hash1 = [0]*(n+1)
        self.pow1 = [1]*(n+1)
        self.hash2 = [0]*(n+1)
        self.pow2 = [1]*(n+1)
        for i in range(n):
            self.hash1[i+1] = (self.hash1[i]*base1 + ord(s[i])) % self.mod1
            self.pow1[i+1] = (self.pow1[i]*base1) % self.mod1
            self.hash2[i+1] = (self.hash2[i]*base2 + ord(s[i])) % self.mod2
            self.pow2[i+1] = (self.pow2[i]*base2) % self.mod2

    def get(self, l, r):
        h1 = (self.hash1[r] - self.hash1[l] * self.pow1[r-l]) % self.mod1
        h2 = (self.hash2[r] - self.hash2[l] * self.pow2[r-l]) % self.mod2
        return (h1,h2)


n = int(input())
s = input()
rh = RollingHash(s, base1=3**6, base2=3**7, mod1=2**61-1, mod2=2**61-1)

for len_ in range(n//2,0,-1):
    ql = [(-1,-1)]*(len_-1)
    wait_q = deque(ql)
    hset = set()
    # print(len_)
    for i in range(n-len_+1):
        # print(s[i:i+len_])
        hs = rh.get(i,i+len_)
        if hs in hset:
            print(len_)
            exit()
        else:
            wait_q.append(hs)
            hset.add(wait_q.popleft())
        # print(wait_q)
        # print(hset)

else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
mx=0
for i in range(1,n):
  c=0
  for j in range(n-i):
    if s[j]==s[j+i]:
      c+=1
      mx=max(mx,c)
      if c==i:
        break
    else:
      c=0
print(mx)

Submission status: Time Limit Exceeded

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

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

for i in reversed(range(n)):
    for j in reversed(range(n)):
        if s[i] == s[j]:
            dp[i][j] = dp[i+1][j+1]+1


ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        x = min(dp[i][j], j-i)
        if ans < x:
            ans = x
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def lcs(s1, s2):
  dp=[]
  for s2_k in s2:
    bgn_idx=0
    for i, cur_idx in enumerate(dp):
      chr_idx=s1.find(s2_k,bgn_idx)+1
      if not chr_idx:break
      dp[i]=min(cur_idx,chr_idx)
      bgn_idx=cur_idx
    else:
      chr_idx=s1.find(s2_k,bgn_idx)+1
      if chr_idx:dp.append(chr_idx)
  return len(dp)

n=int(input())
s=input()
l=0
for i in range(n):
  l=max(lcs(s[:i],s[i:]),l)
print(l)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
#import numba
#@numba.jit
def solve(n,s):
    dp=np.zeros((n+1,n+1),dtype=np.int16)
    for i in range(n):
        for j in range(i+1,n):
            if s[i]==s[j]:
                if dp[i][j]<j-i:
                    dp[i+1][j+1]=dp[i][j]+1
    print(np.amax(dp))
n=int(input())
s=np.array([ord(i) for i in input()])
solve(n,s)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import numba
@numba.jit
def solve(n,s):
    dp=np.zeros((n+1,n+1),dtype=np.int16)
    for i in range(n):
        for j in range(i+1,n):
            if s[i]==s[j]:
                if dp[i][j]<j-i:
                    dp[i+1][j+1]=dp[i][j]+1
    print(np.amax(dp))
n=int(input())
s=input()
solve(n,s)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import numba
@numba.jit
def solve(n,s):
    dp=np.zeros((n+1,n+1),dtype=int)
    for i in range(n):
        for j in range(i+1,n):
            if s[i]==s[j]:
                if dp[i][j]<j-i:
                    dp[i+1][j+1]=dp[i][j]+1
    print(np.amax(dp))
n=int(input())
s=input()
solve(n,s)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n=int(input())
s=input()
dp=np.zeros((n+1,n+1),dtype=int)
for i in range(n):
    for j in range(i+1,n):
        if s[i]==s[j]:
            if dp[i][j]<j-i:
                dp[i+1][j+1]=dp[i][j]+1
print(np.amax(dp))

Submission status: Time Limit Exceeded

Solution code:
def main():
    n=int(input())
    s=input()
    dp=[(n+1)*[0]for _ in range(n+1)]
    ans=0
    for i in range(1,n):
        for j in range(i+1,n+1):
            if s[i-1]==s[j-1]:
                dp[i][j]=min(dp[i-1][j-1]+1,j-i)
                ans=max(ans,dp[i][j])
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
s = input()
### ローリングハッシュ rolling hash
import random
# M = 10**9+7
# M = 1<<63 - 1
# M = 9007199254740997
M = 92709568269121

b = random.choice(range(1,M))
def rhash_list(s):
    l = [chr(v) for v in range(ord("a"), ord("z")+1)]
    d = {c:i+2 for i,c in enumerate(l)}
    ans = 0
    v = 1
    l = [0]
    for item in s:
        ans += d[item]*v
        v *= b
        ans %= M
        v %= M
        l.append(ans)
    return l
l = rhash_list(s)
if len(set(s))==n:
    ans = 0
else:
    binv = pow(b,M-2,M)
    pows = [None]*(n+1)
    v = 1
    for j in range(n+1):
        pows[j] = v
        v *= binv
        v%= M
#         pow(binv,j,M)
    ans = 0
    from collections import defaultdict
    for i in range(n//2, 0, -1):
        d = defaultdict(list)
        for j in range(n-i+1):
            d[((l[j+i]-l[j])*pows[j])%M].append(j)
        for k,v in d.items():
            if v[0]+i<=v[-1]:
                ans = i
        if ans>0:
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
s = input()
### ローリングハッシュ rolling hash
import random
# M = 10**9+7
# M = 1<<63 - 1
M = 9007199254740997

b = random.choice(range(1,M))
def rhash_list(s):
    l = [chr(v) for v in range(ord("a"), ord("z")+1)]
    d = {c:i+2 for i,c in enumerate(l)}
    ans = 0
    v = 1
    l = [0]
    for item in s:
        ans += d[item]*v
        v *= b
        ans %= M
        v %= M
        l.append(ans)
    return l
l = rhash_list(s)
if len(set(s))==n:
    ans = 0
else:
    binv = pow(b,M-2,M)
    pows = [None]*(n+1)
    v = 1
    for j in range(n+1):
        pows[j] = v
        v *= binv
        v%= M
#         pow(binv,j,M)
    ans = 0
    from collections import defaultdict
    for i in range(n//2, 0, -1):
        d = defaultdict(list)
        for j in range(n-i+1):
            d[((l[j+i]-l[j])*pows[j])%M].append(j)
        for k,v in d.items():
            if v[0]+i<=v[-1]:
                ans = i
        if ans>0:
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


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

    ret = 0
    for i in range(1, N):
        ret = max(ret, min(A[i], i))

    return ret


def main():

    N = in_n()
    S = in_s()

    ans = 0
    for i in range(N):
        ans = max(ans, z_algo(S[i:]))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
"""
連続する部分文字列の種類は多くてN**2個ある。
N<=5000という制約から考えて、これらの連続する部分文字列に対して全探索ができる。
問題は、各部分文字列が条件を満たしているかどうかをどうやって調べるかだ。
これは、各部分文字列種ごとにどの区間で出現するかをメモしておけば良い。
dic["hogehoge"] => "hogehoge"という連続部分文字列が出現する区間をメモした配列
dic["hogehoge"] = [(0,7),(2,9),(6,13),(10,17)]　といった具合だ。
dic[hogehoge][x][1]とdic[hogehoge][x+1][1]が重複しているかを調べることで条件を満たすかどうかを判定できる。
区間(i,j)のjで昇順並びになっている必要があるが、実直にi,jでループして連続部分文字列を探索すれば、自然と昇順でメモされる。
計算量はO(N**2)で間に合う。
"""
N = int(input())
S = input()

dic = {}
for i in range(N):
    for j in range(i,N):
        if S[i:j+1] not in dic:
            dic[S[i:j+1]] = []
        dic[S[i:j+1]].append((i,j))

ans = 0
for k,v in dic.items():
    if len(v) > 1:
        for i in range(1,len(v)):
            if v[i][0]<=v[i-1][1]:
                break
        else:
            ans = max(ans,len(k))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
"""
連続する部分文字列の種類は多くてN**2個ある。
N<=5000という制約から考えて、これらの連続する部分文字列に対して全探索ができる。
問題は、各部分文字列が条件を満たしているかどうかをどうやって調べるかだ。
これは、各部分文字列種ごとにどの区間で出現するかをメモしておけば良い。
dic["hogehoge"] => "hogehoge"という連続部分文字列が出現する区間をメモした配列
dic["hogehoge"] = [(0,7),(2,9),(6,13),(10,17)]　といった具合だ。
dic[hogehoge][x][1]とdic[hogehoge][x+1][1]が重複しているかを調べることで条件を満たすかどうかを判定できる。
区間(i,j)のjで昇順並びになっている必要があるが、実直にi,jでループして連続部分文字列を探索すれば、自然と昇順でメモされる。
計算量はO(N**2)で間に合う。
"""
N = int(input())
S = input()

dic = {}
for i in range(N):
    for j in range(N):
        if S[i:j+1] not in dic:
            dic[S[i:j+1]] = []
        dic[S[i:j+1]].append((i,j))

ans = 0
for k,v in dic.items():
    if len(v) > 1:
        for i in range(1,len(v)):
            if v[i][0]<=v[i-1][1]:
                break
        else:
            ans = max(ans,len(k))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def LCS(S, T, f=False):

    L1 = len(S)
    L2 = len(T)
    dp = [[0] * (L2 + 1) for i in range(L1 + 1)]

    for i in range(L1 - 1, -1, -1):
        for j in range(L2 - 1, -1, -1):
            r = max(dp[i + 1][j], dp[i][j + 1])
            if S[i] == T[j]:
                r = max(r, dp[i + 1][j + 1] + 1)
            dp[i][j] = r

    if not f:
        return dp[0][0]

    res = []
    i = 0
    j = 0
    while i < L1 and j < L2:
        if S[i] == T[j]:
            res.append(S[i])
            i += 1
            j += 1
        elif dp[i][j] == dp[i + 1][j]:
            i += 1
        elif dp[i][j] == dp[i][j + 1]:
            j += 1

    return (dp[0][0], ''.join(res))


def main():
    N = in_n()
    S = in_s()

    ans = 0
    s1 = list(S)
    s2 = []
    for i in range(N - 1):
        s2.append(s1[0])
        s1.pop(0)
        ans = max(ans, LCS(s1, s2))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def LCS(S, T, f=False):

    L1 = len(S)
    L2 = len(T)
    dp = [[0] * (L2 + 1) for i in range(L1 + 1)]

    for i in range(L1 - 1, -1, -1):
        for j in range(L2 - 1, -1, -1):
            r = max(dp[i + 1][j], dp[i][j + 1])
            if S[i] == T[j]:
                r = max(r, dp[i + 1][j + 1] + 1)
            dp[i][j] = r

    if not f:
        return dp[0][0]

    res = []
    i = 0
    j = 0
    while i < L1 and j < L2:
        if S[i] == T[j]:
            res.append(S[i])
            i += 1
            j += 1
        elif dp[i][j] == dp[i + 1][j]:
            i += 1
        elif dp[i][j] == dp[i][j + 1]:
            j += 1

    return (dp[0][0], ''.join(res))


def main():
    N = in_n()
    S = in_s()

    ans = 0
    for i in range(1, N):
        ans = max(ans, LCS(S[:i], S[i:]))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import numba
from numba import jit, njit

@njit
def solve(dp, sn):
    for i in range(n-2, -1, -1):
        for j in range(n-1, i,-1):
            if i + dp[i+1][j+1] >= j:
                break
            if s[i] == s[j]:
                dp[i][j] = dp[i+1][j+1] + 1
    return dp.max()

n = int(input())
s = input() + '_'
sn = np.zeros(n+1, dtype=int)
for i in range(n+1):
    sn[i] = ord(s[i])

dp = np.zeros((n+1,n+1), dtype=int)

print(solve(dp, sn))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())
s = input() + '_'
    
dp = np.zeros((n+1,n+1),dtype=int)
for i in range(n-2, -1, -1):
    for j in range(n-1, i,-1):
        if i + dp[i+1][j+1] >= j:
            break
        if s[i] == s[j]:
            dp[i][j] = dp[i+1][j+1] + 1
print(dp.max())

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-2, -1, -1):
    for j in range(n-1, i,-1):
        if i + dp[i+1][j+1] >= j:
            break
        if s[i] == s[j]:
            dp[i][j] = dp[i+1][j+1] + 1
print(max(list(map(lambda x: max(x), dp))))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = str(input())
l = 0
m = 1
for i in range(n):
    for h in range(m,(n//2)+m):
        if s[i:h] in s[:i] or s[i:h] in s[h:]:
            if l < len(s[i:h]):
                l = len(s[i:h])
    m += 1
print(l)