Problem:


Score : 500 points

Problem Statement

Given is a string S of length N.

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

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

l_1 + len \leq l_2

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

If there is no such integer len, print 0.

Constraints

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

|S| = N

S consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

N
S

Output

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

Sample Input 1

5
ababa

Sample Output 1

2

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

Sample Input 2

2
xy

Sample Output 2

0

No non-empty string satisfies the conditions.

Sample Input 3

13
strangeorange

Sample Output 3

5



Sample input:
5
ababa


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
S= input()
import math
def findLongestConseqSubseq(arr, n): 
  
    s = set() 
    ans=0
  
    # Hash all the array elements 
    for ele in arr: 
        s.add(ele) 
  
    # check each possible sequence from the start 
    # then update optimal length 
    for i in range(n): 
  
         # if current element is the starting 
        # element of a sequence 
        if (arr[i]-1) not in s: 
  
            # Then check for next elements in the 
            # sequence 
            j=arr[i] 
            while(j in s): 
                j+=1
  
            # update  optimal length if this length 
            # is more 
            ans=max(ans, j-arr[i]) 
    return ans 

C=[]
M=0
for i in range(n):
    for j in range(i+1, n):
        if S[i]==S[j]:
            C.append([i,j])
if C!=[]:
    T=[[c[1]-c[0],c[0]] for c in C]
    T.sort()
    k=T[0][0]
    A=[[[],k]]
    i=0
    for t in T :
        if t[0]==k:
            A[i][0].append(t[1])
        else:
            k=t[0]
            A.append([[],k])
            i+=1
            A[i][0].append(t[1])
    M=0
    for a in A:
        m=min(findLongestConseqSubseq(a[0],1),a[1])
        if m>M:
            M=m
print(M)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

# input
N = int(input())
S = input()
max_val = 0


for j in range(len(S)):
    s = S[j:]
    z = [0]*len(s)
    n = len(s)
    L = 0
    R = 0
    for i in range(1, n):
        if i > R:
            L = i
            R = i
            while (R < n):
                if (s[R - L] == s[R]):
                    z[i] = R - L + 1
                    if z[i] > L:
                        z[i] = 0
                else:
                    break
                R += 1
        else:
            k = i - L
            if z[k] < R - i + 1:
                z[i] = z[k]
            else:
                L = i
                while (R < n):
                    if s[R - L] == s[R]:
                        z[i] = R - L + 1
                        if z[i] > L:
                            z[i] = 0
                    else:
                        break
                    R += 1
    max_z = max(z)
    # print(z)
    # print(n)
    if (max_z > max_val) & (max_z / 2 < n//2):
        max_val = max(z)

print(max_val)

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
    k = (s.H2[r] - s.H2[l] * s.P2[r - l] + 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:
n=int(input())
S= input()
C=[]
k=0
for i in range(n):
    for j in range(i+1, n):
        if S[i]==S[j]:
            C.append([i,j])
while C != [] :
    k+=1
    t=[]
    for c in C:
        if c[0]+k < c[1] and c[1]+k  in range(len(S)) and S[c[0]+k]==S[c[1]+k]:
            t.append(c)
    C=t        
print(k)

Submission status: Time Limit Exceeded

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

# Zアルゴリズムで解く

c=0
max_num=0
for sub in range(len(S)):
    subS = S[sub:]
    length = len(subS)
    if length <= max_num:
        break
    
    A=[0 for i in range(length-max_num)]

    for i in range(1,length-max_num):
        if i+ A[i-c] < c+A[c]:
            A[i] = A[i-c]
        else:
            j=max(0,c+A[c]-i)
            while i+j<length and subS[j]==subS[i+j]:
                j+=1
            A[i]=j
            if max_num<A[i] and i>=A[i]:
                max_num = A[i]
print(max_num)

Submission status: Time Limit Exceeded

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

# Zアルゴリズムで解く

c=0
max_num=0
for sub in range(len(S)):
    subS = S[sub:]
    length = len(subS)
    if length <= max_num:
        break
    
    A=[0 for i in range(length-max_num)]

    for i in range(1,length-max_num):
        if i+ A[i-c] < c+A[c]:
            A[i] = A[i-c]
        else:
            j=max(0,c+A[c]-i)
            while i+j<length and subS[j]==subS[i+j]:
                j+=1
            A[i]=j
        if max_num<A[i] and i>=A[i]:
            max_num = A[i]
print(max_num)

Submission status: Time Limit Exceeded

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

# Zアルゴリズムで解く

c=0
max_num=0
for sub in range(len(S)):
    subS = S[sub:]
    length = len(subS)
    A=[0 for i in range(length-max_num)]

    for i in range(1,length-max_num):
        if i+ A[i-c] < c+A[c]:
            A[i] = A[i-c]
        else:
            j=max(0,c+A[c]-i)
            for _ in range(length):
                if i+j<length and subS[j]==subS[i+j]:
                    j+=1
            A[i]=j
        if max_num<A[i] and i>=A[i]:
            max_num = A[i]
print(max_num)

Submission status: Time Limit Exceeded

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

# Zアルゴリズムで解く

c=0
max_num=0
for sub in range(len(S)):
    subS = S[sub:]

    A=[0 for i in range(len(subS))]

    for i in range(1,len(subS)-max_num):
        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(subS) and subS[j]==subS[i+j]:
                j+=1
            A[i]=j
        if max_num<A[i] and i>=A[i]:
            max_num = A[i]
print(max_num)

Submission status: Time Limit Exceeded

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

# Zアルゴリズムで解く

# int c = 0;
# for (int i = 1; i < S.size(); i++){
#   if (i+A[i-c] < c+A[c]) {
#     A[i] = A[i-c];
#   } else {
#     int j = max(0, c+A[c]-i);
#     while (i+j < S.size() && S[j] == S[i+j]) ++j;
#     A[i] = j;
#   }
# }
# A[0] = S.size();

c=0
max_num=0
for sub in range(len(S)):
    subS = S[sub:]

    A=[0 for i in range(len(subS))]

    for i in range(1,len(subS)):
        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(subS) and subS[j]==subS[i+j]:
                j+=1
            A[i]=j
        if max_num<A[i] and i>=A[i]:
            max_num = A[i]
print(max_num)

Submission status: Time Limit Exceeded

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

for i in range(len, 0, -1):
  for j in range(N - i*2 + 1):
    target = S[j:j+i]
    count = S.count(target)
    
    if count >= 2:
      tag_len = i
      break
      
  if tag_len >= 2:
    break

print(tag_len)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = str(input())
#N = 13
#S = "strangeorange"

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

Submission status: Time Limit Exceeded

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

lb = 0
ub = N //2 + 1
while (ub - lb > 1):
    mid = (lb + ub) // 2
    s = []
    for i in range(N - 2*mid + 1):
        s.append(S[mid+i : 2*mid + i])
    for i in range(N - 2*mid + 1):
        if S[i:i+mid] in s:
            flag = True
            break
        else:
            flag = False
            s.pop(0)
    
    if flag == True:
        lb = mid
    else:
        ub = mid
print(lb)

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
    input = sys.stdin.readline
    
    n = int(input())
    s = input()

    ans = 0
    for i in range(1, n):
        cnt = 0
        for j in range(n-i):
            if s[i+j] == s[j]:
                cnt += 1
            else:
                if cnt >= i:
                    ans = max(ans, i)
                    break
                else:
                    ans = max(ans, cnt)
                    cnt = 0

        ans = max(ans, min(cnt, i))

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

    ans = 0
    for i in range(1, n):
        cnt = 0
        for j in range(n-i):
            if s[i+j] == s[j]:
                cnt += 1
            else:
                if cnt >= i:
                    ans = max(ans, i)
                    break
                else:
                    ans = max(ans, cnt)
                    cnt = 0

        ans = max(ans, min(cnt, i))

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(1, n):
    cnt = 0
    for j in range(n-i):
        if s[i+j] == s[j]:
            cnt += 1
        else:
            if cnt >= i:
                ans = max(ans, i)
                break
            else:
                ans = max(ans, cnt)
                cnt = 0

    ans = max(ans, min(cnt, i))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
class LcpArr(object):
    def __init__(self, orig_str: str):
        self.orig_str = orig_str
        self.sufs = self.__create_sufs()
        self.suf_arr, self.lcp_arr = self.__create_arr()

    def __call__(self, i: int, j: int):
        si, sj = sorted([self.suf_arr.index(i), self.suf_arr.index(j)])
        return min(self.lcp_arr[si:sj])

    def __create_sufs(self):
        n = len(self.orig_str)
        return [self.orig_str[i:] for i in range(n)] + [""]

    def __create_arr(self):
        n = len(self.orig_str)
        suf_arr = sorted(range(n), key=lambda x: self.sufs[x]) + [n]

        lcp_arr, c = [-1]*n, 0
        for i in range(n):
            si = suf_arr.index(i)
            lcp_arr[si] = c = self.__lcp_len(i, suf_arr[si+1], c)

        return suf_arr, lcp_arr

    def __lcp_len(self, i: int, j: int, c: int):
        suf, next_suf = self.sufs[i], self.sufs[j]

        l = c-1 if c>=2 else 0
        for i in range(l, min(len(suf), len(next_suf))):
            if suf[i] != next_suf[i]:
                break
            l += 1
        return l

def f_e():
    n = int(input())
    s = input()
    lcp = LcpArr(s)
    a = 0
    for i in range(n):
        for j in range(n):
            if i>=j:
                continue
            a = max(a, min(lcp(i, j), j-i))
    print(a)

if __name__ == "__main__":
    f_e()

Submission status: Time Limit Exceeded

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

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

    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
l = 0
i = 0
while N - i >= 2*(l + 1):
    j = i + l + 1
    while N - j >= l + 1:
        f = False
        if S[i : i + l + 1] == S[j : j + l + 1]:
            f = True
            cnt = 0
            for k in range(l + 1,min(j - i, N - j)):
                if S[i + k] == S[j + k]:
                    cnt += 1
                else:
                    break
            l += cnt + 1
            j = i + l + 1
        else:
            j += 1
    i += 1
print(l)

Submission status: Time Limit Exceeded

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

n += 1
s += "#"

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = list(map(ord, list(input())))
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 check(m):
    if N-m<m:
        return False
    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
ok = 0
ng = N+1
while ng-ok>1:
    mid = (ok+ng)//2
    
    if check(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
l = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        f = True
        for k in range(0, min(j - i, N - j )):
            if S[i + k] == S[j + k]: # ここがスライスの時はkの範囲がrange(1, min(j - i, N - j ) + 1)
                pass
            else:
                f = False
                break
        if f:
            l = max(l, k + 1)
        else:
            l = max(l, k)
print(l)

Submission status: Time Limit Exceeded

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

def zal(s):
    i = 1
    j = 0
    _N = len(s)
    Z = [0]*_N
    Z[0] = _N
    res = 0
    while i < _N:
        while i + j < _N and s[j] == s[i+j]:
            j += 1
        Z[i] = j

        if Z[i] <= i:
            res = max(res, Z[i])

        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < _N and k + Z[k] < j:
            Z[i+k] = Z[k]

            if Z[i+k] <= i+k:
                res = max(res, Z[i+k])

            k += 1
        i += k
        j -= k
    return res

ans = 0
for i in range(N):
    _S = S[i:]
    res = zal(_S)
    ans = max(ans, res)
print(ans)

Submission status: Time Limit Exceeded

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

def zal(s):
    i = 1
    j = 0
    _N = len(s)
    Z = [0]*_N
    Z[0] = _N
    while i < _N:
        while i + j < _N and s[j] == s[i+j]:
            j += 1
        Z[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < _N and k + Z[k] < j:
            Z[i+k] = Z[k]
            k += 1
        i += k
        j -= k
    return Z

res = 0
for i in range(N):
    _S = S[i:]
    Z = zal(_S)
    for j in range(len(Z)):
        if Z[j] <= j:
            res = max(res, Z[j])
print(res)

Submission status: Time Limit Exceeded

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

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

for i in range(N):
  for j in range(i+1,N):
    if S[i]==S[j]:
      dp[i][j]=dp[i-1][j-1]+1
#print(dp)

ans=0
for i in range(N):
  for j in range(i+1,N):
    if ans<dp[i][j]:
      if j-i>=dp[i][j]:
        ans=dp[i][j]

print(ans)

Submission status: Time Limit Exceeded

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

res = 0
for i in range(N):
    for j in range(i+1, N):
        _i = i
        _j = j
        while True:
            if S[_i] == S[_j]:
                _i += 1
                _j += 1
                if _i == j or _j == N:
                    break
            else:
                break
        _i -= 1
        _j -= 1
        res = max(res, _i-i+1)

print(res)

Submission status: Time Limit Exceeded

Solution code:
class LcpArr(object):
    def __init__(self, orig_str: str):
        self.orig_str = orig_str
        self.sufs = self.__create_sufs()
        self.suf_arr, self.lcp_arr = self.__create_arr()

    def __call__(self, i: int, j: int):
        si, sj = sorted([self.suf_arr.index(i), self.suf_arr.index(j)])
        return min(self.lcp_arr[si:sj])

    def __create_sufs(self):
        n = len(self.orig_str)
        return [self.orig_str[i:] for i in range(n)] + [""]

    def __create_arr(self):
        n = len(self.orig_str)
        suf_arr = sorted(range(n), key=lambda x: self.sufs[x]) + [n]

        lcp_arr = [-1]*n
        for i in range(n):
            si = suf_arr.index(i)
            lcp_arr[si] = self.__lcp_len(i, suf_arr[si+1])

        return suf_arr, lcp_arr

    def __lcp_len(self, i: int, j: int):
        suf, next_suf = self.sufs[i], self.sufs[j]

        l = 0
        for i in range(min(len(suf), len(next_suf))):
            if suf[i] != next_suf[i]:
                break
            l += 1
        return l

def f_e():
    n = int(input())
    s = input()
    lcp = LcpArr(s)
    a = 0
    for i in range(n):
        for j in range(n):
            if i>=j:
                continue
            a = max(a, min(lcp(i, j), j-i))
    print(a)

if __name__ == "__main__":
    f_e()

Submission status: Time Limit Exceeded

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

#動的計画法 dp
dp =[[0 for j in range(n+1)] for i in range(n+1)]

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

print(ans)

Submission status: Time Limit Exceeded

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

#動的計画法 dp
dp =np.array([[0 for j in range(n+1)] for i in range(n+1)])

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

#print(dp)
print(np.max(dp))

Submission status: Time Limit Exceeded

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

#動的計画法 dp
dp =np.array([[0 for j in range(n+1)] for i in range(n+1)])

for i in range(n-1, -1, -1):
    for j in range(n-1, -1, -1):
        if i <j:
            if S[i] != S[j]:
                dp[i][j] = 0
            elif S[i] == S[j]:
                dp[i][j] = 1 + dp[i+1][j+1]
                if dp[i][j] >=n/2:
                    dp[i][j] = 0

#print(dp)
print(np.max(dp))

Submission status: Time Limit Exceeded

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

#動的計画法 dp
dp =np.array([[0 for _ in range(n+1)] for _ in range(n+1)])

for i in range(n-1, -1, -1):
    for j in range(n-1, -1, -1):
        if i ==j:
            continue
        if S[i] != S[j]:
            dp[i][j] = 0
        elif S[i] == S[j]:
            dp[i][j] = 1 + dp[i+1][j+1]
            if dp[i][j] >=n/2:
                dp[i][j] = 0

print(np.max(dp))

Submission status: Time Limit Exceeded

Solution code:

N = int(input())
S = list(input())
A = [0] * N

for c in range(N-1):
    for i in range(c+1,N):
        if i+A[i-c] < c+A[c]:
            if A[i-c] > A[i]:
                A[i] = A[i-c]
        else:
            j = max(0, c+A[c]-i)
            while i+j < N and S[c+j] == S[i+j] and j<(N-c)//2:
                j += 1
            if j > A[i]:
                A[i] = j

print(max(A))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
x = []
for i in range(n):
    x.append(s[i:])

x.sort()

ans = 0
for i in range(n):
    for j in range(i+1, n):
        y = x[i]
        z = x[j]
        m = min(len(y), len(z), abs(len(y) - len(z)))
        tmp = 0
        for k in range(m):
            if y[k] == z[k]:
                tmp += 1
        if ans < tmp:
            ans = tmp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import count
 
N = int(input())
S = input()
 
abc = set(S)
 
T = {''}
 
flag = True
for i in count():
    T2 = set(T)
    T = set()
    for t in T2:
        for c in abc:
            if S.count(t + c) > 1:
                T.add(t + c)
                flag = False
    if flag:
        print(i)
        break
    flag = True

Submission status: Time Limit Exceeded

Solution code:

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

for i in range(int(len(S) / 2), 0, -1):
    for j in range(len(S) - i):
        #if S[i + j:].find(S[j:j + i]) >= 0:
        if S[j:j + i] in S[i + j:]:
            print(i)
            break
    else:
        continue
    break
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
a = []

for i in range(n):
    for j in range(i+1,n+1):
        a.append([s[i:j],i,j-1])

a.sort()
a.reverse()

ans = 0
for i in range(len(a)-1):
    if a[i][0]==a[i+1][0]:
        if a[i][2]<a[i+1][1] or a[i][1]>a[i+1][2]:
            ans = max(ans,len(a[i][0]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
n = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip()
f = False
for l in range(n//2, 0, -1):
    for j in range(n):
        ptn = S[j:j+l]
        if j+l ==n:
            break
        #print(ptn)
        if ptn in S[j+l:]:
            print(l)
            f = True
            break
    if f == True:
        break
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
import sys
n = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip()
f = False
for l in range(n//2, 0, -1):
    for j in range(n):
        ptn = S[j:j+l]
        if len(ptn) != l:
            break
        #print(ptn)
        if ptn in S[j+l:]:
            print(l)
            f = True
            break
    if f == True:
        break
else:
    print(0)

Submission status: Time Limit Exceeded

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

### @file wsap.py
### @brief
### @author Yusuke Matsunaga (松永 裕介)
###
### Copyright (C) 2019 Yusuke Matsunaga
### All rights reserved.

def Z_algorithm(S) :
    n = len(S)
    A = [ 0 for i in range(n) ]
    A[0] = n
    i = 1
    j = 0
    max_val = 0
    while i < n :
        while (i + j) < n and S[j] == S[i + j] :
            j += 1
        A[i] = j
        if j <= i and max_val < j :
            max_val = j
        if j == 0 :
            i += 1
            continue
        k = 1
        while (i + k) < n and k + A[k] < j :
            A[i + k] = A[k]
            k += 1
        i += k
        j -= k

    return max_val


def wsap(S) :
    n = len(S)
    max_len = 0
    for i in range(n) :
        val = Z_algorithm(S[i:])
        if max_len < val :
            max_len = val
    return max_len


if __name__ == '__main__' :

    n = int(input())
    S = input()
    max_len = wsap(S)
    print(max_len)

Submission status: Time Limit Exceeded

Solution code:

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

for i in range(int(len(S) / 2), 0, -1):
    for j in range(len(S) - i):
        if S[i + j:].find(S[j:j + i]) >= 0:
            print(i)
            break
    else:
        continue
    break
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
import sys
import re
n = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip()
f = False
for l in range(n//2, 0, -1):
    for j in range(n):
        ptn = S[j:j+l]
        if len(ptn) != l:
            break
        #print(ptn)
        ptn = re.compile(ptn)
        result = ptn.findall(S)
        if len(result) >=2:
            print(len(result[0]))
            f = True
            break
    if f == True:
        break
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
import sys
import re
n = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip()
f = False
for l in range(n//2, 0, -1):
    for j in range(n):
        ptn = S[j:j+l]
        ptn = re.compile(ptn)
        result = ptn.findall(S)
        if len(result) >=2:
            print(len(result[0]))
            f = True
            break
    if f == True:
        break
else:
    print(0)

Submission status: Time Limit Exceeded

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

def Z_algo(string):
    n = len(string)
    A = [0] * n
    A[0] = n
    i = 1
    j = 0
    while i < n:
        while i+j < n and string[j] == string[i+j]:
            j += 1
        A[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < n and k+A[k] < j:
            A[i+k] = A[k]
            k += 1
        i += k
        j -= k
    return A

ans = 0

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

Submission status: Time Limit Exceeded

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

for i in range(n-1):
    for j in range(1, n):
        if s[i:j] in s[j:]:
            length = max(length, len(s[i:j]))

print(length)

Submission status: Time Limit Exceeded

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

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

for i in range(N-2, -1, -1):
    for j in range(N-1, i, -1):
        if S[i] == S[j] and i + dp[i+1][j+1] < j:
            dp[i][j] = max(dp[i][j], dp[i+1][j+1] + 1, dp[i+1][j], dp[i][j+1])
        else:
            dp[i][j] = max(dp[i][j], dp[i+1][j], dp[i][j+1])
    
ans = max(dp[i][j] for i in range(N) for j in range(N))
print(ans)

Submission status: Time Limit Exceeded

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

print(max(max(min(dp[a][b], a-b) for a in range(N)) for b in range(N)))

Submission status: Time Limit Exceeded

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

print(max(max(min(dp[a][b], a-b) for a in range(b, N)) for b in range(N)))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
dp = [[0]*(N+1) for _ in range(N+1)]
for i in range(N)[::-1]:
    for j in range(N)[::-1]:
        if S[i] == S[j]:
            dp[i][j] = dp[i+1][j+1] + 1

print(max(max(min(dp[a][b], a-b) for a in range(b, N)) for b in range(N)))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

inf = float('inf')

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

dp = [[-inf] * N for _ in range(N)]

def rec(i, j):
    if not (0 <= i < j < N):
        return 0
    if dp[i][j] != -inf:
        return dp[i][j]
    res = 0
    if S[i] == S[j] and i + rec(i+1, j+1) < j:
        res = max(res, rec(i+1, j+1) + 1, rec(i+1, j), rec(i, j+1))
    else:
        res = max(res, rec(i+1, j), rec(i+1, j))
    dp[i][j] = res
    return res

ans = 0

for i in range(N):
    for j in range(i+1, N):
        ans = max(ans, rec(i, j))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
class RollingHash:
    def __init__(self,text):
        self.mod=10**17+3
        self.p=10007
        self.n=len(text)
        self.table=[0]*(self.n+1)
        for i in range(self.n):
            self.table[i+1]=(self.table[i]*self.p+ord(text[i]))%self.mod
        self.pp=[1]*(self.n+1)
        for i in range(self.n):
            self.pp[i+1]=(self.pp[i]*self.p)%self.mod
    def hash(self, i, j):
        return (self.table[j]-self.table[i]*self.pp[j-i])%self.mod
    def lcp(self, i, j):
        l,r=0,min(self.n-i,self.n-j)+1
        while r-l>1:
            m=(l+r)//2
            if self.hash(i,i+m)==self.hash(j,j+m):
                l=m
            else:
                r=m
        return l

n=int(input())
hs=RollingHash(input())
ans=0
for i in range(n):
    for j in range(i+1,n):
        ans=max(ans,min(j-i,hs.lcp(i,j)))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class RollingHash:
    def __init__(self,text):
        self.mod=10**17+3
        self.p=10007
        self.n=len(text)
        self.table=[0]*(self.n+1)
        for i in range(self.n):
            self.table[i+1]=(self.table[i]*self.p+ord(text[i]))%self.mod
        self.pp=[1]*(self.n+1)
        for i in range(self.n):
            self.pp[i+1]=(self.pp[i]*self.p)%self.mod
    def hash(self, i, j):
        return (self.table[j]-self.table[i]*self.pp[j-i])%self.mod
    def lcp(self, i, j):
        l,r=0,min(self.n-i,self.n-j)
        while r-l>0:
            m=(l+r)//2+1
            if self.hash(i,i+m)==self.hash(j,j+m):
                l=m
            else:
                r=m-1
        return l

n=int(input())
hs=RollingHash(input())
ans=0
for i in range(n):
    for j in range(i+1,n):
        ans=max(ans,min(j-i,hs.lcp(i,j)))
print(ans)