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:
import sys

input = sys.stdin.readline

def main():
    def hash_ini(t):
        h = 0
        p = 1
        for i in range(1, len(t)+1):
            h = hash_table[i] = (h * base + t[i-1]) % hash_md
            p = pw[i] = p * base % hash_md

    def hash(s):
        res = 0
        for i, c in enumerate(s[::-1]):
            res = (res + pw[i] * (ord(c) - ord_a)) % hash_md
        return res

    # インデックスがi以上j未満の文字列のハッシュ
    def hash_ij(i, j):
        return (hash_table[j] - hash_table[i] * pw[j - i]) % hash_md

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

    # 初期化
    base = 29
    hash_md = pow(3, 19)
    ord_a = ord('a')
    t = [ord(c) - ord_a for c in s]
    hash_table = [0] * (len(t) + 1)
    pw = [1] * (len(t) + 1)
    hash_ini(t)

    ok = 0
    ng = n // 2 + 1
    while ok + 1 < ng:
        br = False
        w = (ok + ng) // 2
        for i in range(n - 2 * w + 1):
            ptn = hash_ij(i, i + w)
            for j in range(i + w, n - w + 1):
                if hash_ij(j, j + w) == ptn:
                    ok = w
                    br = True
                    break
            if br: break
        else:
            ng = w
    print(ok)

main()

Submission status: Time Limit Exceeded

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

length = 0 

for i in range(N):
    l1 = i
    l2 = i + 1
    _word = S[l1:l2]
    _S = S[l2:]
    while _word in _S and l1 + len(_word) <= l2:
        l2 += 1
        _word = S[l1:l2]
        _S = S[l2:]
    length = max(len(_word)-1, length)

print(length)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

def main():
    def hash_ini(t):
        h = t[0]
        hash_table.append(h)
        p = 1
        for i in range(1, len(t)):
            h = (h * base + t[i]) % hash_md
            hash_table.append(h)
            p = p * base % hash_md
            pw.append(p)

    def hash(s):
        res = 0
        for i, c in enumerate(s[::-1]):
            res = (res + pw[i] * (ord(c) - ord_a)) % hash_md
        return res

    # インデックスがi以上j未満の文字列のハッシュ
    def hash_ij(i, j):
        return (hash_table[j] - hash_table[i] * pw[j - i]) % hash_md

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

    # 初期化
    base = 29
    hash_md = pow(3, 19)
    ord_a = ord('a')
    t = [ord(c) - ord_a for c in s]
    hash_table = [0]
    pw = [1]
    hash_ini(t)

    ok = 0
    ng = n // 2 + 1
    while ok + 1 < ng:
        br = False
        w = (ok + ng) // 2
        for i in range(n - 2 * w + 1):
            ptn = hash_ij(i, i + w)
            for j in range(i + w, n - w + 1):
                if hash_ij(j, j + w) == ptn:
                    ok = w
                    br = True
                    break
            if br: break
        else:
            ng = w
    print(ok)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

def main():
    def hash_ij(i, j):
        if i + j == 0: return 0
        res = hash_table[i][j]
        if res == -1:
            if i > 0:
                res = (hash_ij(i - 1, j - 1) * base + target[j - 1]
                       - target[i - 1] * power(j - i)) % hash_md
            else:
                res = (hash_ij(i, j - 1) * base + target[j - 1]) % hash_md
            hash_table[i][j] = res
        return res

    def power(e):
        if e == 0: return 1
        res = pw[e]
        if res == -1:
            res = pw[e] = power(e - 1) * base % hash_md
        return res

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

    # 初期化
    base = 29  # 文字種以上の素数
    hash_md = pow(3, 37)  # 2のべき乗以外がよい
    ord_a = ord('a')
    target = [ord(c) - ord_a for c in target]
    hash_table = [[-1] * (len(target) + 1) for _ in range(len(target))]
    pw = [-1] * (len(target) + 1)

    ok = 0
    ng = n // 2 + 1
    while ok + 1 < ng:
        br = False
        w = (ok + ng) // 2
        for i in range(n - 2 * w + 1):
            ptn = hash_ij(i, i + w)
            for j in range(i + w, n - w + 1):
                if hash_ij(j, j + w) == ptn:
                    ok = w
                    br = True
                    break
            if br: break
        else:
            ng = w
    print(ok)

main()

Submission status: Time Limit Exceeded

Solution code:
class Rori:
  B1 = 1009
  B2 = 1007
  MOD1 = 10 ** 9 + 7
  MOD2 = 10 ** 9 + 9
  H1, H2 = None, None
  P1, P2 = None, None
  def __init__(s, L):
    n = len(L) + 1
    s.H1 = [0] * n
    s.H2 = [0] * n
    s.P1 = [1] * n
    s.P2 = [1] * n
    for i in range(n - 1):
      S = ord(L[i]) - ord('a') + 1
      s.H1[i + 1] = (s.H1[i] * s.B1 + S) % s.MOD1
      s.H2[i + 1] = (s.H2[i] * s.B2 + S) % s.MOD2
      s.P1[i + 1] = s.P1[i] * s.B1 % s.MOD1
      s.P2[i + 1] = s.P2[i] * s.B2 % s.MOD2
  def hashLR(s, l, r):
    t = ((s.H1[r] - s.H1[l] * s.P1[r - l]) % s.MOD1 + s.MOD1) % s.MOD1
    k = ((s.H2[r] - s.H2[l] * s.P2[r - l]) % s.MOD2 + s.MOD2) % s.MOD2
    return (t, k)


class AVL:
  import sys
  sys.setrecursionlimit(1000000)
  class Node:
    def __init__(s, k):
      s.k = k
      s.l = None
      s.r = None
      s.d = 1
  def __init__(s):
    s.x = None
  def l_rot(s, z):
    y = z.r
    t = y.l
    y.l, z.r = z, t
    z.d = s.get_depth(z)
    y.d = s.get_depth(y)
    return y
  def r_rot(s, z):
    y = z.l
    t = y.r
    y.r, z.l = z, t
    z.d = s.get_depth(z)
    y.d = s.get_depth(y)
    return y
  def depth(s, node):
    if not node:
      return 0
    else:
      return node.d
  def get_depth(s, node):
    return 1 + max(s.depth(node.l), s.depth(node.r))
  def add(s, k):
    s.x = s.add_sub(s.x, k)
  def add_sub(s, node, k):
    if not node:
      return s.Node(k)
    elif node.k == k:
      return node
    elif node.k > k:
      node.l = s.add_sub(node.l, k)
    else:
      node.r = s.add_sub(node.r, k)
    node.d = s.get_depth(node)
    bal = s.depth(node.l) - s.depth(node.r)
    if bal > 1:
      if node.l.k > k:
        return s.r_rot(node)
      else:
        node.l = s.l_rot(node.l)
        return s.r_rot(node)
    elif bal < -1:
      if node.r.k < k:
        return s.l_rot(node)
      else:
        node.r = s.r_rot(node.r)
        return s.l_rot(node)
    return node
  def check(s, k):
    return s.check_sub(k, s.x)
  def check_sub(s, k, node):
    if node == None:
      return False
    if node.k == k:
      return True
    if node.k > k:
      return s.check_sub(k, node.l)
    else:
      return s.check_sub(k, node.r)

def hersCode(n):
  ok = 0
  ng = n
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if nasu(mid):
      ok = mid
    else:
      ng = mid
  return ok

def nasu(n):
  L = [None] * (N - n + 1)
  for i in range(len(L)):
    L[i] = R.hashLR(i, i + n)
  T = AVL()
  T.add(L[0])
  for i in range(n, len(L)):
    if T.check(L[i]):
      return True
    T.add(L[i - n + 1])
  return False

def honya(x, y, n):
  for i in range(n):
    if S[x + i] != S[y + i]:
      return i
  return n

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

R = Rori(S)
print(hersCode(N))

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

def main():
    def hash_ini(t):
        h = t[0]
        hash_table.append(h)
        p = 1
        for i in range(1, len(t)):
            h = (h * base + t[i]) % hash_md
            hash_table.append(h)
            p = p * base % hash_md
            pw.append(p)

    def hash(s):
        res = 0
        for i, c in enumerate(s[::-1]):
            res = (res + pw[i] * (ord(c) - ord_a)) % hash_md
        return res

    # インデックスがi以上j未満の文字列のハッシュ
    def hash_ij(i, j):
        return (hash_table[j] - hash_table[i] * pw[j - i]) % hash_md

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

    # 初期化
    base = 29
    hash_md = pow(3, 37)
    ord_a = ord('a')
    t = [ord(c) - ord_a for c in s]
    hash_table = [0]
    pw = [1]
    hash_ini(t)

    ok = 0
    ng = n // 2 + 1
    while ok + 1 < ng:
        br = False
        w = (ok + ng) // 2
        for i in range(n - 2 * w + 1):
            ptn = hash_ij(i, i + w)
            for j in range(i + w, n - w + 1):
                if hash_ij(j, j + w) == ptn:
                    ok = w
                    br = True
                    break
            if br: break
        else:
            ng = w
    print(ok)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

def main():
    def hash_ini(t):
        h = t[0]
        hash_table.append(h)
        p = 1
        for i in range(1, len(t)):
            h = (h * base + t[i]) % hash_md
            hash_table.append(h)
            p = p * base % hash_md
            pw.append(p)

    def hash(s):
        res = 0
        for i, c in enumerate(s[::-1]):
            res = (res + pw[i] * (ord(c) - ord_a)) % hash_md
        return res

    # インデックスがi以上j未満の文字列のハッシュ
    def hash_ij(i, j):
        return (hash_table[j] - hash_table[i] * pw[j - i]) % hash_md

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

    # 初期化
    base = 29
    hash_md = pow(3, 37)
    ord_a = ord('a')
    t = [ord(c) - ord_a for c in s]
    hash_table = [0]
    pw = [1]
    hash_ini(t)

    l = 0
    ans = 0
    for r in range(1, n):
        ptn = hash_ij(l, r)
        d = r - l
        for ll in range(r, n - d + 1):
            if hash_ij(ll, ll + d) == ptn:
                ans = d
                break
        else:
            l += 1
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

def main():
    def hash_ini(t):
        h = t[0]
        hash_table.append(h)
        p = 1
        for i in range(1, len(t)):
            h = (h * base + t[i]) % hash_md
            hash_table.append(h)
            p = p * base % hash_md
            pw.append(p)

    def hash(s):
        res = 0
        for i, c in enumerate(s[::-1]):
            res = (res + pw[i] * (ord(c) - ord_a)) % hash_md
        return res

    # インデックスがi以上j未満の文字列のハッシュ
    def hash_ij(i, j):
        return (hash_table[j] - hash_table[i] * pw[j - i]) % hash_md

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

    # 初期化
    base = 29
    hash_md = pow(3, 37)
    ord_a = ord('a')
    t = [ord(c) - ord_a for c in s]
    hash_table = [0]
    pw = [1]
    hash_ini(t)

    for w in range(n // 2, 0, -1):
        for i in range(n - 2 * w + 1):
            ptn = hash_ij(i, i + w)
            for j in range(i + w, n - w + 1):
                if hash_ij(j, j + w) == ptn:
                    print(w)
                    exit()
    print(0)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def z_algo(S):
    N = len(S)
    #print(N)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    #print(A)
    return A

#input = sys.stdin.readline

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

for t in range(N):
    L = z_algo(S[t:])
    for u in range(len(L)):
        if L[u] <= u:
            ans = max(ans,L[u])

print(ans)

Submission status: Time Limit Exceeded

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

dp=[[0 for _ in range(i)] for i in range(N)]
#dp[i][j]:i文字目とj文字目からの共通文字の最大長さ(i>j)

for i in range(N-1):
  if S[i]==S[N-1]:
    dp[N-1][i]=1

for i in reversed(range(N-1)):
  for j in range(i):
    if S[i]==S[j]:
      dp[i][j]=dp[i+1][j+1]+1
      if j+dp[i][j]-1>=i:
        dp[i][j]=i-j

A=[]
for i in range(N):
  for j in range(i):
    A.append(dp[i][j])

print(max(A))

Submission status: Time Limit Exceeded

Solution code:
class Rori:
  B1 = 1009
  B2 = 1007
  MOD1 = 10 ** 9 + 7
  MOD2 = 10 ** 9 + 9
  H1, H2 = None, None
  P1, P2 = None, None
  def __init__(s, L):
    n = len(L) + 1
    s.H1 = [0] * n
    s.H2 = [0] * n
    s.P1 = [1] * n
    s.P2 = [1] * n
    for i in range(n - 1):
      S = ord(L[i]) - ord('a') + 1
      s.H1[i + 1] = (s.H1[i] * s.B1 + S) % s.MOD1
      s.H2[i + 1] = (s.H2[i] * s.B2 + S) % s.MOD2
      s.P1[i + 1] = s.P1[i] * s.B1 % s.MOD1
      s.P2[i + 1] = s.P2[i] * s.B2 % s.MOD2
  def hashLR(s, l, r):
    t = ((s.H1[r] - s.H1[l] * s.P1[r - l]) % s.MOD1 + s.MOD1) % s.MOD1
    k = ((s.H2[r] - s.H2[l] * s.P2[r - l]) % s.MOD2 + s.MOD2) % s.MOD2
    return (t, k)

def hersCode(n):
  ok = 0
  ng = n
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if nasu(mid):
      ok = mid
    else:
      ng = mid
  return ok

def nasu(n):
  L = [None] * (N - n + 1)
  for i in range(len(L)):
    L[i] = R.hashLR(i, i + n)
  for i in range(n, len(L)):
    for j in range(i - n + 1):
      if L[i][0] == L[j][0] and L[i][1] == L[j][1]:
        return True
  return False

def honya(x, y, n):
  for i in range(n):
    if S[x + i] != S[y + i]:
      return i
  return n

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

R = Rori(S)

print(hersCode(N))

Submission status: Time Limit Exceeded

Solution code:
def z_algorithm(S):
  L = 0
  R = 0
  N = len(S)
  Z = [0 for i in range(N)]
  ans = 0
  for i in range(N):
    if i>R:
      L = i
      R = i
      while R < N and S[R-L] == S[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-L] == S[R]:
          R += 1
        Z[i] = R-L
        R-=1
    ans = max(ans,Z[i])
  return ans


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

ans = 0
for i in range(N):
  len_ans = z_algorithm(S[i:])
  if len_ans *2 <= N:
    ans = max(ans,len_ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

def LcpByZ(target):
    len_t = len(target)
    lcp = [-1] * len_t
    top = 1  # 右の箱において、左の箱の0に対応する点
    right = 0  # 左の箱の右端
    lcp[0] = 0
    while top < len_t:
        # 箱を右に広げていく
        while top + right < len_t and target[right] == target[top + right] and right<top:
            right += 1
        # 右の箱左端のlcpを記録
        lcp[top] = right
        left = 1
        # 左端＝右端だったらtopを動かして、このターン終了
        if right == 0:
            top += 1
            continue
        # lcpを記録しながら箱を左に縮めていく（最初の条件重要）
        while left + lcp[left] < right and left < right:
            lcp[top + left] = lcp[left]
            left += 1
        # topを右の箱の左端にして、左の箱を0まで戻す
        top += left
        right -= left
    return max(lcp)

def main():
    n = int(input())
    s = input()[::-1]
    ans=0
    for i in range(n):
        ans=max(ans,LcpByZ(s[i:]))
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
def z_algorithm(S):
  L = 0
  R = 0
  N = len(S)
  Z = [0 for i in range(N)]
  for i in range(N):
    if i>R:
      L = i
      R = i
      while R < N and S[R-L] == S[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-L] == S[R]:
          R += 1
        Z[i] = R-L
        R-=1
  return Z


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

ans = 0
for i in range(N):
  len_ans = max(z_algorithm(S[i:]))
  if len_ans *2 <= N:
    ans = max(ans,len_ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def z_algorithm(S):
  L = 0
  R = 0
  Z = [0 for i in range(len(S))]
  for i in range(len(S)):
    if i>R:
      L = i
      R = i
      while R < len(S) and S[R-L] == S[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 < len(S) and S[R-L] == S[R]:
          R += 1
        Z[i] = R-L
        R-=1
  return max(Z)


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

ans = 0
for i in range(len(S)):
  len_ans = z_algorithm(S[i:])
  if len_ans *2 <= N:
    ans = max(ans,len_ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=input()
max=0
A = [0] *len(S)
for f in range(len(S)-1):
    i = f+1
    A[f]=len(S)
    while(i<len(S)):
        j=0
        while(i+j<len(S) and S[f+j]==S[i+j] and f+j<i):
            j+=1
        A[i]=j
        if(j==0):
            i+=1
            continue
        else:
            i += j
            if (j > max):
                max = j

print(max)

Submission status: Time Limit Exceeded

Solution code:
'''Z algorithm https://snuke.hatenablog.com/entry/2014/12/03/214243'''
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:
N=int(input())
S=input()
max=0
A = [0] *len(S)
for f in range(len(S)-1):
    i = f+1

    A[0]=len(S)
    while(i<len(S)):
        j=0
        while(i+j<len(S) and S[f+j]==S[i+j] and j<i):
            j+=1
        A[i]=j
        if(j==0):
            i+=1
            continue
        if (j > max):
            max = j
        k=1
        while(k+i<len(S) and k+A[k+j]<j):
            A[i+k]=A[f+k]
            k+=1
        i+=k
print(max)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
_max = 0
 
for i in range(N):
  s_max = 0
  s_max2 = 0
  A = []
  for k in range(N - i):
    if S[k + i] == S[k]:
      A.append('1')
      s_max2 = s_max2 + 1
      if s_max2 > i:
        s_max = i
        break
    else:
      A.append('0')
      if s_max < s_max2:
        s_max = s_max2
      s_max2 = 0
      
    if s_max < s_max2:
      s_max = s_max2
      
  if s_max > i:
    s_max = i
    
  if _max < s_max:
    _max = s_max
    
print(_max)

Submission status: Time Limit Exceeded

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

for f in range(len(S)-1):
    #print("roop "+str(f))
    i = f+1
    A = [0] * (len(S)-f+i)
    A[0]=len(S)
    while(i<len(S)):
        j=0
        #print("i=" + str(i) + " j=" + str(j))
        while(i+j<len(S) and S[f+j]==S[i+j] and j<i):
            j+=1
            #print(S[f+j]+" "+S[i+j])
        A[i]=j
        if(j>max):
            max=j
            #print("update max ="+str(max))

        if(j==0):
            i+=1
            continue
        k=1
        while(k+i<len(S) and k+A[k]<j):
            A[i+k]=A[k]
            k+=1
        i+=k



#print(A)
print(max)

Submission status: Time Limit Exceeded

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

    ans = 0
    isleft = True

    def f(n):
        kaisu = N_original - n+1
        for i in range(kaisu):
            if S[i:i+n] in S[i+n:]:
                return True
        return False

    left = 0
    right = N
    N = N//4
    while True:
        if f(N):
            if left == N:
                ans = left
                break
            left = N
        else:
            if right == N:
                ans = right
                break
            right = N
        N = (left + right)//2
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    S = input()
    N_original = N

    ans = 0
    isleft = True

    def f(n):
        kaisu = N_original - n+1
        for i in range(kaisu):
            if S[i:i+n] in S[i+n:]:
                return True
        return False

    left = 0
    right = N
    N = N//4
    while True:
        if f(N):
            if left == N:
                ans = left
                break
            left = N
        else:
            if right == N:
                ans = right
                break
            right = N
        N = (left + right)//2
    print(ans)

main()

Submission status: Time Limit Exceeded

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

for i in range(N):
  s_max = 0
  s_max2 = 0
  A = []
  for k in range(N - i):
    if S[k + i] == S[k]:
      A.append('1')
      s_max2 = s_max2 + 1
    else:
      A.append('0')
      if s_max < s_max2:
        s_max = s_max2
      s_max2 = 0
      
    if s_max < s_max2:
      s_max = s_max2
      
  if s_max > i:
    s_max = i
    
  if _max < s_max:
    _max = s_max
    
print(_max)

Submission status: Time Limit Exceeded

Solution code:
import sys
input= sys.stdin.readline
n = int(input())
s = input()
cnt = 0
flag = False
for i in range(n//2):
    for j in range(n-i-1):
        for k in range(n-j-2*i-1):
            if s[j:j+i+1]==s[j+i+k+1:j+2*i+k+2]:
                flag = True
                cnt = i+1
                break
        if flag:
            flag = False
            break

print(cnt)

Submission status: Time Limit Exceeded

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

ans = 0
isleft = True

def f(n):
    for i in range(N_original - n+1):
        temp = S[i:i+n]
        if temp in S[i+n:]:
            return True
    return False

left = 0
right = N
N = N//4
while True:
    if f(N):
        if left == N:
            ans = left
            break
        left = N
    else:
        if right == N:
            ans = right
            break
        right = N
    N = (left + right)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=[ord(c) for c in input()]
def zalgo(S):
    a=[0]*len(S)
    c=0
    for i in range(1,len(S)):
        if i+a[i-c]<c+a[c]:
            a[i]=a[i-c]
        else:
            j=max(0,c+a[c]-i)
            while i+j<len(S) and S[j]==S[i+j]:
                j+=1
            a[i]=min(i,j)
    a[0]=len(S)
    return a
r=0
for i in range(N):
    a=zalgo(S[i:])
    m=max(a[1:]) if len(a)>1 else 0
    r=max(r,m)
print(r)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
String=input()
max=0

for f in range(len(String)):
    S=String[f:]
    A = [0] * len(S)
    A[0] = len(S)
    i, j = 1, 0
    #print(S)
    while(i<len(S)):
        #print(A)
        #print("i= " + str(i) + "j= " + str(j))
        while(i+j<len(S) and S[j]==S[i+j] and j<i):
            #print("i= "+str(i)+"j= "+str(j))
            j+=1
        A[i]=j
        if(j>max):
            max=j
            #print(max)
        if(j==0):
            i+=1
            continue
        k=1
        while(k+i<len(S) and k+A[k]<j):
            A[i+k]=A[k]
            k+=1
        i+=k
        j=0


#print(A)
print(max)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=[ord(c) for c in input()]
def zalgo(S):
    a=[0]*len(S)
    c=0
    for i in range(1,len(S)):
        if i+a[i-c]<c+a[c]:
            a[i]=a[i-c]
        else:
            j=max(0,c+a[c]-i)
            while i+j<len(S) and S[j]==S[i+j]:
                j+=1
            a[i]=j
    a[0]=len(S)
    return a
r=0
for i in range(N):
    a=zalgo(S[i:])
    for j in range(N-i):
        r=max(r,min(a[j],j))
print(r)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=input()
def zalgo(S):
    a=[0]*len(S)
    c=0
    for i in range(1,len(S)):
        if i+a[i-c]<c+a[c]:
            a[i]=a[i-c]
        else:
            j=max(0,c+a[c]-i)
            while i+j<len(S) and S[j]==S[i+j]:
                j+=1
            a[i]=j
    a[0]=len(S)
    return a
r=0
for i in range(N):
    a=zalgo(S[i:])
    for j in range(N-i):
        r=max(r,min(a[j],j))
print(r)

Submission status: Time Limit Exceeded

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

def search(n):
    if n == 0:
        return False
    for i in range(N-n):
        if i <= n:
            if S[i:i+n] in S[i+n:]:
                return True
        else:
            if S[i:i+n] in S[:i] + "|" + S[i+n:]:
                return True
    return False

l = 1
r = N//2+1

while l<r:
    mid = (l+r)//2
    if search(mid):
        l = mid+1
    else:
        r = mid

print(l-1)

Submission status: Time Limit Exceeded

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

def search(n):
    if n == 0:
        return False
    for i in range(N-n):
        if S[i:i+n] in S[:i] + "|" + S[i+n:]:
            return True
    return False

l = 1
r = N//2+1

while l<r:
    mid = (l+r)//2
    if search(mid):
        l = mid+1
    else:
        r = mid

print(l-1)

Submission status: Time Limit Exceeded

Solution code:
import sys

def solve():
    N = int(input())
    S = input()
    sdict = dict()
    lens = len(S)
    for i in range(lens): sdict[i] = S[i]
    
    DP = [[0 for j in range(lens)] for i in range(lens - 1)]
    maxlength = 0
    for i in reversed(range(lens - 1)):
        for j in reversed(range(i + 1, lens)):
            if sdict[i] == sdict[j]:
                if j == lens - 1: DP[i][j] = 1
                else: DP[i][j] = DP[i+1][j+1] + 1
                maxlength = max(maxlength, min(DP[i][j], j - i))

    print(maxlength)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys

def solve():
    N = int(input())
    S = input()
    lens = len(S)
    alp = ["a", "b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u",\
        "v","w","x","y","z"]
    
    DP = [[0 for j in range(lens)] for i in range(lens)]
    DP[lens - 2][lens - 1] = (1 if S[lens-2] == S[lens - 1] else 0)
    for i in reversed(range(lens - 1)):
        for j in reversed(range(i + 1, lens)):
            if S[i] == S[j]:
                if j == lens - 1: DP[i][j] = 1
                else: DP[i][j] = DP[i+1][j+1] + 1

    maxlength = 0
    for i in range(lens):
        for j in range(i+1, lens):
            maxlength = max(maxlength, min(DP[i][j], j - i))

    print(maxlength)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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

ans = 0
isleft = True

def f(n):
    for i in range(N_original - n+1):
        temp = S[i:i+n]
        if temp in S[0:i] + "|" + S[i+n:]:
            return True
    return False

left = 0
right = N
N = N//4
while True:
    if f(N):
        if left == N:
            ans = left
            break
        left = N
    else:
        if right == N:
            ans = right
            break
        right = N
    N = (left + right)//2
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

hantei = False
ans = 0

isleft = True
kosu_original = N//4
if N > 2*10**5:
    for j in range(10):
        for i in range(N-kosu_original+1):
            temp = S[i:i+kosu_original]
            # print("比較する文字列1:", temp)
            # print("比較する文字列2:",S[0:i] + "|" + S[i+kosu_original:],"\n")
            if temp in S[0:i] + "|" + S[i+kosu_original:]:
                # print("Trueの時\n-----------------")
                ans = kosu_original
                isleft = False
                break
            if isleft:
                kosu_original //= 2
            else:
                kosu_original = (kosu_original + kosu_original*2)/2
                isleft = True

    if isleft:
        for kosu in range(kosu_original-1, 0, -1):
            if hantei:
                break

            for i in range(N-kosu+1):
                if hantei:
                    break
                else:
                    temp = S[i:i+kosu]
                    # print("比較する文字列1:", temp)
                    # print("比較する文字列2:",S[0:i] + "|" + S[i+kosu:],"\n")
                if temp in S[0:i] + "|" + S[i+kosu:]:
                    # print("Trueの時\n-----------------")
                    ans = kosu
                    hantei = True
                    break
    else:
        for kosu in range(N//2, kosu_original, -1):
            if hantei:
                break

            for i in range(N-kosu+1):
                if hantei:
                    break
                else:
                    temp = S[i:i+kosu]
                    # print("比較する文字列1:", temp)
                    # print("比較する文字列2:",S[0:i] + "|" + S[i+kosu:],"\n")
                if temp in S[0:i] + "|" + S[i+kosu:]:
                    # print("Trueの時\n-----------------")
                    ans = kosu
                    hantei = True
                    break
else:
    for i in range(N-kosu_original+1):
        temp = S[i:i+kosu_original]
        # print("比較する文字列1:", temp)
        # print("比較する文字列2:",S[0:i] + "|" + S[i+kosu_original:],"\n")
        if temp in S[0:i] + "|" + S[i+kosu_original:]:
            # print("Trueの時\n-----------------")
            ans = kosu_original
            isleft = False
            break

    if isleft:
        for kosu in range(kosu_original-1, 0, -1):
            if hantei:
                break

            for i in range(N-kosu+1):
                if hantei:
                    break
                else:
                    temp = S[i:i+kosu]
                    # print("比較する文字列1:", temp)
                    # print("比較する文字列2:",S[0:i] + "|" + S[i+kosu:],"\n")
                if temp in S[0:i] + "|" + S[i+kosu:]:
                    # print("Trueの時\n-----------------")
                    ans = kosu
                    hantei = True
                    break
    else:
        for kosu in range(N//2, kosu_original, -1):
            if hantei:
                break

            for i in range(N-kosu+1):
                if hantei:
                    break
                else:
                    temp = S[i:i+kosu]
                    # print("比較する文字列1:", temp)
                    # print("比較する文字列2:",S[0:i] + "|" + S[i+kosu:],"\n")
                if temp in S[0:i] + "|" + S[i+kosu:]:
                    # print("Trueの時\n-----------------")
                    ans = kosu
                    hantei = True
                    break

print(ans)