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: Wrong Answer

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

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

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

print(calc())

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

# Zアルゴリズムで解く

c=0
max_num=0
for sub in range(len(S)):
    subS = S[:sub+1]
    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+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]
            i+=j
print(max_num)

Submission status: Wrong Answer

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+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]
            i+=j

    print(A)
print(max_num)

Submission status: Wrong Answer

Solution code:
n=int(input())
S= input()
import math

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])
    for a in A:
        N=len(a[0])
        m=1
        for j in range(N-1):
            if a[0][j+1]-a[0][j]==1:
                m+=1
            elif m>M:
                M=min(m,a[1])
                m=1    
        if m>M:
            M=min(m,a[1])
print(M)

Submission status: Wrong Answer

Solution code:
def Z_algo(s):
    n = len(s)
    z = [0]*n
    L = 0
    R = 0
    for i in range(1, n):
        if i > R:
            L = i
            R = i
            while R < n and s[R - L] == s[R]:
              R += 1
              z[i] = R - L
        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
    return z
  
ans = 0
N = int(input())
S = input()
for i in range(N):
    LCP = Z_algo(S[i:])
    for j, l in enumerate(LCP):
        tmp = min(l, j)
        ans = max(ans, tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
def Z_algo(s):
    n = len(s)
    z = [0]*n
    L = 0
    R = 0
    for i in range(1, n):
        if i > R:
            L = i
            R = i
            while R < n and s[R - L] == s[R]:
              z[i] = R - L + 1
              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]:
                  z[i] = R - L + 1
                  R += 1
    return z
  
ans = 0
N = int(input())
S = input()
for i in range(N):
    LCP = Z_algo(S[i:])
    for j, l in enumerate(LCP):
        tmp = min(l, j)
        ans = max(ans, tmp)
print(ans)

Submission status: Wrong Answer

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) and (s[R - L] == s[R]):
                z[i] = R - L + 1
                if z[i] > i:
                    z[i] = i
                    break
                R += 1
        else:
            k = i - L
            if z[k] < R - i + 1:
                if z[k] <= i:
                    z[i] = z[k]
                else:
                    z[i] = i
            else:
                L = i
                while (R < n) and (s[R - L] == s[R]):
                    z[i] = R - L + 1
                    if z[i] > i:
                        z[i] = i
                        break
                    R += 1
    max_z = max(z)
    if max_z > max_val:
        max_val = max(z)

print(max_val)

Submission status: Wrong Answer

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) and (s[R - L] == s[R]):
                R += 1
                z[i] = R - L + 1
                if z[i] > i:
                    z[i] = 0
                    break
        else:
            k = i - L
            if z[k] < R - i + 1:
                z[i] = z[k]
                if z[i] > i:
                    z[i] = 0
            else:
                L = i
                while (R < n) and (s[R - L] == s[R]):
                    R += 1
                    z[i] = R - L + 1
                if z[i] > i:
                    z[i] = 0
                    break
    max_z = max(z)
    if max_z > max_val:
        max_val = max(z)

print(max_val)

Submission status: Wrong Answer

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) and (s[R - L] == s[R]):
                z[i] = R - L + 1
                R += 1
                if z[i] > L:
                    z[i] = 0
                    break
        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]):
                    z[i] = R - L + 1
                    R += 1
                if z[i] > L:
                    z[i] = 0
                    break
    max_z = max(z)
    if (max_z > max_val):
        max_val = max(z)

print(max_val)

Submission status: Wrong Answer

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:
                    z[i] = 0
                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:
                        z[i] = 0
                    R += 1
    max_z = max(z)
    if (max_z > max_val) & (max_z / 2 < n//2):
        max_val = max(z)

print(max_val)

Submission status: Wrong Answer

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_val = max(z)

print(max_val)

Submission status: Wrong Answer

Solution code:
S= input()
C=[]
k=0
for i in range(len(S)):
    for j in range(i+1, len(S)):
        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: Wrong Answer

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

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

for c in range(len(S)):

    for i in range(1,length-max_num):
        if i+ A[i] < c+A[c]:
            A[i] = A[i-c]
        else:
            j=max(0,c+A[c]-i)
            while i+j<length and S[j]==S[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: Wrong Answer

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]
    if max_num!=0:
        break
print(max_num)

Submission status: Wrong Answer

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)//2+1):
        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
    nums =max(A)
    ind  =A.index(nums) 
    if nums!=0 and ind>=nums:
        max_num = nums
        break
print(max_num)

Submission status: Wrong Answer

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

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
    nums =max(A)
    ind  =A.index(nums) 
    if nums!=0 and ind>=nums:
        max_num = nums
        break
print(max_num)

Submission status: Wrong Answer

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

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

    def __create_z(self, s: str):
        n = len(s)
        Z = [0]*n
        Z[0] = n
        l, r = 0, 0

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

def f_e():
    n = int(input())
    s = input()
    a = 0
    for i in range(n-1):
        ss = s[i:]
        z_algo = ZAlgorithm(ss)
        for j in range(len(ss)):
            a = max(a, min(z_algo(j), j))
    print(a)

if __name__ == "__main__":
    f_e()

Submission status: Wrong Answer

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

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

    def __create_z(self, s: str):
        n = len(s)
        Z = [0]*n
        Z[0] = n
        l, r = 0, 0

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

def f_e():
    n = int(input())
    s = input()
    a = 0
    for i in range(n-1):
        ss = s[i:]
        z_algo = ZAlgorithm(ss)
        for j in range(len(ss)):
            a = max(a, min(z_algo(j), j))
    print(a)

if __name__ == "__main__":
    f_e()

Submission status: Wrong Answer

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])
    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: Wrong Answer

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 = set()
    for i in range(N - 2*mid + 1):
        s.add(S[i:mid+i])
        for j in range(i+1):
            if S[mid+j:j+2*mid] in s:
                flag = True
                break
            else:
                flag = False
    if flag == True:
        lb = mid
    else:
        ub = mid
print(lb)

Submission status: Wrong Answer

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 = set()
    for i in range(N - 2*mid + 1):
        s.add(S[mid+i:2*mid+i])
        for j in range(i+1):
            if S[j:j+mid] in s:
                flag = True
                break
            else:
                flag = False
    if flag == True:
        lb = mid
    else:
        ub = mid
print(lb)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

    def __create_z(self, s: str):
        n = len(s)
        Z = [0]*n
        Z[0] = n
        l, r = 0, 0

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

def f_e():
    n = int(input())
    s = input()
    a = 0
    for i in range(n-1):
        ss = s[i:]
        z_algo = ZAlgorithm(ss)
        for j in range(1, len(ss)):
            a = max(a, min(z_algo(j), j))
    print(a)

if __name__ == "__main__":
    f_e()

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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:
        if S[i : i + l + 1] == S[j : j + l + 1]:
            cnt = 0
            for k in range(l + 1,min(j - 1 - i - l, N - 1 - j - l) + 1):
                if S[i + k] == S[j + k]:
                    cnt += 1
                else:
                    break
            l += cnt + 1
        j += 1
    i += 1
print(l)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = list(map(ord, list(input())))
mod = 10**9+7
base = 100
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
    rolling_hash = [0]*(N-m+1)
    res = 0
    for i in range(m):
        res+=S[i]*power[m-i-1]
        res%=mod
    rolling_hash[0] = res
    dic = {res:0}
    for i in range(N-m):
        tmp = ((rolling_hash[i]-S[i]*power[m-1])*base
                             +S[i+m])%mod
        rolling_hash[i+1] = tmp
        if tmp in dic.keys():
            index = dic[tmp]
            if index +m<=i+1:
                return True
        else:
            dic[rolling_hash[i+1]] = 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: Wrong Answer

Solution code:
def f_e_dp():
    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 i>=j:
                continue
            if s[i]==s[j]:
                dp[i][j] = min(j-i, dp[i+1][j+1]+1)
    print(max(max(dp)))

if __name__ == "__main__":
    f_e_dp()

Submission status: Wrong Answer

Solution code:

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

for c in range(N-1):
    mid = (N-c)//2
    for i in range(c+mid,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<mid:
                j += 1
            if j > A[i]:
                A[i] = j

print(max(A))

Submission status: Wrong Answer

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-1):
    m = min(len(x[i]), len(x[i+1]), abs(len(x[i]) - len(x[i+1])))
    tmp = 0
    for j in range(m):
        if x[i][j] == x[i+1][j]:
            tmp += 1
    if ans < tmp:
        ans = tmp
print(ans)

Submission status: Wrong Answer

Solution code:
def Z_algo(S):
    n = len(S)
    LCP = [0]*n
    i = 1
    j = 0
    c = 0#最も末尾側までLCPを求めたインデックス
    for i in range(1, n):
        #i番目からのLCPが以前計算したcからのLCPに含まれている場合
        if i+LCP[i-c] < c+LCP[c]:
            LCP[i] = LCP[i-c]
        else:
            j = max(0, c+LCP[c]-i)
            while i+j < n and S[j] == S[i+j]: j+=1
            LCP[i] = j
            c = i
    LCP[0] = n
    return LCP
ans = 0
N = int(input())
S = input()
for i in range(N):
    LCP = Z_algo(S[i:])
    for j, l in enumerate(LCP):
        tmp = min(l, j-i)
        ans = max(ans, tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
def Z_algo(S):
    n = len(S)
    LCP = [0]*n
    i = 1
    j = 0
    c = 0#最も末尾側までLCPを求めたインデックス
    for i in range(1, n):
        #i番目からのLCPが以前計算したcからのLCPに含まれている場合
        if i+LCP[i-c] < c+LCP[c]:
            LCP[i] = LCP[i-c]
        else:
            j = max(0, c+LCP[c]-i)
            while i+j < n and S[j] == S[i+j]: j+=1
            LCP[i] = j
            c = i
    LCP[0] = n
    return LCP
ans = 0
N = int(input())
S = input()
for i in range(N):
    LCP = Z_algo(S[i:])
    for j, l in enumerate(LCP):
        tmp = min(l, j-i+1)
        ans = max(ans, tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
def Z_algo(S):
    n = len(S)
    LCP = [0]*n
    i = 1
    j = 0
    c = 0#最も末尾側までLCPを求めたインデックス
    for i in range(1, n):
        #i番目からのLCPが以前計算したcからのLCPに含まれている場合
        if i+LCP[i-c] < c+LCP[c]:
            LCP[i] = LCP[i-c]
        else:
            j = max(0, c+LCP[c]-i)
            while i+j < n and S[j] == S[i+j]: j+=1
            LCP[i] = j
            c = i
    LCP[0] = n
    return LCP
ans = 0
N = int(input())
S = input()
for i in range(N):
    LCP = Z_algo(S[i:])
    print(LCP)
    for j, l in enumerate(LCP):
        tmp = min(l, j-i+1)
        ans = max(ans, tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N = int(input())
        S = input().rstrip()

        ans = 0
        for i in range(N - 1):
            tmp_max = min(self.longest_common_subsequence(S[i:]), (N - i) // 2)
            ans = max(tmp_max, ans)

        print(ans)

    # Z-Algorithm を使った連続する部分文字列長の計算
    def longest_common_subsequence(self, s: str) -> int:
        z = [0] * len(s)
        z[0] = len(s)

        # Z-box の初期値
        z_box_start, z_box_end, = 0, 0

        # １文字目から一文字ずつチェック
        for i in range(1, len(s)):
            # Z-box の範囲外
            if i > z_box_end:
                # 一文字ずつチェックする
                while i + z[i] < len(s) and s[z[i]] == s[z[i] + i]:
                    z[i] += 1
                # 新しい Z-box が見つかった場合
                if z[i] > 0:
                    z_box_start, z_box_end = i, i + z[i] - 1

            # Z-box の範囲内
            else:
                # 計算済みの Z-Value(一致する文字列長)を利用
                # 一致範囲が Z-Box の範囲内
                if z[i - z_box_start] <= z_box_end - i:
                    # 計算済みの Z-Value を利用
                    z[i] = z[i - z_box_start]

                # 一致範囲が Z-Box の範囲外
                else:
                    # Z-Box の範囲外 の部分を, 一文字ずつチェックする
                    check_target = z_box_end + 1
                    while check_target < len(s) and s[check_target] == s[check_target - i]:
                        check_target += 1
                    z[i] = check_target - i
                    # Z-Box の更新
                    z_box_start, z_box_end = i, check_target - 1

        # 最大長を返却
        return max(z[1:])


# Run main
if __name__ == '__main__':
    AtCoder().main()

Submission status: Wrong Answer

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 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: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N = int(input())
        S = input().rstrip()

        ans = 0
        for i in range(N - 1):
            ans = max((self.longest_common_subsequence(S[i:]), ans))

        print(ans)

    # Z-Algorithm を使った連続する部分文字列長の計算
    def longest_common_subsequence(self, s: str) -> int:
        z = [0] * len(s)
        z[0] = len(s)

        # Z-box の初期値
        z_box_end, z_box_start = 0, 0

        # １文字目から一文字ずつチェック
        for i in range(1, len(s)):
            # Z-box の範囲外
            if i > z_box_end:
                # 一文字ずつチェックする
                while i + z[i] < len(s) and z[i] < i and s[z[i]] == s[z[i] + i]:
                    z[i] += 1
                # 新しい Z-box が見つかった場合
                if z[i] > 0:
                    z_box_start, z_box_end = i, i + z[i] - 1

            # Z-box の範囲内
            else:
                # 利用する計算済みの Z-Value(一致する文字列長) が Z-Box の範囲内
                if z[i - z_box_start] < z_box_end - i + 1:
                    # 計算済みの Z-Value を利用
                    z[i] = z[i - z_box_start]

                # 利用する計算済みの Z-Value(一致する文字列長) が Z-Box の範囲外
                else:
                    # Z-Box の範囲外 の部分を, 一文字ずつチェックする
                    current_pos = z_box_end + 1
                    while current_pos < len(s) and current_pos - i < i and s[current_pos] == s[current_pos - i]:
                        current_pos += 1
                    if current_pos == z_box_end + 1:
                        z[i] = current_pos - i - 1
                        continue
                    z[i] = current_pos - i
                    # Z-Box の更新
                    z_box_start, z_box_end = i, current_pos

        # 最大長を返却
        return max(z[1:])


# Run main
if __name__ == '__main__':
    AtCoder().main()

Submission status: Wrong Answer

Solution code:

def wsap(s) :
    n = len(s)

    max_len = 0
    for i in range(n) :
        # s[i] から始まる文字列と同じ部分文字列を探す
        for j in range(i + 1, n) :
            l1 = j - i
            if l1 <= max_len :
                continue
            for k in range(l1) :
                if j + k >= n or s[i + k] != s[j + k] :
                    l = k - 1
                    break
            else :
                l = l1
            if max_len < l :
                max_len = l

    return max_len


if __name__ == '__main__' :

    n = int(input())
    s = input()
    print(wsap(s))