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:
#!/usr/bin/env python3

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    

    from random import randint
    class RollingHash:
        def __init__(self, s):
            self.s = s    # パターン探索を行われる側の文字列
            self.size = len(s)
            self.hashmod = 2 ** 64 - 1
            self.base = randint(2 ** 10, 2 ** 11)
            self.hash_list = self._make_rolling_hash_list()

        def _make_rolling_hash_list(self):
            hash_list = [0] * (self.size + 1)    # [h(s[0:0]), h(s[0:1]), h(s[0:2]), h(s[0:3]), ..., h(s[0:size])]
            prev = 0
            for i in range(1, self.size + 1):
                hash_num = (prev * self.base + ord(self.s[i-1])) % self.hashmod
                hash_list[i] = hash_num
                prev = hash_num
            return hash_list

        def calc_hash_str(self, pattern):
            """
            pattern のハッシュを計算
            """
            n = len(pattern)
            hash_num = 0
            for i in range(n):
                hash_num = (hash_num + ord(pattern[i]) * pow(self.base, n-1-i, self.hashmod)) % self.hashmod
            return hash_num
        
        def calc_interval_hash(self, i, j):
            """
            s[i:j] のハッシュを計算
            """
            return (self.hash_list[j] - self.hash_list[i] * pow(self.base, (j - i))) % self.hashmod

    
    n = ii()
    s = input()
    if len(list(set(list(s)))) == n:
        print(0)
    else:
        # main
        rolling = RollingHash(s)
        updated = True
        ans = 0
        for span in range(1, (n // 2) + 1):
            if not updated:
                break
            updated = False
            d = dict()
            for i in range(n - span + 1):
                j = i + span
                h = rolling.calc_interval_hash(i, j)
                try:
                    right = d[h]
                    if right <= i:
                        ans = span
                        updated = True
                except KeyError:
                    d[h] = j
                if updated:
                    break
        print(ans)



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    

    from random import randint
    class RollingHash:
        def __init__(self, s):
            self.s = s    # パターン探索を行われる側の文字列
            self.size = len(s)
            self.hashmod = 2 ** 64 - 1
            self.base = randint(2 ** 10, 2 ** 11)
            self.hash_list = self._make_rolling_hash_list()

        def _make_rolling_hash_list(self):
            hash_list = [0] * (self.size + 1)    # [h(s[0:0]), h(s[0:1]), h(s[0:2]), h(s[0:3]), ..., h(s[0:size])]
            prev = 0
            for i in range(1, self.size + 1):
                hash_num = (prev * self.base + ord(self.s[i-1])) % self.hashmod
                hash_list[i] = hash_num
                prev = hash_num
            return hash_list

        def calc_hash_str(self, pattern):
            """
            pattern のハッシュを計算
            """
            n = len(pattern)
            hash_num = 0
            for i in range(n):
                hash_num = (hash_num + ord(pattern[i]) * pow(self.base, n-1-i, self.hashmod)) % self.hashmod
            return hash_num
        
        def calc_interval_hash(self, i, j):
            """
            s[i:j] のハッシュを計算
            """
            return (self.hash_list[j] - self.hash_list[i] * (self.base ** (j - i))) % self.hashmod

    
    n = ii()
    s = input()
    if len(list(set(list(s)))) == n:
        print(0)
    else:
        # main
        rolling = RollingHash(s)
        updated = True
        ans = 0
        for span in range(1, (n // 2) + 1):
            if not updated:
                break
            updated = False
            d = dict()
            for i in range(n - span + 1):
                j = i + span
                h = rolling.calc_interval_hash(i, j)
                try:
                    right = d[h]
                    if right <= i:
                        ans = span
                        updated = True
                except KeyError:
                    d[h] = j
                if updated:
                    break
        print(ans)



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    

    from random import randint
    class RollingHash:
        def __init__(self, s):
            self.s = s    # パターン探索を行われる側の文字列
            self.size = len(s)
            self.hashmod = 2 ** 64 - 1
            self.base = randint(2 ** 10, 2 ** 11)
            self.hash_list = self._make_rolling_hash_list()

        def _make_rolling_hash_list(self):
            hash_list = [0] * (self.size + 1)    # [h(s[0:0]), h(s[0:1]), h(s[0:2]), h(s[0:3]), ..., h(s[0:size])]
            prev = 0
            for i in range(1, self.size + 1):
                hash_num = (prev * self.base + ord(self.s[i-1])) % self.hashmod
                hash_list[i] = hash_num
                prev = hash_num
            return hash_list

        def calc_hash_str(self, pattern):
            """
            pattern のハッシュを計算
            """
            n = len(pattern)
            hash_num = 0
            for i in range(n):
                hash_num = (hash_num + ord(pattern[i]) * pow(self.base, n-1-i, self.hashmod)) % self.hashmod
            return hash_num
        
        def calc_interval_hash(self, i, j):
            """
            s[i:j] のハッシュを計算
            """
            return (self.hash_list[j] - self.hash_list[i] * (self.base ** (j - i))) % self.hashmod

    
    n = ii()
    s = input()
    if len(list(set(list(s)))) == n:
        print(0)
    else:
        # main
        rolling = RollingHash(s)
        updated = True
        ans = 0
        for span in range(1, (n // 2) + 1):
            if not updated:
                break
            updated = False
            d = defaultdict(list)
            for i in range(n - span + 1):
                j = i + span
                h = rolling.calc_interval_hash(i, j)
                for right in d[h]:
                    if right <= i:
                        ans = span
                        updated = True
                d[h].append(j)
                if updated:
                    break
        print(ans)



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def rolling_hash(s):
    l = len(s)
    h = [0]*(l + 1)
    v = 0
    for i in range(l):
        h[i+1] = v = (v * base + ord(s[i])) % mod
    return h
# RH前に、必要な長さの最大値分のpow-tableを計算しておく
def setup_pw(l):
    pw = [1]*(l + 1)
    v = 1
    for i in range(l):
        pw[i+1] = v = v * base % mod
    return pw
def get(h, b, l, r):
    return (h[r] - h[l] * b[r-l]) % mod

N = int(input())
S = input()
mod = 1000000007
base = 37
h1 = rolling_hash(S)
b1 = setup_pw(N)
Max = N // 2
broke = False
for i in range(Max-1):
    for j in range(N-2*(Max-i)+1):
        for k in range(N-2*(Max-i)-j+1):
            if get(h1,b1,j,(Max-i)+j) == get(h1,b1,j+(Max-i)+k,2*(Max-i)+j+k):
                print(Max-i)
                broke = True
                break
        if broke == True:
            break
    if broke == True:
        break
if broke == False:
    print('0')

Submission status: Time Limit Exceeded

Solution code:
def rolling_hash(s):
    l = len(s)
    h = [0]*(l + 1)
    v = 0
    for i in range(l):
        h[i+1] = v = (v * base + ord(s[i])) % mod
    return h
# RH前に、必要な長さの最大値分のpow-tableを計算しておく
def setup_pw(l):
    pw = [1]*(l + 1)
    v = 1
    for i in range(l):
        pw[i+1] = v = v * base % mod
    return pw
def get(h, b, l, r):
    return (h[r] - h[l] * b[r-l]) % mod

N = int(input())
S = input()
mod = 1000000007
base = 37
h1 = rolling_hash(S)
b1 = setup_pw(N)
base = 401
h2 = rolling_hash(S)
b2 = setup_pw(N)
Max = N // 2
broke = False
for i in range(Max-1):
    for j in range(N-2*(Max-i)+1):
        for k in range(N-2*(Max-i)-j+1):
            if get(h1,b1,j,(Max-i)+j) == get(h1,b1,j+(Max-i)+k,2*(Max-i)+j+k) and get(h2,b2,j,(Max-i)+j) == get(h2,b2,j+(Max-i)+k,2*(Max-i)+j+k):
                print(Max-i)
                broke = True
                break
        if broke == True:
            break
    if broke == True:
        break
if broke == False:
    print('0')

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N = int(input())
S = input()
ans = 0
for i in range(1, N+1):
    d = defaultdict(list)
    for j in range(N - i + 1):
        d[S[j:j+i]].append(j)
    # print(d)
    for l in d.values():
        for j in range(len(l) - 1):
            if l[j] + i <= l[j + 1]:
                ans = max(ans, i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

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

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

ans = 0

for l2 in range(1, N):
    same_len = 0
    for i in range(N):
        if N - 1 < l2 + i:
            continue

        if S[i] == S[l2 + i]:
            same_len += 1
        else:
            same_len = min(l2, same_len)
            ans = max(ans, same_len)
            same_len = 0
    same_len = min(l2, same_len)
    ans = max(same_len, ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
N=int(sys.stdin.readline().strip())
S=sys.stdin.readline().strip()

def judge(n):   #n:文字列の長さで条件を満たせるかをジャッジする
    for i in range(N):
        if N<i+n:  continue
        s=S[i:i+n]
        if s in S[i+n:]:
            return True
    else:
        return False

h=N
l=0
while h-l!=1:
    m=(h+l)/2
    if judge(m):    #条件を見たしていれば、下限lをmの位置まで引き上げる
        l=m
    else:    #条件を見たしていなければ、上限hをmの位置まで引き下げる
        h=m
print l

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

def main():
    n = int(input())
    s = input()
    x = 1

    sn = [ord(c) - 96 + x for c in s]

    lmax = n // 2
    m1 = 10 ** 9 + 7
    m2 = 2 ** 61 - 1

    ans = 0

    for l in range(1, lmax + 1):
        appeared = set()
        diff = pow(m1, l - 1, m2)

        h_init = 0
        for i in range(l):
            h_init += sn[i] * pow(m1, l - 1 - i, m2)

        hashlist = [0] * n
        hashlist[0] = h_init
        h = h_init

        for i in range(l, n):
            h -= sn[i-l] * diff
            h *= m1
            h += sn[i]
            h %= m2
            hashlist[i] = h
            if i - l >= 0:
                appeared.add(hashlist[i-l])
            if h in appeared:
                ans = l
                break

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def z_alg(S):
  N=len(S)
  Z=[N]+[0]*(N-1)
  i,j=1,0
  while i<N:
    while i+j<N and S[j]==S[i+j]:
      j+=1
    if not j:
      i+=1
      continue
    Z[i]=j
    k=1
    while N-i>k and k<j-Z[k]:
      Z[i+k]=Z[k]
      k+=1
    i+=k
    j-=k
  return Z

answer=0
for i in range(N):
  zlist=z_alg(S[i:])
  #print(i,S[i:],zlist)
  for j in range(N-i):
    if j>=zlist[j] and answer<zlist[j]:
      answer=zlist[j]
      
print(answer)

Submission status: Time Limit Exceeded

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

def search_k(k):
  if k==0:
    return True
  elif k in search_dic:
    return search_dic[k]
  
  for i in range(N-2*k+1):
    for j in range(i+k,N-k+1):
      for kk in range(k):
        if S[i+kk]!=S[j+kk]:
          break
      else:
        search_dic[k]=True
        return True
      
  search_dic[k]=False
  return False

search_dic={}
l,r=0,N//2
while(l<=r):
  mid=(l+r)//2
  
  res1=search_k(mid)
  res2=search_k(mid+1)
  if res1 and not res2:
    print(mid)
    sys.exit(0)
  elif res1:
    l=mid+1
  else:
    r=mid-1

Submission status: Time Limit Exceeded

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

def search_k(k):
  for i in range(N-2*k+1):
    for j in range(i+k,N-k+1):
      for kk in range(k):
        if S[i+kk]!=S[j+kk]:
          break
      else:
        return True
      
  return False

for k in reversed(range(1,N//2+1)):
  if search_k(k):
    print(k)
    break
else:
  print(0)

Submission status: Time Limit Exceeded

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

for k in reversed(range(1,N//2+1)):
  for i in range(N-2*k+1):
    S1=S[i:i+k]
    for j in range(i+k,N-k+1):
      S2=S[j:j+k]
      #print(k,S1,S2)
      if S1==S2:
        print(k)
        sys.exit(0)
print(0)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
S=list(input())
A=[[0]*n for i in range(n)]
for i in range(n-1):
  for j in range(i+1,n):
    if S[i]==S[j]:
      A[i][j]=1
dp=[[0]*(n+1) for i in range(n+1)]#i文字目まで、j文字目までの長さ
for i in range(1,n):
  for j in range(i+1,n+1):
    if A[i-1][j-1]==1:
      if j-i<dp[i-1][j-1]+1:
        dp[i][j]=dp[i-1][j-1]
      else:
        dp[i][j]=dp[i-1][j-1]+1
ans=0
for i in range(n+1):
  for j in range(n+1):
    if dp[i][j]>ans:
      ans=dp[i][j]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#Z[i]:length of the longest list starting from S[i] which is also a prefix of S
#O(|S|)
def Z_algorithm(s):
    N = len(s)
    Z_alg = [0]*N

    Z_alg[0] = N
    i = 1
    j = 0
    while i < N:
        while i+j < N and s[j] == s[i+j]:
            j += 1
        Z_alg[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k + Z_alg[k]<j:
            Z_alg[i+k] = Z_alg[k]
            k += 1
        i += k
        j -= k
    return Z_alg

N=int(input())
S=input()
S=[S[i] for i in range(0,N)]

def condition(num):
    if num==0:
        return True
    for i in range(0,N-2*num+1):
        s=S[i:]
        data=Z_algorithm(s)
        for j in range(num,len(data)):
            if data[j]>=num:
                return True

    return False

start=0
end=N
while end-start>1:
    test=(end+start)//2
    if condition(test):
        start=test
    else:
        end=test

if condition(end):
    print(end)
else:
    print(start)

Submission status: Time Limit Exceeded

Solution code:
#Z[i]:length of the longest list starting from S[i] which is also a prefix of S
#O(|S|)
def Z_algorithm(s):
    N = len(s)
    Z_alg = [0]*N

    Z_alg[0] = N
    i = 1
    j = 0
    while i < N:
        while i+j < N and s[j] == s[i+j]:
            j += 1
        Z_alg[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k + Z_alg[k]<j:
            Z_alg[i+k] = Z_alg[k]
            k += 1
        i += k
        j -= k
    return Z_alg

N=int(input())
S=input()
S=[S[i] for i in range(0,N)]

def condition(num):
    if num==0:
        return True
    for i in range(0,N-2*num+1):
        s=S[i:i+num]
        t=S[i+num:]
        data=Z_algorithm(s+['?']+t)
        for j in range(num+1,len(data)):
            if data[j]==num:
                return True

    return False

start=0
end=N
while end-start>1:
    test=(end+start)//2
    if condition(test):
        start=test
    else:
        end=test

if condition(end):
    print(end)
else:
    print(start)

Submission status: Time Limit Exceeded

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


class RMQ:
    inf = 10 ** 9 + 7

    def __init__(self, x):
        # 1-index
        self.n = 2 ** len(x).bit_length()
        self.dat = [self.inf] * (2 * self.n - 1)
        
        for k, v in enumerate(x):
            self.update(k, v)
        
    def update(self, k, v):
        k += self.n - 1
        self.dat[k] = v
        while k > 0:
            k = (k - 1) // 2
            self.dat[k] = min(self.dat[k * 2 + 1], self.dat[k * 2 + 2])
            
    def query(self, a, b, k=0, l=0, r=None):
        # Retrun min [a, b)
        if r is None:
            r = self.n
        
        if b <= l or r <= a:
            return self.inf
        
        if a <= l and r <= b:
            return self.dat[k]
        
        vl = self.query(a, b, k * 2 + 1, l, (l + r) // 2)
        vr = self.query(a, b, k * 2 + 2, (l + r) // 2, r)
        
        return min(vl, vr)
            
    def __repr__(self):
        return ', '.join([str(v) for v in self.dat])


class SuffixArray:
    """Manber & Myers `(O(n log^2 n))`."""
    def __init__(self, s):
        if not isinstance(s, str):
            raise ValueError("Input must be string")

        # Input array
        self.array = s
        self.len = len(s) + 1

        # Suffix array
        self.sa = list(range(self.len))
        self.rank = list(map(ord, self.array)) + [-1]

        # Longest Common Prefix
        self.lcp = [-1] * self.len

        # RMQ
        self.rmq = None

        # Initialize
        self._construct()
        self._calc_lcp()
        self._init_rmq()

    def __getitem__(self, index):
        return self.array[self.sa[index]:]

    def __len__(self):
        return self.len

    def _construct(self):
        """Sorts 2k chars."""
        n = self.len
        k = 1
        while k <= n:
            self.sa.sort(key=lambda x: self._key(x, k))

            tmp = [0] * n
            for i in range(1, n):
                tmp[self.sa[i]] = (tmp[self.sa[i - 1]]
                                   + int(self.compare(i - 1, i, k)))

            self.rank = tmp[:]
            k *= 2

    def _key(self, i, k):
        """Returns key for sort."""
        v1 = self.rank[i]
        v2 = self.rank[i + k] if i + k < self.len else -1
        return (v1, v2)

    def compare(self, i, j, k):
        key1 = self._key(self.sa[i], k)
        key2 = self._key(self.sa[j], k)

        # Compare rank[i] and rank[j]
        if key1[0] != key2[0]:
            return key1[0] < key2[0]

        # Compare rank[i + k] and rank[j + k]
        return key1[1] < key2[1]

    def _calc_lcp(self):
        n = self.len
        for i in range(n):
            self.rank[self.sa[i]] = i

        self.lcp[0] = 0
        h = 0
        for i in range(n - 1):
            j = self.sa[self.rank[i] - 1]

            if h > 0:
                h -= 1
            while j + h < n - 1 and i + h < n - 1:
                if self.array[j + h] != self.array[i + h]:
                    break
                h += 1

            self.lcp[self.rank[i] - 1] = h
            
    def _init_rmq(self):
        lcp = [self.lcp[self.rank[i]] for i in range(self.len)]
        self.rmq = RMQ(lcp)

    def get_lcp(self, i, j):
        if self.rank[i] >= self.rank[j]:
            i, j = j, i

        return self.rmq.query(self.rank[i], self.rank[j])


sa = SuffixArray(S)
res = 0
for i in range(1, len(sa)):
    for j in range(i + 1, len(sa)):
        lcp = sa.get_lcp(i, j)
        res = max(res, lcp)

print(res)

Submission status: Time Limit Exceeded

Solution code:
import re
N=int(input());S=input()

def same_check(index,number):
    while index-number>=0:
        pattern=S[index-number:index+1]
        match_list=re.findall(pattern,S[:index+1])
        if len(match_list)==1:
            return number
        else:
            number+=1

number=0
for i in range(N):
    number=same_check(i,number)
print(number)

Submission status: Time Limit Exceeded

Solution code:
def main():
    for l in range(n, 0, -1):
        D = {}
        for i in range(n-l+1):
            s = S[i:i+l]
            try:
                if D[s] + l <= i:
                    return l
            except:
                D[s] = i
    return 0


n = int(input())
S = input()
print(main())

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

B = 10 ** 9 + 7
ans = 0
for l in range(1, N + 1):
    t = B ** l
    
    # First hash
    ah = 0
    bh = 0
    for i in range(l):
        ah = ah * B + ord(S[i])
        bh = bh * B + ord(S[i])
        
    # Roll
    ctr = defaultdict(list)
    for i in range(N - l + 1):
        if not ctr[ah] or ctr[ah][-1] + l <= i:
            ctr[ah].append(i)
        
        if i < N - l:
            ah = ah * B + ord(S[i + l]) - ord(S[i]) * t

    # Check appearance number
    if max(map(len, ctr.values())) >= 2:
        ans = l

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
def f(m):
    res = False
    hs = []
    for i in range(0,N-m+1):
        hs.append(hash(S[i:i+m]))
    for i in range(0,N-m+1):
        if hash(S[i:i+m]) in hs[i+m:]:
            res = True
            break
    return res

l = 0
r = N//2+1
while (r-l)>1:
    mid = (r+l)//2
    if f(mid):
        l = mid
    else:
        r = mid
print(l)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
dp = [[0]*N for _ in range(N)]
ans = 0
for i in range(N-1,0,-1):
    for j in range(i-1,-1,-1):
        if S[i] == S[j]:
            if i < N-1 and j < i-1:
                dp[i][j] = min(dp[i+1][j+1]+1, i-j)
            else:
                dp[i][j] = 1
        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
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j] and i != j:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        if A[i] >= N - i - 1:
        	return A[i]
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return 0

ans = 0
for i in range(n-1):
	res = z_algo(s[i:])
	#print(res)
	#tmp = max(res[1:])
	ans = max(ans, res)

print(ans)