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

import numpy as np
dp = np.zeros((N, N), dtype = 'int') - 1

for j in range(1, N):
    k = 0
    while j + k < N and S[k] == S[j + k]:
        k += 1
    dp[0][j] = k


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

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

Submission status: Time Limit Exceeded

Solution code:
def z_array(pattern, text):
    psize = len(pattern)
    tsize = len(text)
    str = pattern + '$' + text
    matchsize = 0
    for i in range(tsize-1):
        j = 0
        while (j <= psize - 1 and i+j <= tsize - 1 and str[j] == str[i+psize+1+j]):
            j += 1
        if(matchsize < j): matchsize = j
    return matchsize

def main(size, text):
    length = 0
    for i in range(size-1):
        z = z_array(text[i+1:size], text[:i+1])
        if(length < z): length = z
    return length

size = int(input())
text = input()
print(main(size, text))

Submission status: Time Limit Exceeded

Solution code:
def z_array(pattern, text):
    str = pattern + '$' + text
    matchsize = 0
    for i in range(len(text)-1):
        j = 0
        while (i+1+j <= len(text) and str[j] == str[i+len(pattern)+1+j]):
            j += 1
        if(matchsize < j): matchsize = j
    return matchsize

def main(size, text):
    length = 0
    for i in range(size-1):
        z = z_array(text[i+1:size], text[:i+1])
        if(length < z): length = z
    return length

size = int(input())
text = input()
print(main(size, text))

Submission status: Time Limit Exceeded

Solution code:
def z_array(pattern, text):
    str = pattern + '$' + text
    matchsize = 0
    for i in range(len(str)-1):
        j = 0
        while (i+1+j <= len(str)-1 and str[j] == str[i+1+j]):
            j += 1
        if(matchsize < j): matchsize = j
    return matchsize

def main(size, text):
    length = 0
    for i in range(size-1):
        z = z_array(text[i+1:size], text[:i+1])
        if(length < z):
            length = z
    return length

size = int(input())
text = input()
print(main(size, text))

Submission status: Time Limit Exceeded

Solution code:
def z_array(pattern, text):
    str = pattern + '$' + text
    z = []
    z.append(0)
    for i in range(len(str)-1):
        j = 0
        z.append(0)
        while (i+1+j <= len(str)-1 and str[j] == str[i+1+j]):
            j += 1
            z[i+1] = j
    return z

def main(size, text):
    length = 0
    for i in range(size-1):
        z = z_array(text[i+1:size], text[:i+1])
        if(length < max(z)):
            length = max(z)
    return length

size = int(input())
text = input()
print(main(size, text))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
def Zalgo(S):
    N = len(S)
    A = [0]*N
    A[0] = N
    i = 1
    j = 0
    while i < N:
        while i + j < N and S[j] == S[i + j]:
            j += 1
        A[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < N and k + A[k] < j:
            A[i + k] = A[k]
            k += 1
        i += k
        j -= k
    return A
res = 0
for i in range(N - 1):
    lcp = Zalgo(S[i:])
    for j in range(N - i):
        l = min(j, lcp[j])
        res = max(l, res)
print(res)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
class ZAlgorithm(object):
    def __init__(self, s: str):
        self.lcp = self.__create_z(s)

    def __call__(self, i: int):
        return self.lcp[i]

    def __create_z(self, s: str):
        n = len(s)
        lcp = [n] + [0]*(n-1)
        l, r = 0, 0

        for t in range(1, n):
            if t>r:
                z = 0
                while t+z<n and s[0+z]==s[t+z]:
                    z += 1
                lcp[t] = z
                if z>0:
                    l, r = t, t+z-1
            else:
                p, b = t-l, r-t+1
                if lcp[p]<b:
                    lcp[t] = lcp[p]
                else:
                    i = r+1
                    while i<n and s[i]==s[i-t]:
                        i += 1
                    lcp[t] = i-t
                    l, r = t, i-1
        return lcp

def main():
    n, s = open(0).read().split()
    a = 0
    for i in range(int(n)-1):
        ss = s[i:]
        z_algo = ZAlgorithm(ss)
        for j in range(len(ss)):
            a = max(a, min(z_algo(j), j))
    print(a)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
n = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip()


dp = [[float('inf') for i in range(n)] for j in range(n)]
#初期条件
for j in range(1, n):
    if S[0] == S[j]:
        dp[0][j] = 1
    else:
        dp[0][j] = 0

#print(dp)

for i in range(1, n-1):
    for j in range(i+1, n):
        if S[i] ==S[j]:
            dp[i][j] = min(dp[i-1][j-1] +1, n//2)
        else:
            dp[i][j] = 0

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

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S = input()
l, r = 0, N

def pow_mod(a, b, m):
  ab = 1
  for _ in range(b):
    ab = (ab * a) % m
  return ab

def c2n(c):
  return ord(c) - 97

def hash(s, B, H):
  sh = 0
  for c in s:
    sh = (sh * B + c2n(c)) % H
  return sh

def find_rolling_hash(s, t):
  B, H = 10 ** 8 + 7, 2 ** 64

  sl, tl = len(s), len(t)
  if sl > tl:
    return False
  Bsl = pow_mod(B, sl, H)
  sh, cth = hash(s, B, H), hash(t[:sl], B, H)
  if sh == cth:
    return True
  for i in range(tl - sl):
    cth = (cth * B - c2n(t[i]) * Bsl + c2n(t[i+sl])) % H
    if sh == cth:
      return True
  return False

def t(n):
  for i in range(0, N-n):
    s = S[i:i+n]
    if find_rolling_hash(s, S[i+n:]):
      return True
  return False

while l+1<r:
  m = (l+r)//2
  if t(m):
    l=m
  else:
    r=m

print(l)

Submission status: Time Limit Exceeded

Solution code:
def zalg(pattern, text):
  L = pattern + "$" + text
  N = len(L)
  Z = [0] * (N)
  i = 1
  j = 0
  while i < N:
    while i + j < N and L[j] == L[i + j]:
      j += 1
    Z[i] = j
    if j == 0:
      i += 1
      continue
    k = 1
    while i + k < N 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 = zalg(S[i:], S)
  for j in range(1, N):
    ans = max(ans, min(Z[-j], N - i - j))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def zalgo(s):
    n = len(s)
    z = [0]*n
    l,r = 0,0
    for i in range(1,n):
        if i > r:
            l = r = i
            initial_r = r
            while r < n and s[r] == s[r-l] and r-l != initial_r:
                r += 1
            z[i] = r-l
            r -= 1
        else:
            k = i-l
            if z[k] < r-i+1:
                z[i] = z[k]
            else:
                l = i
                while r < n and s[r] == s[r - l]:
                    r += 1
                z[i] = r - l
                r -= 1
    return z
n = input()
s = input()
l = 0
for i in range(0,len(s)):
    l = max(l,max(zalgo(s[i:])))
print(l)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
def Zalgo2(S):
    N = len(S)
    A = [0]*N
    A[0] = N
    i = 1
    j = 0
    while i < N:
        while i + j < N and S[j] == S[i + j]:
            j += 1
        A[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < N and k + A[k] < j:
            A[i + k] = A[k]
            k += 1
        i += k
        j -= k
    for i in range(N):
        A[i] = min(i, A[i])
    return A
print(max([max(Zalgo2(S[i:])[1:]) for i in range(N - 1)]))

Submission status: Time Limit Exceeded

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

def z_algo2(S):
    N = len(S)
    A = [0]*N 
    A[0] = N 
    j = 1 
    i = 1 
    for i in range(N):
        c = j + A[j] - i
        if c <= 0:
            k = 0
            while i + k < N and S[k] == S[i + k]:
                k += 1
            A[i] = k
            j = i
        elif c > 0:
            if A[i - j] == c:
                k = 0
                while i + k + c < N and S[c + k] == S[i + c + k]:
                    k += 1
                A[i] = c + k
                j = i
            elif A[i - j] > c:
                A[i] = c
                j = i
            else:
                A[i] = A[i - j]
    for i in range(N):
        A[i] = min(i, A[i])
    return A

print(max([max(z_algo2(S[i:])[1:]) for i in range(N - 1)]))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S = input()
l, r = 0, N

def t(n):
  for i in range(0, N-n):
    s = S[i:i+n]
    if s in S[i+n:]:
      return True
  return False

while l+1<r:
  m = (l+r)//2
  if t(m):
    l=m
  else:
    r=m

print(l)

Submission status: Time Limit Exceeded

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

    dp = [[0] * (N + 1) for _ in range(N + 1)]
    result = 0
    l = list(range(N - 1, -1, -1))
    for i in l:
        dpi = dp[i]
        dpi1 = dp[i + 1]
        for j in l:
            if S[i] == S[j]:
                t = dpi1[j + 1] + 1
                dpi[j] = t
                ji = j - i
                if t > ji:
                    t = ji
                if t > result:
                    result = t
    print(result)


main()

Submission status: Time Limit Exceeded

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

result = 0
for i in range(N - 1, 0, -1):
    if i < result:
        break
    t = 0
    for j in range(N - i):
        if S[j] == S[j+i]:
            t += 1
            if t > result:
                result = t
            if t == i:
                break
        else:
            t = 0

print(result)

Submission status: Time Limit Exceeded

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

ms = 0
for i in range(1, N):
    ts = 0
    for j in range(N - i):
        if S[j] == S[j+i]:
            ts += 1
            if ts > ms:
                ms = ts
            if ts == i:
                break
        else:
            ts = 0
print(ms)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    S = input()
    dp = [[0] * (N + 1) for _ in range(N + 1)]
    for i in range(N - 1, -1, -1):
        dpi = dp[i]
        dpi1 = dp[i + 1]
        for j in range(N - 1, -1, -1):
            if S[i] != S[j]:
                dpi[j] = 0
            else:
                dpi[j] = dpi1[j + 1] + 1
    result = 0
    for i in range(N):
        dpi = dp[i]
        for j in range(i + 1, N):
            t1 = dpi[j]
            t2 = j - i
            if t1 > t2:
                t1 = t2
            if t1 > result:
                result = t1
    print(result)


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

Submission status: Time Limit Exceeded

Solution code:
import math

def Z_Algorithm(S, N):
    c = 0
    A = [0] * N
    res = 0
    flag = True
    for i in range(1,N):
        # print('else', i, c)
        j = max(0, c+A[c]-i)
        while i+j < N and S[j] == S[i+j] and j < i: j += 1
        A[i] = j
        c = i
        if res < j:
            res = j
    return res

def solve():
    N = int(input())
    S = input()
    result = 0
    for i in range(N//2+1):
        Z = Z_Algorithm(S[i:], N-i)

        if result < Z:
            result = Z
            
        if result == math.ceil(N/2):
            break
        
    print(result)
    
solve()

Submission status: Time Limit Exceeded

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

#print(r)

maxV=0
for i in range(n):
  for j in  range(n):
    ii=n-1-i
    jj=n-1-j
    if s[ii]==s[jj]:
      r[ii][jj]=min(r[ii+1][jj+1]+1,abs(ii-jj))
      maxV=max(maxV,r[ii][jj])

print(maxV)

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input()) #文字列長
S = input()      #文字列
lst = []         #一致した文字列長

if N < 2:
    exit()

if not len(S) == N:
    exit()

while N >= 2:
#文字列検索　繰り返し回数
    h = math.ceil((N-1)/2)
    #文字列を抽出
    for i in range(h):
        p_str = S[0:i+1]
        #文字列検索
        res = p_str in S[i+1:N]
        if res == True:
            lst.append(int(len(p_str)))
    #一番左の文字を1文字消す
    S = S[1:]
    #文字列長からマイナス1
    N = N - 1
if not lst:
    print(0)
    exit()
    
print(max(lst))

Submission status: Time Limit Exceeded

Solution code:
def z_advanced(s, Z_max):
    """An advanced computation of Z-values of a string."""

    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
                
        Z_max = max(Z_max, min(k, Z[k]))  # check_k_zk()を参考のこと
    
    # return Z, Z_max
    return Z_max
  
N = int(input())
S = input()
Z_max = 0
for i in range(N):
    Z_max = z_advanced(S[i:], Z_max)

print(Z_max)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
 
solarr =[]
for i in range(n):
    solarr.append(0)
    if i == 0:
        continue
    head = s[i]
    subarr = s[:i]
    idxarr = []
    count = subarr.count(head)
    if count == 0:
        continue
    for j in range(count):
        if j == 0:
            idxarr.append(subarr.index(head))
        else:
            idxarr.append(subarr[idxarr[-1]+1:].index(head) + idxarr[-1]+1)
    j = 0
    tmparr = idxarr[:]
    while idxarr != []:
        j += 1
        if i+j >= n:
            break
        for k,l in enumerate(idxarr):
            if l+j >= i:
                tmparr.remove(l)
                continue
            if subarr[l+j] != s[i+j]:
                tmparr.remove(l)
        idxarr = tmparr[:]
    solarr[i] += j
        
print(max(solarr))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
 
solarr =[]
for i in range(n):
    solarr.append(0)
    if i == 0:
        continue
    head = s[i]
    subarr = s[:i]
    idxarr = []
    count = subarr.count(head)
    if count == 0:
        continue
    for j in range(count):
        if j == 0:
            idxarr.append(subarr.index(head))
        else:
            idxarr.append(subarr[idxarr[-1]+1:].index(head) + idxarr[-1]+1)
    j = 0
    tmparr = idxarr[:]
    while idxarr != []:
        j += 1
        if i+j >= n:
            idxarr = []
        for k,l in enumerate(idxarr):
            if l+j >= i:
                tmparr.remove(l)
                continue
            if subarr[l+j] != s[i+j]:
                tmparr.remove(l)
        idxarr = tmparr[:]
    solarr[i] += j
        
print(max(solarr))

Submission status: Time Limit Exceeded

Solution code:
# E - Who Says a Pun?
n = int(input())
s = input()

list = [[0 for i in range(n+5)] for j in range(n+5)]

for i in reversed(range(0, n)):
    for j in reversed(range(0, n)):
        if(i < j):
            if s[i] != s[j]: list[i][j] = 0
            else: list[i][j] = list[i+1][j+1] + 1

a = 0
for i in reversed(range(n)):
    for j in reversed(range(n)):
        if(i > j):continue
        now = min(list[i][j], j-i)
        a = max(now, a)

print(a)

Submission status: Time Limit Exceeded

Solution code:
class RollingHash:
    def __init__(self, s: str, base: int=1007, mod: int=10**9+7):
        self.s = s
        self.n = len(s)
        self.base = base
        self.mod = mod

        # preprocess
        self.hash_cum = [0] * (self.n + 1) # hash_cum[i] = (hash of s[:i])
        self.base_pow = [1] * (self.n + 1) # base_pow[i] = base ** i
        for i in range(self.n):
            self.hash_cum[i+1] = (self.hash_cum[i] * base + ord(s[i])) % mod
            self.base_pow[i+1] = (self.base_pow[i] * base) % mod

    def get_hash(self, l: int, r: int) -> int:
        hash_val = self.hash_cum[r] - self.hash_cum[l] * self.base_pow[r-l] % self.mod
        if hash_val < 0:
            hash_val += self.mod
        return hash_val


class RollingHashMulti:
    def __init__(self, s: str, base_list: list=[1007, 2009], mod_list: list=[10**9+7, 10**9+9]):
        self.n = len(base_list)
        self.base_list = base_list
        self.rh_list = [RollingHash(s, base_list[i], mod_list[i]) for i in range(self.n)]

    def get_hash(self, l: int, r: int) -> tuple:
        return tuple( self.rh_list[i].get_hash(l, r) for i in range(self.n) )




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

rh = RollingHashMulti(s)

def check(x):
    for i in range(n-2*x+1):
        for j in range(i+x, n-x+1):
            if rh.get_hash(i, i+x) == rh.get_hash(j, j+x):
                return True
    return False


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

print(lb)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import Counter
n = int(input())
s = input()
# n=10**3
# s='abcab'*(10**3)
count = 0
for le in range(1, n//2+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:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

Submission status: 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[j:].find(s[i:j])!=-1:
            # print(s[j:].find(s[i:j]))
            ans=max(ans,len(s[i:j]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N =int(input())
moji = input()
 
ans = 0
for i in range(N):
  k = 1
  while(True):
    if(moji[i:i+k] in moji[i+k:]):
      k += 1
    else:
      break
  ans = max(ans, k-1)

print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(N):
  k = 1
  while(k<N):
    if(moji[i:i+k] in moji[i+k:]):
      k += 1
    else:
      break
  ans = max(ans, k-1)

print(ans)

Submission status: Time Limit Exceeded

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

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

print(mx)

Submission status: Time Limit Exceeded

Solution code:
N= int(input().rstrip())
mojilist = list(input().rstrip())

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:

N= int(input().rstrip())
mojilist = list(input().rstrip())


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

for i in reversed(range(0,N)):
  for j in reversed(range(0,N)):
    if mojilist[i] != mojilist[j]:
      dp[j][i] = 0
    else:
      dp[j][i] = dp[j+1][i+1] + 1
      
maximumlist = []
for i in range(N):
  for j in range(N):
    maximumlist.append(min(dp[i][j], j-i))

print(max(maximumlist))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class RollingHash(object):
    """
    construct: O(N)
    get_hash: O(1)
    LCP: O(logN)
    """
    def __init__(self,S,m1=10**9+9,b1=2009,m2=10**9+7,b2=1007):
        """
        S: string
        m1>m2: prime sufficiently large
        b1,b2: base 0<bi<mi
        """
        assert m1>m2 and 0<b1<m1 and 0<b2<m2
        n=len(S)
        self.__n=n
        self.__m1=m1
        self.__m2=m2
        self.__H1,self.__H2=[0]*(n+1),[0]*(n+1)
        self.__P1,self.__P2=[1]*(n+1),[1]*(n+1)
        for i,s in enumerate(S):
            self.__H1[i+1]=(self.__H1[i]*b1+ord(s))%m1
            self.__H2[i+1]=(self.__H2[i]*b2+ord(s))%m2
            self.__P1[i+1]=self.__P1[i]*b1%m1
            self.__P2[i+1]=self.__P2[i]*b2%m2
        self.__d=0
        while(m1):
            m1//=10
            self.__d+=1

    @property
    def len(self):
        return self.__n

    def hash(self,l,r=None):
        """
        l,r: int (0<=l<=r<=n)
        return hash of S[l:r]
        """
        if r is None: r=self.len
        assert 0<=l<=r<=self.len
        return (self.__H1[r]-self.__P1[r-l]*self.__H1[l]%self.__m1)%self.__m1*(10**self.__d)+(self.__H2[r]-self.__P2[r-l]*self.__H2[l]%self.__m2)%self.__m2

    def LCP(self,l1,r1=None,rh2=None,l2=0,r2=None):
        if r1 is None: r1=self.len
        if rh2 is None: rh2=self
        if r2 is None: r2=rh2.len
        assert 0<=l1<=r1<=self.len and 0<=l2<=r2<=rh2.len
        L=0
        R=min(r1-l1,r2-l2)
        if self.hash(l1,l1+R)==rh2.hash(l2,l2+R): return R
        while(R-L>1):
            H=(L+R)//2
            if self.hash(l1,l1+H)==rh2.hash(l2,l2+H): L=H
            else: R=H
        return L

def resolve():
    n=int(input())
    S=input()
    rh=RollingHash(S)
    ans=0
    for i in range(n):
        for j in range(i+1,n):
            ans=max(ans,min(j-i,rh.LCP(l1=i,l2=j)))
    print(ans)
resolve()

Submission status: Time Limit Exceeded

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

#N = int(input())
#S = str(input())
#N = 13
#S = "strangeorange"
 
lb = 0
ub = N //2 + 1
flag = False
while (ub - lb > 1):
    mid = (lb + ub) // 2
    s = [""]*(N - 2*mid + 1)
    for i in range(N - 2*mid + 1):
        s[i] = S[i:mid+i]
        if S[mid+i:i+2*mid] in s:
            flag = True
            break
        else:
            flag = False
    if flag == True:
        lb = mid
    else:
        ub = mid
print(lb)

Submission status: Time Limit Exceeded

Solution code:
N = 13
S = "strangeorange"

#N = int(input())
#S = str(input())

N = int(input())
S = str(input())
#N = 13
#S = "strangeorange"
 
lb = 0
ub = N //2 + 1
flag = False
while (ub - lb > 1):
    mid = (lb + ub) // 2
    s = []
    for i in range(N - 2*mid + 1):
        if not (S[i:mid+i] in s):
            s.append(S[i:mid+i])
        if S[mid+i:i+2*mid] in s:
            flag = True
            break
        else:
            flag = False
    if flag == True:
        lb = mid
    else:
        ub = mid
print(lb)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
S_len = int(len(S) / 2)
tag_len = 0

for i in range(N-1):
  s = S[i:]
  for j in range(1, len(s)):
    target = s[j:]
    if target == s[:len(target)]:
      if tag_len < len(target) & len(target) <= S_len:
        tag_len = len(target)
print(tag_len)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
dp = [[0]*5001 for _ in range(5001)]
 
def solve(s1, s2):
  for i in range(len(s1)):
    for j in range(len(s2)):
      if s1[i] == s2[j]:
        dp[i+1][j+1] = dp[i][j] + 1
      else:
        dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
  return dp[len(s1)][len(s2)]
 
ans = 0
for i in range(1, N):
  ans = max(ans, solve(S[0:i], S[i:]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
stringCount = int(input())
targetString = input()
 
def z_algorithm(str):
  '''
  引数として渡された文字列の各 index(以下i) について
  「str と str[i:|str|-1] の最長共通接頭辞の長さ」を記録した配列 result を返します。
  
  計算量 : O(|S|) 
  Parameters
  ----------
  str : string
    対象文字列
  
  Returns
  -------
  result : array[int]
    strとstr[index:]の最長共通接頭辞の長さ
  
  '''
  strLength = len(str)
  result = [0] * strLength
  # 結果の一番最初は対象の文字列全体マッチする
  result[0] = strLength
  i = 1
  j = 0
  
  while i < strLength:
    while (i + j) < strLength and str[j] == str[j+i]:
      j += 1
    if j > (strLength // 2):
      result[i] = 0
    else:
      result[i] = j
  return result
 
response = 0
for i in range(len(targetString)):
  str = targetString[i:]
  result = z_algorithm(str)
  result[0] = 0
  for i in range(len(result)):
    if (i+1) < result[i]:
      result[i] = 0
  maxCount = max(result)
  if response < maxCount:
    response = maxCount
 
print(response)

Submission status: Time Limit Exceeded

Solution code:
'''Z algorithm https://snuke.hatenablog.com/entry/2014/12/03/214243'''
N = int(input())
S = input()
A = [0]*N

def calc():
  ans = 0
  for l1 in range(N):
    A[0] = 0
    l2 = l1+1
    len_ = 0;
    while l2 < N:
      # S[l1:l2] と S[l2:] が何文字目まで等しいか調べる
      while l2+len_< N and l1+len_ < l2 and S[l1+len_] == S[l2+len_]:
        # print(len_, S[l1+len_], S[l2+len_])
        len_ += 1

      A[l2] = len_;
      if len_ == 0:
        l2 += 1
        continue
      k = 1;
      # 既に計算した部分は足す
      while l2+k < N and k+A[k] < len_:
        A[l2+k] = A[k]
        k += 1
      l2 += k
      len_ -= k;
    # print(A)
    ans = max(max(A), ans)
  return ans

print(calc())

Submission status: Time Limit Exceeded

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N = I()
    S = ST()
    
    def z_algorithm(S):
        N = len(S)
        A = [N] + [0] * (N-1)
        left = 1
        length = 0
        while left < N:
            while left+length<N and S[length] == S[left+length]:
                length += 1
            A[left] = length
            if not length:
                left += 1
                continue
            k = 1
            while k+left<N and k+A[k]<length:
                A[left+k] = A[k]
                k += 1
            
            left += k
            length -= k

        return A

    ans = 0
    for i in range(N):
        A = z_algorithm(S[i:])
        for i,a in enumerate(A):
            ans = max(ans, min(a,i))
    print(ans)
    


    """
    # めぐる式二分探索
    def meguru_bisect(ok, ng):
        while abs(ok - ng) > 1:
            mid=(ok + ng) // 2
            if is_ok(mid):
                ok=mid
            else:
                ng=mid
        return ok

    def is_ok(l):
        for i,s in enumerate(S[:-l + 1]):
            st = S[i:i+l]
            if st in S[i+l:]:
                return True
        return False

    ans = meguru_bisect(0,len(S))
    print(ans)
    """


if __name__ == '__main__':
    main()