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


def arihon_SA(T):
    rank = [0] * (n + 1)
    SA = [0] * (n + 1)
    temp = [0] * (n + 1)

    def rank_calc(i):
        res1 = rank[i]
        res2 = -1
        if i + k <= n:
            res2 = rank[i + k]
        return (res1, res2)

    for i in range(n + 1):
        SA[i] = i
        if i < n:
            rank[i] = ord(T[i])
        else:
            rank[i] = -1
    k = 1

    while k <= n:
        SA.sort(key=rank_calc)
        temp[SA[0]] = 0
        for i in range(1, n + 1):
            temp[SA[i]] = temp[SA[i - 1]]
            if rank_calc(SA[i - 1]) < rank_calc(SA[i]):
                temp[SA[i]] += 1
        rank = temp[::]
        k *= 2

    return SA


# SAとsからSA[i+1],SA[i]の共通接頭辞LCP[i]を求めたい。
# len(s)=nならlen(SA)=n+1
# LCP[0]は必ず0
def arihon_LCP(s, SA):
    num = len(s)
    rank = [0] * (num + 1)
    LCP = [-1] * (num)
    for i in range(num + 1):
        rank[SA[i]] = i
    h = 0
    LCP[0] = 0
    for i in range(num):
        j = SA[rank[i] - 1]
        if h > 0:
            h -= 1
        while j + h < num and i + h < num:
            if s[j + h] != s[i + h]:
                break
            else:
                h += 1
        LCP[rank[i] - 1] = h
    return LCP


class SegmentTree:
    ele = 10 ** 20
    func = min
    # SEG木は1-index
    # Aに関しては0-index

    def __init__(self, n):  # Aは0-idx
        self.n = n
        self.num = 2 ** ((self.n - 1).bit_length())
        self.SEG = [self.ele] * (2 * self.num)

    def search(self, idx):
        return self.SEG[idx + self.num]

    def initialize(self, A):
        for i in range(self.n):
            self.SEG[i + self.num] = A[i]
        for i in range(self.num - 1, 0, -1):
            self.SEG[i] = self.func(self.SEG[2 * i], self.SEG[2 * i + 1])

    def update(self, idx, val):
        idx += self.num
        self.SEG[idx] = val
        idx //= 2
        while idx:
            self.SEG[idx] = self.func(self.SEG[2 * idx], self.SEG[2 * idx + 1])
            idx //= 2

    def query(self, left, right):
        # maspy式。半開区間のママ処理する
        # left, rightで値を分けているのは交換法則不成立のときのため
        # 開区間→Rが奇数→右端が偶数→1ずらしてから計算
        # 　下から上への遷移は2で割る
        # juppy氏は閉区間に直していた
        resleft = self.ele
        resright = self.ele
        left += self.num
        right += self.num
        while right - left > 0:
            if left % 2 == 1:
                resleft = self.func(resleft, self.SEG[left])
                left += 1
            if right % 2 == 1:
                right -= 1
                resright = self.func(resright, self.SEG[right])
            left //= 2
            right //= 2
        return self.func(resleft, resright)


SA = arihon_SA(s)
LCP = arihon_LCP(s, SA)
ST = SegmentTree(n)
ST.initialize(LCP)
ans = 0
for i in range(n):
    for j in range(i + 1, n + 1):
        a = SA[i]
        b = SA[j]
        temp = ST.query(i, j)
        if abs(b - a) >= temp:
            ans = max(ans, temp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, Counter
from itertools import combinations
import re

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

d = defaultdict(list)
for i in range(N-2):
  d[S[i:i+3]].append(i)

m = 0
for x in d.values():
  if len(x) > 1:
    for i, j in combinations(x, 2):
      if j < i + 3:
        continue
      l = 3
      while i+l < j and j+l < N and S[i+l] == S[j+l]:
        l += 1
      m = max(m, l)

for k in range(2, 0, -1):
  if m > 0:
    break
  d = {}
  for i in range(N-k+1):
    x = S[i:i+k]
    if x in d and d[x] + k <= i:
      m = k
      break
    else:
      d[x] = i

print(m)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, Counter
from itertools import combinations
import re

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

d = defaultdict(list)
for i in range(N-2):
  d[S[i], S[i+1], S[i+2]].append(i)

m = 0
for x in d.values():
  if len(x) > 1:
    for i, j in combinations(x, 2):
      if j < i + 3:
        continue
      l = 3
      while i+l < j and j+l < N and S[i+l] == S[j+l]:
        l += 1
      m = max(m, l)

if m == 0:
  if re.search(r'(..).*(\1)', S):
    m = 2
  elif re.search(r'(.).*(\1)', S):
    m = 1

print(m)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N = int(input())
S = input()

mod = (1 << 61) - 1
b = 10 ** 9 + 7

h_table = [[0] * (N + 1) for _ in range(N + 1)]
memo = defaultdict(list)
length = defaultdict(int)

for i, s in enumerate(S):
    h = ord(s)
    h_table[i][i + 1] = h
    memo[h].append((i, i + 1))
    length[h] = 1

for d in range(2, N + 1):
    for i, s in enumerate(S[d - 1:]):
        h = (h_table[i][i+d-1] * b + ord(s)) % mod
        h_table[i][i+d] = h
        memo[h].append((i, i+d))
        length[h] = d

ans = 0
for h, v in memo.items():
    if len(v) < 2:
        continue
    _, L = v[0]
    R, _ = v[-1]
    if L <= R:
        ans = length[h]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
class RollingHash:
    def __init__(self, s):
        B = 10**5+7
        self.MOD = 10**9+7

        size = len(s)
        self.hashtable = [0] * (size+1)
        self.power = [0] * (size+1)
        self.power[0] = 1

        for i in range(1, size+1):
            self.hashtable[i] = (self.hashtable[i-1] * B + ord(s[i-1]))%self.MOD
        for i in range(1, size+1):
            self.power[i] = (B * self.power[i-1])%self.MOD

    def get_hash(self, l, length):
        r = length+l-1
        l -= 1
        return (self.hashtable[r]-self.hashtable[l]*self.power[r-l])%self.MOD


def solve():
    N = int(input())
    S = input()
    size = len(S)
    hash_table = RollingHash(S)

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

            left = 1
            right = min(j-i, size-j+1)+1

            while right-left>1:
                m = (left+right)//2
                if hash_table.get_hash(i, m)==hash_table.get_hash(j, m):
                    left = m
                else:
                    right = m
            ans = max(ans, left)

    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
class RollingHash:
    def __init__(self, s):
        B = 10**5+7
        self.MOD = 10**9+7

        size = len(s)
        self.hashtable = [0] * (size+1)
        self.power = [0] * (size+1)
        self.power[0] = 1

        for i in range(1, size+1):
            self.hashtable[i] = (self.hashtable[i-1] * B + ord(s[i-1]))%self.MOD
        for i in range(1, size+1):
            self.power[i] = (B * self.power[i-1])%self.MOD

    def get_hash(self, l, length):
        r = length+l-1
        l -= 1
        return (self.hashtable[r]-self.hashtable[l]*self.power[r-l])%self.MOD


N = int(input())
S = input()
size = len(S)
hash_table = RollingHash(S)

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

        left = 1
        right = min(j-i, size-j+1)+1

        while right-left>1:
            m = (left+right)//2
            if hash_table.get_hash(i, m)==hash_table.get_hash(j, m):
                left = m
            else:
                right = m
        ans = max(ans, left)

print(ans)

Submission status: Time Limit Exceeded

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


class RollingHash:
    """文字列stringsの部分文字列のハッシュを構築する。O(N)"""
    def __init__(self, string):
        self.n = len(string)
        self.BASE = 1234
        self.MASK30 = (1 << 30) - 1
        self.MASK31 = (1 << 31) - 1
        self.MASK61 = (1 << 61) - 1
        self.MOD = self.MASK61
        self.hash = [0] * (self.n + 1)
        self.pow = [1] * (self.n + 1)

        for i, char in enumerate(string):
            self.hash[i + 1] = self.calc_mod(self.mul(self.hash[i], self.BASE)
                                             + ord(char))
            self.pow[i + 1] = self.calc_mod(self.mul(self.pow[i], self.BASE))

    def calc_mod(self, x):
        """x mod 2^61-1 を返す。"""
        xu = x >> 61
        xd = x & self.MASK61
        x = xu + xd
        if x >= self.MOD:
            x -= MASK61
        return x

    def mul(self, a, b):
        """a*b mod 2^61-1 を返す。"""
        au = a >> 31
        ad = a & self.MASK31
        bu = b >> 31
        bd = b & self.MASK31
        mid = ad * bu + au * bd
        midu = mid >> 30
        midd = mid & self.MASK30
        return self.calc_mod(au * bu * 2 + midu + (midd << 31) + ad * bd)

    def get_hash(self, l, r):
        """string[l:r]のハッシュ値を返す。O(1)"""
        res = self.calc_mod(self.hash[r]
                            - self.mul(self.hash[l], self.pow[r - l]))
        return res

    def merge(self, h1, h2, length2):
        """ハッシュ値h1と長さlength2のハッシュ値h2を結合する。O(1)"""
        return self.calc_mod(self.mul(h1, self.pow[length2]) + h2)

    def get_lcp(self, l1, r1, l2, r2):
        """string[l1:r2]とstring[l2:r2]の長共通接頭辞(longest common prefix)の
        長さを求める。O(log|string|)
        """
        ng = min(r1 - l1, r2 - l2) + 1
        ok = 0
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            if self.get_hash(l1, l1 + mid) == self.get_hash(l2, l2 + mid):
                ok = mid
            else:
                ng = mid
        return ok


n = int(input())
s = input()[:-1]


len_s = len(s)
rh = RollingHash(s)

ans = 0
for l1 in range(len_s):
    for l2 in range(l1 + 1, len_s):
        lcp_length = rh.get_lcp(l1, l2, l2, len_s)
        ans = max(lcp_length, ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = str(input())
ans = 0
for i in range(N):
  for j in range(i+1,N):
    if S[j+1:].count(S[i:j+1]) >= 1:
      ans = max(ans,len(S[i:j+1]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
max_val = 0
for l1 in range(n):
    for l2 in range(l1 + 1, n):
        if s[l1] != s[l2]:
            continue
        i = l1
        j = l2
        val = 0
        while i < l2 and j < n and s[i] == s[j]:
            i += 1
            j += 1
            val += 1
        max_val = max(max_val, val)
print(max_val)

Submission status: Time Limit Exceeded

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

def ZA(n,s):
    Z=[0 for i in range(n)]
    Z[0]=n
    i=1
    j=0
    cand=0
    while i<n:
        while i+j<n and s[j]==s[i+j]:
            j+=1
        Z[i]=j
        cand=max(cand,min(Z[i],i))
        if j==0:
            i+=1
            continue
        k=1
        while k<j and k+Z[k]<j:
            Z[i+k]=Z[k]
            cand=max(cand,min(Z[i],i))
            k+=1
        i+=k
        j-=k
    #print(Z)
    return cand


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

Submission status: Time Limit Exceeded

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

# 左は尺取り。しかも３とって失敗したら、l,r双方いんくりしてよい
# 右は総当たり。

ans = 0
l,r = 0,1
while l<N and r<N:
  findf = False
  target = S[l:r]
  L = r-l
  for k in range(l+L,N-1):
    compare = S[k:k+L]
    #print(target, compare)
    if target == S[k:k+L]:
      ans = max(ans,L)
      findf = True
      break
  if findf and r < N-1:
    r += 1
  else:
    l += 1
    r = min(r+1,N-1)
    
print(ans)

Submission status: Time Limit Exceeded

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

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

        if s[i] == s[j]:
            dp[i][j] = dp[i+1][j+1] + 1        

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

Submission status: Time Limit Exceeded

Solution code:
def z_al(s):
    le = len(s)
    res = [0 for i in range(le)]
    i, j = 1, 0
    while i < le:
        while i + j < le and s[i + j] == s[j]:
            j += 1
        res[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < le and res[k] + k < j:
            res[i + k] = res[k]
            k += 1
        i += k
        j -= k
    return res
n = int(input())
s = input()
ans = 0
for i in range(n):
    s2 = s[i:]
    res = z_al(s2)
    for j in range(len(s2)):
        ans = max(ans, min(res[j], j))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
S = input().strip()
kmax = 0
for k in range(1,N//2+1):
    C = {}
    a = deque(list(S[:k]))
    C[tuple(a)]=[0]
    for i in range(1,N-k+1):
        a.popleft()
        a.append(S[i+k-1])
        if tuple(a) not in C:
            C[tuple(a)] = []
        C[tuple(a)].append(i)
    for a in C:
        if len(C[a])>=2:
            flag = 0
            for i in range(1,len(C[a])):
                if C[a][i]-C[a][i-1]>=k:
                    flag = 1
                    break
            if flag==1:
                kmax = k
                break
print(kmax)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input().strip()
kmax = 0
for k in range(1,N//2+1):
    C = {}
    for i in range(N-k+1):
        if S[i:i+k] not in C:
            C[S[i:i+k]] = []
        C[S[i:i+k]].append(i)
    for a in C:
        if len(C[a])>=2:
            flag = 0
            for i in range(1,len(C[a])):
                if C[a][i]-C[a][i-1]>=k:
                    flag = 1
                    break
            if flag==1:
                kmax = k
                break
print(kmax)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
#dp[i][j] S[i-x:i+1]==S[j-x:j+1]となる最大のx
dp = [[0] * (N + 1) for _ in range(N + 1)]
ans = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        if S[i] == S[j]:
            dp[i][j] = min(dp[i - 1][j - 1] + 1, j - i)
    ans = max(dp[i] + [ans])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
#dp[i][j] S[i-x:i+1]==S[j-x:j+1]となる最大のx
dp = [[0] * (N + 1) for _ in range(N + 1)]
ans = 0
for i in range(N - 1):
    for j in range(i+1,N):
        if S[i] == S[j]:
            dp[i][j] = min(j - i, dp[i - 1][j - 1] + 1)
            ans = max(ans, max(dp[i]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

def main(N, S):
    dp = np.zeros((N + 1, N + 1), dtype=int)
    ans = 0
    for i in range(N - 1):
        for j in range(i + 1, N):
            dp[i, j] = min(j - i, dp[i - 1, j - 1] + 1) if S[i] == S[j] else 0
        ans = max(ans, np.max(dp[i]))
    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', 'i8(i8,i8[:])')(main)
    # b1: bool, i4: int32, i8: int64, double: f8, [:], [:, :]
    cc.compile()
else:
    try:
        from my_module import main
    except:
        1
    N = int(input())
    S = np.array([ord(_) for _ in input()])
    print(main(N, S))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from numba import njit

def main(N, S, dp):
    ans = 0
    for i in range(N - 1):
        for j in range(i + 1, N):
            dp[i,j] = min(j - i, dp[i - 1,j - 1] + 1) if S[i] == S[j] else 0
        ans = max(ans, np.max(dp[i]))
    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', 'i8(i8,unicode_type,i8[:,:])')(main)
    # b1: bool, i4: int32, i8: int64, double: f8, [:], [:, :]
    cc.compile()
else:
    from my_module import main
    N = int(input())
    S = input()#np.array([ord(_) for _ in input()])
    dp = np.zeros((N + 1, N + 1), dtype=int)
    print(main(N, S, dp))

Submission status: Time Limit Exceeded

Solution code:
#dp[i][j]:S[i-x:i]==S[j-x:j]となる最大のx
import numpy as np

def solve(NS):
    N = NS[0]
    S = NS[1:]
    dp=np.zeros((N+1,N+1),dtype=int)
    for i in range(N - 1):
        for j in range(i + 1, N):
            dp[i][j] = min(j - i, dp[i - 1][j - 1] + 1) if S[i] == S[j] else 0
    return dp.max()

def main():
    NS = np.array([int(input())] + [ord(_) for _ in input()])
    print(solve(NS))

def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', 'i8(i8[:])')(solve)
    cc.compile()

if __name__ == '__main__':
    import sys
    if sys.argv[-1] == 'ONLINE_JUDGE':
        cc_export()
        exit(0)
    #from my_module import solve
    main()

Submission status: Time Limit Exceeded

Solution code:
#dp[i][j]:S[i-x:i]==S[j-x:j]となる最大のx
import numpy as np

def solve(NS):
    N = NS[0]
    S = NS[1:]
    dp=np.zeros((N+1,N+1),dtype=int)
    for i in range(N - 1):
        for j in range(i + 1, N):
            dp[i][j] = min(j - i, dp[i - 1][j - 1] + 1) if S[i] == S[j] else 0
    return dp.max()

def main():
    NS = np.array([int(input())] + [ord(_) for _ in input()])
    print(solve(NS))

def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()

if __name__ == '__main__':
    import sys
    if sys.argv[-1] == 'ONLINE_JUDGE':
        cc_export()
        exit(0)
    #from my_module import solve
    main()

Submission status: Time Limit Exceeded

Solution code:
#dp[i][j]:S[i-x:i]==S[j-x:j]となる最大のx
import numpy as np
from numba import njit
N = int(input())
S = np.array([ord(_) for _ in input()])
dp = np.array([[0] * (N + 1) for _ in range(N + 1)])

@njit
def solve(N, S, dp):
    for i in range(N - 1):
        for j in range(i + 1, N):
            dp[i][j] = min(j - i, dp[i - 1][j - 1] + 1) if S[i] == S[j] else 0
    print(dp.max())

solve(N, S, dp)

Submission status: Time Limit Exceeded

Solution code:
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    n = ni()
    s = list(input())

    d = [set() for _ in range(n + 1)]

    ans = 0
    for i in range(n - 1, -1, -1):
        d[i] = d[i + 1].copy()
        tmp = ""
        for j in range(i, n):
            tmp += s[j]
            d[i].add(tmp)
            if j + 1 < n:
                if tmp in d[j + 1]:
                    ans = max(ans, j - i + 1)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=input()
ans=0
for i in range(N-1):
  #jstart=i+ans+1
  for j in range(i+1,N):
    if S[i:j] in S[j:]:
      ans=max(ans,j-i)
    else:
      break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
def solve(l):
    for i in range(n-2*l+1):
        for j in range(i+l, n-l+1):
            for k in range(l):
                if s[i+k]!=s[j+k]:
                    break
            else:
                return True
    return False

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
def solve(l):
    for i in range(n-2*l+1):
        for j in range(i+l, n-l+1):
            if s[i:i+l]==s[j:j+l]:
                return True
    return False

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
def lcs(s1, s2, mx):
    imx = min(len(s1), len(s2))
    for i in range(len(s1)+len(s2)-1):
        p1 = max(0, i-len(s1)+1)
        p2 = max(0, len(s2)-i-1)
        if min(len(s1)-p1, len(s2)-p2)<=mx:
            continue
        l = 0
        while p1<len(s1) and p2<len(s2):
            if s1[p1]==s2[p2]:
                l += 1
            else:
                mx = max(mx, l)
                if mx==imx:
                    return mx
                l = 0
            p1 += 1
            p2 += 1
        mx = max(mx, l)
    return mx
ans = 0
for i in range(1, n):
    if min(i, n-i)<=ans:
        continue
    ans = max(ans, lcs(s[:i], s[i:], ans))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
def lcs(s1, s2):
    mx = 0
    for i in range(len(s1)+len(s2)-1):
        p1 = max(0, i-len(s1)+1)
        p2 = max(0, len(s2)-i-1)
        l = 0
        while p1<len(s1) and p2<len(s2):
            if s1[p1]==s2[p2]:
                l += 1
            else:
                mx = max(mx, l)
                l = 0
            p1 += 1
            p2 += 1
        mx = max(mx, l)
    return mx
ans = 0
for i in range(n-1):
    ans = max(ans, lcs(s[:i+1], s[i+1:]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(input())
b = 27
mod = pow(2, 61) - 1
m = n // 2
x = [1] * (m + 1)
for i in range(1, m + 1):
    x[i] = (x[i - 1] * b) % mod
h0 = [0] * m
h0[0] = ord(s[0]) - 96
d = [{} for _ in range(m + 1)]
for i in range(1, m):
    h0[i] = (h0[i - 1] * b + (ord(s[i]) - 96)) % mod
for i in range(m, 0, -1):
    h = h0[i - 1]
    d[i][h] = 0
    for j in range(i, n):
        h *= b
        h %= mod
        h -= (x[i] * (ord(s[j - i]) - 96) % mod)
        h += (ord(s[j]) - 96)
        h %= mod
        if h in d[i]:
            if (j - i + 1 - d[i][h]) >= i:
                print(i)
                exit()
        else:
            d[i][h] = j - i + 1
print(0)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(input())
b = 27
mod = pow(2, 61) - 1
m = n // 2
x = [1] * (m + 1)
for i in range(1, m + 1):
    x[i] = (x[i - 1] * b) % mod
d = {}
for i in range(m, 0, -1):
    h = 0
    for j in range(i):
        h += (x[i - j - 1] * (ord(s[j]) - 96) % mod)
        h %= mod
    d[h] = 0
    for j in range(i, n):
        h *= b
        h %= mod
        h -= (x[i] * (ord(s[j - i]) - 96) % mod)
        h += (ord(s[j]) - 96)
        h %= mod
        if h in d:
            if (j - m + 1 - d[h]) >= i:
                print(i)
                exit()
        else:
            d[h] = j - m + 1
print(0)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(input())
b = 27
mod = pow(2, 61) - 1
m = n // 2
x = [1] * (m + 1)
for i in range(1, m + 1):
    x[i] = (x[i - 1] * b) % mod
for i in range(m, 0, -1):
    h = 0
    d = {}
    for j in range(i):
        h += (x[i - j - 1] * (ord(s[j]) - 96) % mod)
        h %= mod
    d[h] = 0
    for j in range(i, n):
        h *= b
        h %= mod
        h -= (x[i] * (ord(s[j - i]) - 96) % mod)
        h += (ord(s[j]) - 96)
        h %= mod
        if h in d:
            if (j - m + 1 - d[h]) >= i:
                print(i)
                exit()
        else:
            d[h] = j - m + 1
print(0)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    N = int(input())
    S = input()
    d = {}
    for i in range(N):
        key = S[i]
        for j in range(i, N):
            if j != i:
                key += S[j]
            d.setdefault(key, [])
            if len(d[key]) > 0:
                if d[key][-1][1] < i:
                    d[key].append((i, j))    
            else:
                d[key].append((i, j))
    #print(d)
    ans = 0
    for k, v in d.items():
        if len(v) > 1:
            ans = max(ans, len(k))
    print(ans)





if '__main__' == __name__:
    resolve()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    N = int(input())
    S = input()
    d = {}
    for i in range(N):
        for j in range(i+1, N+1):
            key = S[i:j]
            d.setdefault(key, [])
            if len(d[key]) > 0:
                if d[key][-1][1] <= i:
                    d[key].append((i, j))    
            else:
                d[key].append((i, j))
    ans = 0
    for k, v in d.items():
        if len(v) > 1:
            ans = max(ans, len(k))
    print(ans)





if '__main__' == __name__:
    resolve()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
S = input()
ans = 0
for d in range(n):
    cnt = 0
    for i in range(n-d):
        if S[i] == S[d+i]:
            cnt += 1
        else:
            cnt = 0
        ans = max(ans, min(cnt, d))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    s = input()[::-1]

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

    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

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

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
    l = len(S)
    A[0] = l

    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 min(l-i, j-A[k]) > k:
            A[i+k] = A[k]
            k += 1
        i += k
        j -= k
    return A

ans = 0
for i in range(N):
    s = S[i:]
    tmp = z_algo(s)
    
    for i in range(1, len(tmp)):
        if tmp[i] > i:
            tmp[i] = 0
    if len(tmp) >= 2:
        ans = max(ans, max(tmp[1:]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=input()
ans = 0
for i in range(N-2):
  for l in range(1,(N-i)//2+1):
    s = S[i:i+l]
    #print(i,l,s)
    if s in S[i+l:]:
      ans = max(ans,l)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def z_algorithm(s):  # O(|S|)
    """
    SとS[i:]のLCP(longest common prefix: 最長共通接頭辞の長さ) Z[i]を計算し、Zを返す
    """
    n = len(s)
    z = [0] * n
    z[0] = n
    i = 1
    j = 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 = 1
        while k < j and k + z[k] < j:
            z[i + k] = z[k]
            k += 1
        i += k
        j -= k
    return z

# ---------------------- #

n = int(input())
s = input()

ans = 0
for i in range(n):
    Z = z_algorithm(s[i:])
    for j in range(len(Z)):
        if Z[j] > j:
            ans = max(ans, j)
        else:
            ans = max(ans, Z[j])

print(ans)

Submission status: Time Limit Exceeded

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

# Z-algorithm
# 文字列が与えられた時、各 i について「S と S[i:|S|-1] の最長共通接頭辞の長さ」を記録した配列 A を O(|S|) で構築するアルゴリズムです。
#s='aaabaaaab'
def func(s):
  a=[0]*len(s)
  a[0]=len(s)
  i,j=1,0
  while i<len(s):
    while i+j<len(s) and s[j]==s[i+j]:
      j+=1
    a[i]=j
    if j==0:
      i+=1
      continue
    k=1
    while i+k<len(s) and k+a[k]<j:
      a[i+k]=a[k]
      k+=1
    i+=k
    j-=k
  return a
ans=0
for i in range(n):
  a=func(ss[i:])
  for j in range(len(a)):
    ans=max(ans,min(a[j],j))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N = getN()
S = '0' + input()

lista = defaultdict(int)

for i in range(N // 2, -1, -1):
    for j in range(1, N - i + 1):
        opt = S[j:i + j + 1]
        if lista[opt] == 0:
            lista[opt] = i + j
        else:
            if lista[opt] < j:
                print(len(opt))
                exit()
print(0)