Problem:


Score : 500 points

Problem Statement

Given is a string S of length N.

Find the maximum length of a non-empty string that occurs twice or more in S as contiguous substrings without overlapping.

More formally, find the maximum positive integer len such that there exist integers l_1 and l_2 ( 1 \leq l_1, l_2 \leq N - len + 1 ) that satisfy the following:

l_1 + len \leq l_2

S[l_1+i] = S[l_2+i] (i = 0, 1, ..., len - 1)

If there is no such integer len, print 0.

Constraints

2 \leq N \leq 5 \times 10^3

|S| = N

S consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the maximum length of a non-empty string that occurs twice or more in S as contiguous substrings without overlapping. If there is no such non-empty string, print 0 instead.

Sample Input 1

5
ababa

Sample Output 1

2

The strings satisfying the conditions are: a, b, ab, and ba. The maximum length among them is 2, which is the answer.
Note that aba occurs twice in S as contiguous substrings, but there is no pair of integers l_1 and l_2 mentioned in the statement such that l_1 + len \leq l_2.

Sample Input 2

2
xy

Sample Output 2

0

No non-empty string satisfies the conditions.

Sample Input 3

13
strangeorange

Sample Output 3

5



Sample input:
5
ababa


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
def 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)

ans = 0
for i in range(N // 2 + 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:
                ans = max(ans, len(opt))
                break
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)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():

    # *** 入力
    # N: 文字列の長さ
    # S: 文字列
    # *** 出力
    # sa[i]: SuffixArray
    N=int(input())
    S=input()

    import functools

    *SC, = map(ord, S+"$")

    *sa, = range(N)

    L = N + 1
    rh = [0]*(L + 1)
    md = [1]*(L + 1)
    MOD = 2147483647
    base = 37
    rev = pow(base, MOD-2, MOD)
    for i in range(1, L + 1):
        md[i] = md[i-1] * rev % MOD
    cA = ord('a')
    for i in range(L):
        rh[i+1] = (rh[i] * base + (SC[i] - cA)) % MOD

    # lcp(i, j): S[i:] と S[j:] の最長共通接頭語(LCP)の長さを求める
    def lcp(i, j):
        left = 0
        right = N+1 - max(i, j)
        v = (rh[i]-rh[j]) % MOD
        while left+1 < right:
            mid = (left + right) >> 1
            if (rh[i+mid]-rh[j+mid])*md[mid] % MOD == v:
                left = mid
            else:
                right = mid
        return left

    def cmp(a, b):
        k = lcp(a, b)
        return SC[a+k] - SC[b+k]
    sa.sort(key=functools.cmp_to_key(cmp))

    ans=0
    for i in range(N):
        for j in range(i+1,N):
            ans=max(ans,min(j-i,lcp(i,j)))

    print(ans)


resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():

    # Suffix Array (Manber & Myers) : O(n(logn)^2)
    class SuffixArray:
        def __init__(self, s):
            self.s = s
            self.n = len(s)

        # Suffix Array
        def suffix(self):
            s = self.s
            n = self.n
            rank = [0]*(n+1)
            sa = [0]*(n+1)
            tmp = [0]*(n+1)

            for i in range(n+1):
                sa[i] = i
                rank[i] = ord(s[i]) if i < n else -1

            k = 1
            def cmp_key(e): return (rank[e], rank[e+k] if e+k <= n else -1)
            while k <= n:
                sa.sort(key=cmp_key)
                tmp[sa[0]] = 0
                for i in range(1, n+1):
                    tmp[sa[i]] = tmp[sa[i-1]] + \
                        (cmp_key(sa[i-1]) < cmp_key(sa[i]))
                for i in range(n+1):
                    rank[i] = tmp[i]
                k *= 2

            self.sa = sa
            return sa

        # LCP Array
        def lcp(self):
            n = self.n
            s = self.s
            sa = self.sa
            lcp = [-1]*(n+1)
            rank = [0]*(n+1)
            for i in range(n+1):
                rank[sa[i]] = i

            h = 0
            lcp[0] = 0
            for i in range(n):
                j = sa[rank[i] - 1]
                if h > 0:
                    h -= 1
                while j+h < n and i+h < n and s[j+h] == s[i+h]:
                    h += 1
                lcp[rank[i] - 1] = h
            self.lcp = lcp
            return lcp

    # query(a, b): S[a:] と S[b:] の最長共通接頭語(LCP)の長さを求める
    N=int(input())
    S=input()
    # S = (文字列)
    # N = len(S)

    SA = SuffixArray(S)
    sa = SA.suffix()
    lcp = SA.lcp()
    N0 = 2**(N).bit_length()
    data = [0]*(2*N0)
    for i in range(N+1):
        data[i+N0-1] = lcp[i]
    for i in range(N0-2, -1, -1):
        data[i] = min(data[2*i+1], data[2*i+2])
    D = [0]*(N+1)
    for i, s in enumerate(sa):
        D[s] = i

    def query(a, b):
        L = D[a] + N0
        R = D[b] + N0
        if L > R:
            L, R = R, L
        s = N+1
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, data[R-1])

            if L & 1:
                s = min(s, data[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return s

    ans=0
    for i in range(N):
        for j in range(i+1,N):
            ans=max(ans,min(j-i,query(i,j)))

    print(ans)


resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():

    # Suffix Array (Manber & Myers) : O(n(logn)^2)
    class SuffixArray:
        def __init__(self, s):
            self.s = s
            self.n = len(s)

        # Suffix Array
        def suffix(self):
            s = self.s
            n = self.n
            rank = [0]*(n+1)
            sa = [0]*(n+1)
            tmp = [0]*(n+1)

            for i in range(n+1):
                sa[i] = i
                rank[i] = ord(s[i]) if i < n else -1

            k = 1
            def cmp_key(e): return (rank[e], rank[e+k] if e+k <= n else -1)
            while k <= n:
                sa.sort(key=cmp_key)
                tmp[sa[0]] = 0
                for i in range(1, n+1):
                    tmp[sa[i]] = tmp[sa[i-1]] + \
                        (cmp_key(sa[i-1]) < cmp_key(sa[i]))
                for i in range(n+1):
                    rank[i] = tmp[i]
                k *= 2

            self.sa = sa
            return sa

        # LCP Array
        def lcp(self):
            n = self.n
            s = self.s
            sa = self.sa
            lcp = [-1]*(n+1)
            rank = [0]*(n+1)
            for i in range(n+1):
                rank[sa[i]] = i

            h = 0
            lcp[0] = 0
            for i in range(n):
                j = sa[rank[i] - 1]
                if h > 0:
                    h -= 1
                while j+h < n and i+h < n and s[j+h] == s[i+h]:
                    h += 1
                lcp[rank[i] - 1] = h
            self.lcp = lcp
            return lcp

    # query(a, b): S[a:] と S[b:] の最長共通接頭語(LCP)の長さを求める
    N=int(input())
    S=input()
    # S = (文字列)
    # N = len(S)

    SA = SuffixArray(S)
    sa = SA.suffix()
    lcp = SA.lcp()
    N0 = 2**(N).bit_length()
    data = [0]*(2*N0)
    for i in range(N+1):
        data[i+N0-1] = lcp[i]
    for i in range(N0-2, -1, -1):
        data[i] = min(data[2*i+1], data[2*i+2])
    D = [0]*(N+1)
    for i, s in enumerate(sa):
        D[s] = i

    def query(a, b):
        L = D[a] + N0
        R = D[b] + N0
        if L > R:
            L, R = R, L
        s = N+1
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, data[R-1])

            if L & 1:
                s = min(s, data[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return s

    ans=0
    for i in range(N):
        for j in range(i,N):
            ans=max(ans,min(j-i,query(i,j)))

    print(ans)


resolve()

Submission status: Time Limit Exceeded

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

ans = 0
while S:
    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
        else:
            k = 1
            while k < j and k + Z[k] < j:
                Z[i + k] = Z[k]
                k += 1
            i += k
            j -= k    

    ans = max(ans, max(min(i, z) for i, z in enumerate(Z)))

    S = S[1:]
    N -= 1

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

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

    res = 0
    for i in range(n):
        for j in range(n):
            if i < j:
                now = min(dp[i][j], j - i)
                res = max(res, now)
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
from itertools import combinations

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


def resolve():
    n = int(input())
    s = input()
    D = Counter(s)
    idx = [[] for _ in range(26)]
    for k, v in D.items():
        if v >= 2:
            for i in range(n):
                if s[i] == k:
                    idx[ord(k) - 97].append(i)

    res = 0
    for i in idx:
        if not i:
            continue
        tmp = 0
        for pattern in combinations(i, 2):
            left_init, right_init = pattern
            left, right = left_init, right_init
            length = 0
            while right < n and left < right_init:
                if s[left] == s[right]:
                    length += 1
                    left += 1
                    right += 1
                else:
                    break
            tmp = max(tmp, length)
        res = max(res, tmp)
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def main():
    N = int(input())
    S = input()
    counter = defaultdict(int)
    for c in S:
        counter[c] += 1
    ans = 0
    for i in range(N - 1, 0, -1):
        ci = S[i]
        if counter[ci] <= 1:
            continue
        for j in range(i - ans - 1, -1, -1):
            cj = S[j]
            if cj != ci:
                continue
            k = 0
            while k + 1 <= min(j + 1, i - j - 1) and S[i - k - 1] == S[j - k - 1]:
                k += 1
            ans = max(ans, k + 1)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

ans=0  
for i in range(N):
  d=S[i:]
  D=Z_algorithm(d)
  for j in range(N-i):
    ans=max(ans,min(j,D[j]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def zalgo(s):
	lens = len(s)
	a = [0 for _ in range(lens)]
	maxa = 0
	saisho = -1
	saigo = -1
	for i in range(lens):
		cnt = 0
		j = 0
		if saisho != -1:
			j = min(a[i-saisho], max(0, saigo-i))
		while i+j < lens and s[i+j] == s[j]:
			cnt += 1
			j += 1
		if saigo < i+j:
			saigo = i+j
			saisho = i
		a[i] = cnt
		if cnt > maxa and cnt <= i and i != 0:
			maxa = cnt
	return maxa


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

ans = 0
for i in range(n):
	k = zalgo(s[i:])
	if ans < k:
		ans = k
print(ans)

Submission status: Time Limit Exceeded

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

res = 0

for i in range(N - 1):
    for j in range(i + 1, N):
        if S[i:j] not in S[j:]:
            break
    res = max(res, j - i - 1)

print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

N = int(input())
S = input()
D = defaultdict(int)

res = 0

for i in range(N):
    for j in range(i + 1, N + 1):
        s = S[i:j]
        if s in D and D[s] + (j - i) <= i:
            res = max(res, j - i)
        else:
            D[s] = i

print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

N = int(input())
S = input()
D = defaultdict(int)

res = 0

for i in range(N):
    for j in range(i + 1, N + 1):
        s = S[i:j]
        if s in D and D[s] + (j - i) <= i:
            res = max(res, j - i)
        D[s] = i
        
print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
S = str(input())
T = deque(list(S))
#print(T)

#Z = [0 for _ in range(N)]
#Z[0] = N

def momokuroz(s): #z-algorithm
  Max = 0
  n = len(s)
  z = [0 for _ in range(n)]
  z[0] = n
  i = 1; j = 0
  while i < n: #iは基準の位置。
    while i+j < n and s[i+j] == s[j]:
      j += 1 #何文字一致してるかなー？
    z[i] = min(i,j) #jが一致している文字数。
    Max = max(Max,z[i])
    if j == 0:
      i += 1
      continue
    
    k = 1 #途中でjを超えていたらその先は別途見る必要がある。
    #kが一致してる文字数ぴったしだとその先は不明。k<j
    #j文字一致しているところを参照したいが飛び出していたらそこは不明。k+Z[k]<j
    while k<j and k+z[k] <j:
      z[i+k] = z[k]
      k += 1
    
    i += k #基準位置を動かす
    j -= k #このjまでは一致しているのは確定なので上のWhileに戻ってチェック。
  #MAX = max(z[1:])
  #print(Max,s,z)
  return Max

ans = 0    
for i in range(N-1):
  temp = "".join(T)
  a = momokuroz(temp)
  ans = max(ans,a)
  T.popleft()


print(ans)

Submission status: Time Limit Exceeded

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

Z = [0 for _ in range(N)]
Z[0] = N

def momokuroz(s):
  Max = 0
  n = len(s)
  z = [0 for _ in range(n)]
  z[0] = n
  i = 1; j = 0
  while i < n: #iは基準の位置。
    while i+j < n and s[i+j] == s[j]:
      j += 1 #何文字一致してるかなー？
    z[i] = min(i,j) #jが一致している文字数。
    Max = max(Max,z[i])
    if j == 0:
      i += 1
      continue
    
    k = 1 #途中でjを超えていたらその先は別途見る必要がある。
    #kが一致してる文字数ぴったしだとその先は不明。k<j
    #j文字一致しているところを参照したいが飛び出していたらそこは不明。k+Z[k]<j
    while k<j and k+z[k] <j:
      z[i+k] = z[k]
      k += 1
    
    i += k #基準位置を動かす
    j -= k #このjまでは一致しているのは確定なので上のWhileに戻ってチェック。
  #MAX = max(z[1:])
  #print(Max,s,z)
  return Max

ans = 0    
for i in range(N-1):
  temp = S[i:]
  a = momokuroz(temp)
  ans = max(ans,a)


print(ans)

Submission status: Time Limit Exceeded

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

Z = [0 for _ in range(N)]
Z[0] = N

def momokuroz(s):
  n = len(s)
  z = [0 for _ in range(n)]
  z[0] = n
  i = 1; j = 0
  while i < n: #iは基準の位置。
    while i+j < n and s[i+j] == s[j]:
      j += 1 #何文字一致してるかなー？
    z[i] = min(i,j) #jが一致している文字数。
    if j == 0:
      i += 1
      continue
    
    k = 1 #途中でjを超えていたらその先は別途見る必要がある。
    #kが一致してる文字数ぴったしだとその先は不明。k<j
    #j文字一致しているところを参照したいが飛び出していたらそこは不明。k+Z[k]<j
    while k<j and k+z[k] <j:
      z[i+k] = z[k]
      k += 1
    
    i += k #基準位置を動かす
    j -= k #このjまでは一致しているのは確定なので上のWhileに戻ってチェック。
  #MAX = max(z[1:])
  #print(MAX,s)
  return z

ans = 0    
for i in range(N-1):
  temp = S[i:]
  t = momokuroz(temp)
  #print(t,max(t[1:]))
  ans = max(ans,max(t[1:]))    


print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# E
# 文字列比較をローリングハッシュを用いると高速
# 用いなくてもpypy使わなくえれば通る

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

n = int(input())
s = input()[:-1]
# s = list(map(ord, list(input()[:-1])))
# print(s)

lb = 0
ub = n//2 + 1


def check(len):
    # これはTLE
    for l1 in range(n-len):
        for l2 in range(l1+len, n-len+1):
            if s[l1:l1+len] == s[l2:l2+len]:
                return True
    return False


def check3(m):
    # これはOK(pypyではなくpython3）
    dic = defaultdict(str)
    # dic = {}
    for i in range(n-m+1):
        s_ = s[i:i+m]
        if s_ in dic.keys():
            if dic[s_]+m<=i:
                return True
        else:
            dic[s_] = i
    return False


mod = 10**9+7
base = 1234
power = [1]*(n+1)
for i in range(1, n+1):
    power[i] = power[i-1]*base%mod

def check2(m):
    res = 0
    for i in range(m):
        res+=s[i]*power[m-i-1]
        res%=mod

    dic = {res: 0}
    # defaultdictが早い
    # dic = defaultdict(int)
    # dic[res] = 0

    for i in range(n-m):
        res = ((res-s[i]*power[m-1])*base
                             +s[i+m])%mod
        if res in dic.keys():
            index = dic[res]
            if index +m<=i+1:
                return True
        else:
            dic[res] = i+1
    return False


while ub > lb+1:
    x = (lb + ub)//2
    if check3(x):
        lb = x
    else:
        ub = x
    # print(lb, ub)


'''
print(3, check(3))
print(4, check(4))
print(5, check(5))
'''

print(lb)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# E
# 文字列比較をローリングハッシュを用いると高速

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

n = int(input())
s = input()[:-1]
# s = list(map(ord, list(input()[:-1])))
# print(s)

lb = 0
ub = n//2 + 1


def check(len):
    for l1 in range(n-len):
        for l2 in range(l1+len, n-len+1):
            if s[l1:l1+len] == s[l2:l2+len]:
                return True
    return False


mod = 10**9+7
base = 1234
power = [1]*(n+1)
for i in range(1, n+1):
    power[i] = power[i-1]*base%mod


def check2(m):
    res = 0
    for i in range(m):
        res+=s[i]*power[m-i-1]
        res%=mod

    dic = {res: 0}
    # defaultdictが早い
    # dic = defaultdict(int)
    # dic[res] = 0

    for i in range(n-m):
        res = ((res-s[i]*power[m-1])*base
                             +s[i+m])%mod
        if res in dic.keys():
            index = dic[res]
            if index +m<=i+1:
                return True
        else:
            dic[res] = i+1
    return False


def check3(m):
    dic = {}
    for i in range(n-m+1):
        s_ = s[i:i+m]
        if s_ in dic.keys():
            if dic[s_]+m<=i:
                return True
        else:
            dic[s_] = i
    return False


while ub > lb+1:
    x = (lb + ub)//2
    if check(x):
        lb = x
    else:
        ub = x
    # print(lb, ub)


'''
print(3, check(3))
print(4, check(4))
print(5, check(5))
'''

print(lb)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# E
# 文字列比較をローリングハッシュを用いると高速

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

n = int(input())
s = input()[:-1]
# s = list(map(ord, list(input()[:-1])))
# print(s)

lb = 0
ub = n//2 + 1


def check(len):
    for l1 in range(n-len):
        for l2 in range(l1+len, n-len+1):
            if s[l1:l1+len] == s[l2:l2+len]:
                return True
    return False


mod = 10**9+7
base = 1234
power = [1]*(n+1)
for i in range(1, n+1):
    power[i] = power[i-1]*base%mod


def check2(m):
    res = 0
    for i in range(m):
        res+=s[i]*power[m-i-1]
        res%=mod

    dic = {res: 0}
    # defaultdictが早い
    # dic = defaultdict(int)
    # dic[res] = 0

    for i in range(n-m):
        res = ((res-s[i]*power[m-1])*base
                             +s[i+m])%mod
        if res in dic.keys():
            index = dic[res]
            if index +m<=i+1:
                return True
        else:
            dic[res] = i+1
    return False


def check3(m):
    dic = {}
    for i in range(n-m+1):
        s_ = s[i:i+m]
        if s_ in dic.keys():
            if dic[s_]+m<=i:
                return True
        else:
            dic[s_] = i
    return False


while ub > lb+1:
    x = (lb + ub)//2
    if check3(x):
        lb = x
    else:
        ub = x
    # print(lb, ub)


'''
print(3, check(3))
print(4, check(4))
print(5, check(5))
'''

print(lb)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# E
# 文字列比較をローリングハッシュを用いると高速

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

n = int(input())
s = list(map(ord, list(input()[:-1])))
# print(s)

lb = 0
ub = n//2 + 1


def check(len):
    for l1 in range(n-len):
        for l2 in range(l1+len, n-len+1):
            if s[l1:l1+len] == s[l2:l2+len]:
                return True
    return False


mod = 10**9+7
base = 1234
power = [1]*(n+1)
for i in range(1, n+1):
    power[i] = power[i-1]*base%mod

def check2(m):
    res = 0
    for i in range(m):
        res+=s[i]*power[m-i-1]
        res%=mod
    dic = defaultdict(int)
    dic[res] = 0

    for i in range(n-m):
        res = ((res-s[i]*power[m-1])*base
                             +s[i+m])%mod
        if res in dic.keys():
            index = dic[res]
            if index +m<=i+1:
                return True
        else:
            dic[res] = i+1
    return False


while ub > lb+1:
    x = (lb + ub)//2
    if check2(x):
        lb = x
    else:
        ub = x
    # print(lb, ub)


'''
print(3, check(3))
print(4, check(4))
print(5, check(5))
'''

print(lb)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# E

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

n = int(input())
s = list(map(ord, list(input()[:-1])))
# print(s)

lb = 0
ub = n//2 + 1


def check(len):
    for l1 in range(n-len):
        for l2 in range(l1+len, n-len+1):
            if s[l1:l1+len] == s[l2:l2+len]:
                return True
    return False


mod = 10**9+7
base = 1234
power = [1]*(n+1)
for i in range(1, n+1):
    power[i] = power[i-1]*base%mod

def check2(m):
    res = 0
    for i in range(m):
        res+=s[i]*power[m-i-1]
        res%=mod
    dic = {res:0}
    for i in range(n-m):
        res = ((res-s[i]*power[m-1])*base
                             +s[i+m])%mod
        if res in dic.keys():
            index = dic[res]
            if index +m<=i+1:
                return True
        else:
            dic[res] = i+1
    return False


while ub > lb+1:
    x = (lb + ub)//2
    if check2(x):
        lb = x
    else:
        ub = x
    # print(lb, ub)


'''
print(3, check(3))
print(4, check(4))
print(5, check(5))
'''

print(lb)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# E

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

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

lb = 0
ub = n//2 + 1

def check(len):
    for l1 in range(n-len):
        for l2 in range(l1+len, n-len+1):
            # print(len, s[l1:l1 + len], s[l2:l2 + len])

            if s[l1:l1+len] == s[l2:l2+len]:
                return True
    return False

while ub > lb+1:
    x = (lb + ub)//2
    if check(x):
        lb = x
    else:
        ub = x
    # print(lb, ub)


'''
print(3, check(3))
print(4, check(4))
print(5, check(5))
'''

print(lb)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
for n in range(N - 1, 1, -1):
    d = dict()
    for i in range(N - n + 1):
        string = S[i: i + n]
        if d.get(string, None) not in (None, i // n):
            print(n)
            quit()
        d[string] = i // n
print(0)

Submission status: Time Limit Exceeded

Solution code:

def z_algorithm(S):
    # 文字列が与えられた時、各 i について
    # 「S と S[i:|S|-1] の最長共通接頭辞の長さ」を記録した配列 A を
    #  O(|S|) で構築するアルゴリズム
    # S: aaabaaaab
    # A: 921034210
    # 例えば、A[5] = 4だが、これは、S[0:4] == S[5:5+4] 
    # (Sの0文字目からと5文字目からは、4文字一致している(aaab)) ことを意味する。

    lenS = len(S)
    A = [0] * lenS
    i = 1; j = 0
    A[0] = lenS
    # i: 調査開始点
    # iを1文字目からlen(S)-1文字目まで左から順に動かしていく
    while i < lenS:
        # j: 何文字目まで一致するか(iからの距離)
        # 一致しなくなるまでjを左から右へ動かしていく
        while i + j < lenS and S[j] == S[i + j]:
            j += 1
        # 1文字も一致しない場合は調査開始点を一つ右にずらす
        if j == 0:
            i += 1
            continue

        A[i] = j

        # 例）S: momomosumomomomo
        # A[1] = 0, A[2] = 4 (A[0:4] == A[2:2+4] = "momo")

        # i=2の調査が終わった段階で、
        # S[3] = S[2 + 1] = S[1] = "o" 
        # で、A[3] = A[1] = 0（Sの1文字目からと3文字目からは一致しない）
        # のは明らかなので、i = 3の結果はi = 1の結果を流用して0とする。
        # つまり、A[3] = A[2 + 1] = A[1] = 0

        # 今回、i + j 文字目まで、一致するか調べたので、
        # A[i + 1] ~ A[i + j - 1] までの間で、計算結果を流用できるところは流用する
        # j <= k + A[k] となるようなkの場合、
        # j文字目以降は今回調べてないので一致するか本当に分からないので、流用をやめる
        # 今回の場合、
        # k = 1: 1 + A[1] = 1 + 0 = 1 < j = 4 なので、流用できる
        # k = 2: 2 + A[2] = 2 + 4 = 6 > j = 4 なので、流用できない
        # つなり、k=2となった瞬間、流用をせずにループを抜ける。
        k = 1
        while k + A[k] < j and i + k < lenS:
            A[i + k] = A[k]
            k += 1
        # 今回 1回 (=k-1回) 流用できた、つまり A[3] = A[2(=i) + 2(=k) - 1] まで確定したので、
        # 次は A[4] = A[i + k] から調べる
        i += k

        # また、k = 2 のとき、k + A[k] >= j となって流用を打ち切られたということは、
        # k + A[i + k] >= j  => A[i + k] >= j - k
        # A[4] は少なくとも j - k = 4 - 2 = 2 以上となることが確定する。
        # つまり、S[4:]とSは、少なくとも最初の2文字 (j-k文字) は一致する。
        # よって、A[4]を調べるときは、j=2から調査を開始すればよい。
        # （つまり、S[6]とS[4:][2]が一致しているか調べるところから始める）

        #             0123456
        # S         = momomosumomomomo
        # S[2:]     =   momosumomomomo   <- 5文字目が違う
        # S[2:][2:] =     mosumomomomo   <- 3文字目が違う
        # S[4:]     =     mosumomomomo   <- 3文字目が違う
        # S[4:][2:] =       sumomomomo   <- 1文字目が違う
        j -= k
    return A

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

    ans = 0

    # Z-algorithm で、最長共通接頭辞の長さを調べる。
    # Z-algorithm は、「S と S[i:|S|-1] の最長共通接頭辞の長さ」を記録するので、
    # S[1]以降の部分文字列同士の長さは、
    # S=S[i:]としてiをずらしながら最長共通接頭辞を調べることで分かる

    for i in range(N-1):
        A = z_algorithm(S[i:])
        # print(A)
        # 例えばS = ababa のとき、
        # A = [5, 0, 3, 0, 1] となる。
        # A[2] = 3 だが、範囲が被ってしまっているので、
        # A[i] > i の場合、一致する文字数はiまでにしておく。
        ans = max(ans, max([min(i, a) for i, a in enumerate(A)]))

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# from collections import deque
def main():
    N = int(input())
    S = input()

    # d = deque()
    max_len = N // 2
    ans = 0

    for L in reversed(range(1, max_len + 1)):
        found = False
        for i in range(N-L):
            if S[i:i+L] in S[i+L:]:
                found = True
                break
        if found:
            ans = L
            break
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

    max_len = N // 2

    ans = 0
    for L in range(1, max_len + 1):
        found = False
        for i in range(N-L):
            if S[i:i+L] in S[i+L:]:
                found = True
                break
        if found:
            ans = L
    print(ans)

if __name__ == '__main__':
    main()