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:
def solve(n, s, MOD):
    d = 26
    ttt = [ord(c) - 97 for c in s]

    ttx = []
    c = 1
    for t in ttt[::-1]:
        ttx.append(t * c % MOD)
        c = c * d % MOD
    ttx.reverse()
    ttc = [0]
    for t in ttx:
        ttc.append((ttc[-1] + t) % MOD)

    for l in range(n // 2, 0, -1):
        appeared = []
        comparing = set()
        l2 = l * 2
        p = 1

        for i in range(l, n + 1):
            t = (ttc[i] - ttc[i - l]) * p % MOD
            if i >= l2:
                comparing.add(appeared[i - l2])
                if t in comparing:
                    return l
            appeared.append(t)
            p = p * d % MOD

    return 0


n = int(input())
s = input()
print(min(solve(n, s, MOD) for MOD in (10000000033,)))

Submission status: Wrong Answer

Solution code:
def z_arr(s):
    """An advanced computation of Z-values of a string."""
    # From https://ivanyu.me/blog/2013/10/15/z-algorithm/

    Z = [0] * len(s)
    Z[0] = len(s)

    rt = 0
    lt = 0

    for k in range(1, len(s)):
        if k > rt:
            # If k is outside the current Z-box, do naive computation.
            n = 0
            while n + k < len(s) and s[n] == s[n+k]:
                n += 1
            Z[k] = n
            if n > 0:
                lt = k
                rt = k+n-1
        else:
            # If k is inside the current Z-box, consider two cases.

            p = k - lt  # Pair index.
            right_part_len = rt - k + 1

            if Z[p] < right_part_len:
                Z[k] = Z[p]
            else:
                i = rt + 1
                while i < len(s) and s[i] == s[i - k]:
                    i += 1
                Z[k] = i - k

                lt = k
                rt = i - 1
    return Z

if __name__=="__main__":
    s=input()
    ans=0
    for i in range(len(s)):
        A=z_arr(s[i:])
        for a in range(len(A)):
            if A[a]<=a:
                ans=max(ans, A[a])

Submission status: Wrong Answer

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

def check(l):
    D = set()
    for i in range(N - 2 * l + 1):
        D.add(S[i:i+l])
        if S[i+l:i+2*l] in D:
            return True

for i in range(N // 2 + 1):
    if not check(i):
        break

print(i - 1)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = list(input())
ba = ord("a")
for i in range(N):
  S[i] = ord(S[i]) - ba + 1
B = 27
mod = 10 ** 11 + 7
def contain(a, b):
  al = len(a)
  bl = len(b)
  #print(al, a)
  if al > bl: return False
  t = pow(B, al)
  ah = 0; bh = 0
  for i in range(al):
    ah = ah * B + a[i]
    bh = bh * B + b[i]
  for i in range(bl - al + 1):
    if ah == bh: return True
    if i + al < bl:
      #print(i, i + al)
      bh = bh * B + b[i + al] - b[i] * t
  return False
res = 0
for i in range(N):
  r = min(i + N // 2, N + 1)
  l = i + res + 1
  m = (l + r) // 2
  if l > r: continue
  while r - l > 3:
    m = (l + r) // 2
    if contain(S[i: m], S[m: ]):
      l = m
      res = max(res, m - i)
    else:
      r = m
  if m <= N:
    if contain(S[i: m + 1], S[m + 1: ]):
      res = max(res, m + 1 - i)
  if m + 1 <= N:
    if contain(S[i: m + 2], S[m + 2: ]):
      res = max(res, m + 2 - i)
  if m + 2 <= N:
    if contain(S[i: m + 3], S[m + 3: ]):
      res = max(res, m + 3 - i)
print(res)

Submission status: Wrong Answer

Solution code:
def solve(n, s, MOD):
    d = 26
    ttt = [ord(c) - 97 for c in s]

    ttx = []
    c = 1
    for t in ttt[::-1]:
        ttx.append(t * c % MOD)
        c = c * d % MOD
    ttx.reverse()
    ttc = [0]
    for t in ttx:
        ttc.append((ttc[-1] + t) % MOD)

    for l in range(n // 2, 0, -1):
        appeared = []
        comparing = set()
        l2 = l * 2
        p = 1

        for i in range(l, n + 1):
            t = (ttc[i] - ttc[i - l]) * p % MOD
            if i >= l2:
                comparing.add(appeared[i - l2])
                if t in comparing:
                    return l
            appeared.append(t)
            p = p * d % MOD

    return 0


n = int(input())
s = input()
print(min(solve(n, s, MOD)
          for MOD in (100003, 100019, 100043, 100049, 100057,
                      100069, 100103, 100109, 100129, 100151)))

Submission status: Wrong Answer

Solution code:
def solve(n, s, MOD):
    d = 26
    ttt = [ord(c) - 97 for c in s]

    ttx = []
    c = 1
    for t in ttt[::-1]:
        ttx.append(t * c % MOD)
        c = c * d % MOD
    ttx.reverse()
    ttc = [0]
    for t in ttx:
        ttc.append((ttc[-1] + t) % MOD)

    for l in range(n // 2, 0, -1):
        appeared = []
        comparing = set()
        l2 = l * 2
        p = 1

        for i in range(l, n + 1):
            t = (ttc[i] - ttc[i - l]) * p % MOD
            if i >= l2:
                comparing.add(appeared[i - l2])
                if t in comparing:
                    return l
            appeared.append(t)
            p = p * d % MOD

    return 0


n = int(input())
s = input()
print(min(solve(n, s, MOD) for MOD in (19999999967,)))

Submission status: Wrong Answer

Solution code:
N = int(input())
S =  input()
n_list = [0] * N
max_length = 0
for i in range(N):
    for j in range(max_length,N):
        if S[i:j] in S[j:N]:
            continue
        else:
            current_length = j-i-1
            if current_length > max_length:
                max_length = current_length
            break
print(max(n_list))

Submission status: Wrong Answer

Solution code:
def solve(n, s, MOD):
    d = 26
    ttt = [ord(c) - 97 for c in s]

    ttx = []
    c = 1
    for t in ttt[::-1]:
        ttx.append(t * c % MOD)
        c = c * d % MOD
    ttx.reverse()
    ttc = [0]
    for t in ttx:
        ttc.append((ttc[-1] + t) % MOD)

    for l in range(n // 2, 0, -1):
        appeared = []
        comparing = set()
        l2 = l * 2
        p = 1

        for i in range(l, n + 1):
            t = (ttc[i] - ttc[i - l]) * p % MOD
            if i >= l2:
                comparing.add(appeared[i - l2])
                if t in comparing:
                    return l
            appeared.append(t)
            p = p * d % MOD

    return 0


n = int(input())
s = input()
print(min(solve(n, s, MOD) for MOD in (10000000019,)))

Submission status: Wrong Answer

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

ans = 0
for i in range(0, N - 1):
    for j in range(i + 1, N):
        if S[i] == S[j]:
            length, max_length = 1, j
            while True:
                if i + 1 == max_length or j + 1 == N:
                    break
                else:
                    i, j = i + 1, j + 1
                    if S[i] == S[j]:
                        length += 1
                    else:
                        break
            if length > ans:
                ans = length
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = str(input())
dp = [[0 for i in range(N+1)] for i 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
ans = 0
for i in range(N):
    for j in range(N):
        tmp = dp[i][j]
        if j < i:
            tmp = min(j-i,tmp)
            ans = max(tmp,ans)
print(ans)

Submission status: Wrong Answer

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

def z_algorithm(s):
    l = len(s)
    A = [0]*l
    A[0] = 0
    j = 0
    for i in range(1,l):
        while i+j<l and s[j]==s[i+j]:
            j += 1
        if j<1:
            continue
        A[i] = j
        k = 1
        while k < l-i and k < j-A[k]:
            A[i+k] = A[k]
            k += 1
        i += k
        j -= k
    #print(A, s)
    return A


def main():
    ans = 0
    for i in range(0, N):
        tmp = max(z_algorithm(S[i:]))
        #print(tmp)
        ans = max(ans, tmp)
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
def solve(n, s, MOD):
    d = 26
    ttt = [ord(c) - 97 for c in s]

    ttx = []
    c = 1
    for t in ttt[::-1]:
        ttx.append(t * c % MOD)
        c = c * d % MOD
    ttx.reverse()
    ttc = [0]
    for t in ttx:
        ttc.append((ttc[-1] + t) % MOD)

    p = pow(d, n - n // 2 + 1, MOD)
    p = pow(p, MOD - 2, MOD)
    inv_d = pow(d, MOD - 2, MOD)

    for l in range(n // 2, 0, -1):
        appeared = []
        comparing = set()
        q = p
        l2 = l * 2

        for i in range(l, n + 1):
            t = (ttc[i] - ttc[i - l]) * q % MOD
            if i >= l2:
                comparing.add(appeared[i - l2])
            if t in comparing:
                return l
            appeared.append(t)
            q = q * d % MOD

        p = p * inv_d % MOD

    return 0


n = int(input())
s = input()
print(min(solve(n, s, MOD) for MOD in (999999883, 999999893, 999999929, 999999937, 1000000007, 1000000009)))

Submission status: Wrong Answer

Solution code:
N = int(input())
S = str(input())
dp = [[0 for i in range(N+1)] for i 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
ans = 0
for i in range(N):
    for j in range(N):
        tmp = dp[i][j]
        if j > i:
            tmp = min(j-i,tmp)
        ans = max(tmp,ans)
print(ans)

Submission status: Wrong Answer

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

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

dp = [0] * N
max_leng = 0

for i in range(0, N):
    leng = 0
    idx_i = i
    sta_j = -1

    j = i - 1
    while j > -1:
        if sta_j == idx_i:
            leng = 0
            idx_i = i
            j = sta_j-1
            sta_j = -1
            continue

        if S[idx_i] == S[j]:
            if leng == 0:
                sta_j = j
            leng += 1
            idx_i -= 1
            max_leng = max(leng, max_leng)
        else:
            leng = 0
            idx_i = i
        j -= 1
print(max_leng)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = str(input())
dp = [[0 for i in range(N+1)] for i 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
ans = 0
for i in range(N):
    for j in range(N):
        tmp = dp[i][j]
        if j >= i:
            tmp = min(j-i,tmp)
        ans = max(tmp,ans)
print(ans)

Submission status: Wrong Answer

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

def z_algo(S):
    N = len(S)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j]:
            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
    return A

res = 0
for i in range(n):
    res = max(res, max(z_algo(s[i:])[1:]+[0]))
print(res)

Submission status: Wrong Answer

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

import numpy as np

N = int(input())
S = np.array([ord(x) for x in input().rstrip()],dtype=np.int64)

MOD = 10**9 + 7
base = 1234

def cumprod(arr):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr,Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    return arr.ravel()[:L]

x = np.full(N,base,np.int64); x[0] = 1
power = cumprod(x)
x = np.full(N,pow(base,MOD-2,MOD),np.int64); x[0] = 1
power_inv = cumprod(x)

# rolling hash
H = S * power % MOD
Hcum = H.cumsum() % MOD

def test(n):
    # 長さnの文字列で2回現れるものが存在する
    x = (Hcum[n-1:] - Hcum[:N-n+1] + H[:N-n+1]) % MOD
    x *= power_inv[:N-n+1]
    x %= MOD
    # 距離n以上離れたところで連番が存在しないといけない
    ind = x.argsort()
    x = x[ind]
    is_left_end = np.zeros(N-n+1,np.bool)
    is_left_end[1:] = (x[1:] != x[:-1])
    is_left_end[0] = True
    is_right_end = np.zeros(N-n+1,np.bool)
    is_right_end[:-1] = (x[:-1] != x[1:])
    is_right_end[-1] = True
    gap = ind[is_right_end] - ind[is_left_end]
    return gap.max() >= n

left = 0 # 存在
right = N+1 # 非存在
while left + 1 < right:
    mid = (left + right)//2
    if test(mid):
        left = mid
    else:
        right = mid

answer = left
print(answer)

Submission status: Wrong Answer

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

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

dp = [0] * N
max_leng = 0

for i in range(1, N):
    leng = 0
    idx_i = i
    sta_j = -1

    j = i - 1
    while j > -1:
        if sta_j == idx_i:
            leng = 0
            idx_i = i
            j = sta_j-1
            sta_j = -1
            continue

        if S[idx_i] == S[j]:
            if leng == 0:
                sta_j = j
            leng += 1
            idx_i -= 1
            max_leng = max(leng, max_leng)
        else:
            leng = 0
            idx_i = i
        j -= 1
print(max_leng)

Submission status: Wrong Answer

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

M=N//2
m=0

for _ in range(30):
    i=(M+m)//2
    #print(M,m,i)
    F=0
    for j in range(N-i):
        if M-m<=1:
            F=2
            for k in range(j+M+1,N-M):
            #print(i,S[j:j+i+1],S[k:k+i+1])
                if S[j:j+M+1]==S[k:k+M+1]:
                    F=3
            if F==3:
                print(M)
                exit()
            else:
                print(m)
                exit()
        for k in range(j+i+1,N-i):
            #print(i,S[j:j+i+1],S[k:k+i+1])
            if S[j:j+i+1]==S[k:k+i+1]:
                F=1
    if F==1:
        m=i
    else:
        M=i

Submission status: Wrong Answer

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

M=N//2
m=0

for _ in range(30):
    i=(M+m)//2
    #print(M,m,i)
    F=0
    for j in range(N-i):
        if M-m<=1:
            print(M)
            exit()
        for k in range(j+i+1,N-i):
            #print(i,S[j:j+i+1],S[k:k+i+1])
            if S[j:j+i+1]==S[k:k+i+1]:
                F=1
    if F==1:
        m=i
    else:
        M=i

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo

@mt
def slv(N, S):
    dp = [[0] * (N+1) for _ in range(N+1)]

    for i in range(N-1, -1, -1):
        for j in range(N-1, -1, -1):
            if S[i] == S[j]:
                dp[i][j] = dp[i+1][i+1] + 1
    
    ans = 0
    for i in range(N):
        for j in range(N):
            ans = max(ans, min(i-j, dp[i][j]))
    return ans


def main():
    N = read_int()
    S = read_str()
    print(slv(N, S))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def longestRepeatedSubstring(str): 
  
    n = len(str) 
    LCSRe = [[0 for x in range(n + 1)]  
                for y in range(n + 1)] 
  
    res = "" # To store result 
    res_length = 0 # To store length of result 
  
    # building table in bottom-up manner 
    index = 0
    for i in range(1, n + 1): 
        for j in range(i + 1, n + 1): 
              
            # (j-i) > LCSRe[i-1][j-1] to remove 
            # overlapping 
            if (str[i - 1] == str[j - 1] and
                LCSRe[i - 1][j - 1] < (j - i)): 
                LCSRe[i][j] = LCSRe[i - 1][j - 1] + 1
  
                # updating maximum length of the 
                # substring and updating the finishing 
                # index of the suffix 
                if (LCSRe[i][j] > res_length): 
                    res_length = LCSRe[i][j] 
                    index = max(i, index) 
                  
            else: 
                LCSRe[i][j] = 0
  
    # If we have non-empty result, then insert  
    # all characters from first character to  
    # last character of string 
    if (res_length > 0): 
        for i in range(index - res_length + 1, 
                                    index + 1): 
            res = res + str[i - 1] 
  
    return res
n=int(input())
print(longestRepeatedSubstring(input()))

Submission status: Wrong Answer

Solution code:
n = int(input())
my_str = input()
 
start = 0
end = 1
max_len = 0
 
while (end < len(my_str)):
    if my_str[start:end] in my_str[end:]:
        if end - start > max_len:
            max_len = end - start
        end += 1
    else:
        start += 1

Submission status: Wrong Answer

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

ans = 0
for i in range(1, n):
    l = s[:i]
    r = s[i:]
    if i < n/2:
        for j in range(len(l)):
            if ans <  len(l) - j:
                if l[j:len(l)] in r:
                    ans = len(l) - j
            else:
                break
    else:
        for j in range(len(r)):
            if ans <  len(r) - j:
                if r[j:len(r)] in l:
                    ans = len(r) - j
            else:
                break
print(ans)

Submission status: Wrong Answer

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

ans = 0
for i in range(1, n):
    l = s[:i]
    r = s[i:]
    if i < n/2:
        for j in range(len(l)):
            if ans <  len(l) - j:
                if l[j:len(l)] in r:
                    ans = len(l) - j
    else:
        for j in range(len(r)):
            if ans <  len(r) - j:
                if r[j:len(r)] in l:
                    ans = len(r) - j
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = list(input())
maxcnt = 0
cnt = 0
i = 0
j = 1
di = 0

while True:
    if s[i+di] == s[j+di]:
        cnt += 1
        if maxcnt < cnt:
            maxcnt = cnt
        if i+di+1 == j or j+di+1 == n:
            cnt = 0
            j += 1
            di = 0
            if j >= n-1:
                i += 1
                if i == n-1:
                    break
                j = i + 1
                di = 0
        else:
            di += 1
            
    else:
        j += 1
        di = 0
        if j+di >= n:
            i += 1
            j = i + 1
            di = 0
            if i == n-1:
                break

print(maxcnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
r = 1
ans = 0
for l in range(N):
    while True:
        if S.rfind(S[l:r]) >= r:
            r += 1
            ans = max(ans, r)
        else:
            break
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
S =  input()
dp = [0] * N
min_selct = N//2
max_length = 0
for i in range(N):
    for j in range(N -i): #range(min_selct + 1)だと計算量少なくなる
        if S[j+1:N-1].find(S[i:j]) >= 0:
            max_length = max(max_length,j-i+1)
print(max_length)

Submission status: Wrong Answer

Solution code:
def longestRepeatedSubstring(str): 
  
    n = len(str) 
    LCSRe = [[0 for x in range(n + 1)]  
                for y in range(n + 1)] 
  
    res = "" # To store result 
    res_length = 0 # To store length of result 
  
    # building table in bottom-up manner 
    index = 0
    for i in range(1, n + 1): 
        for j in range(i + 1, n + 1): 
              
            # (j-i) > LCSRe[i-1][j-1] to remove 
            # overlapping 
            if (str[i - 1] == str[j - 1] and
                LCSRe[i - 1][j - 1] < (j - i)): 
                LCSRe[i][j] = LCSRe[i - 1][j - 1] + 1
  
                # updating maximum length of the 
                # substring and updating the finishing 
                # index of the suffix 
                if (LCSRe[i][j] > res_length): 
                    res_length = LCSRe[i][j] 
                    index = max(i, index) 
                  
            else: 
                LCSRe[i][j] = 0
  
    # If we have non-empty result, then insert  
    # all characters from first character to  
    # last character of string 
    if (res_length > 0): 
        for i in range(index - res_length + 1, 
                                    index + 1): 
            res = res + str[i - 1] 
  
    return res 
  
# Driver Code 
if __name__ == "__main__": 
      
    str = "geeksforgeeks"
    print(len(longestRepeatedSubstring(str)))