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

def main():
    def input():
        return sys.stdin.readline()[:-1]
    N = int(input())
    S = [ord(x) for x in input()] + [-1]
    ans = 0
    s = -1
    k = 0
    while s < N-1-ans*2:
        s += 1
        for e in range(s+ans+1,N-ans):
            if S[s] == S[e]:
                k = 0
                while s+k < e and e+k < N and S[s+k] == S[e+k]:
                    k += 1
                ans = max(ans,k)
                s += k-1
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

dp = [0] * N
for i in range(N - 1):
    dp2 = dp[:]
    for j in range(i + 1, N):
        if S[i] == S[j] and j - i > dp2[j-1]:
            dp[j] = dp2[j-1] + 1

print(max(dp))

Submission status: Wrong Answer

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

dp = [0 for _ in range(N)]
for i in range(N):
    dp2 = dp[:]
    for j in range(i + 1, N):
        if S[i] == S[j] and j - i > dp2[j-1]:
            dp[j] = dp2[j-1] + 1
print(max(dp))

Submission status: Wrong Answer

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

dp = [0] * N
for i in range(N):
    for j in range(i + 1, N):
        pre = dp[j-1]
        if S[i] == S[j] and j - i > pre:
            dp[j] = pre + 1
print(max(dp))

Submission status: Wrong Answer

Solution code:
def z_arr(s):

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

    rt = 0
    lt = 0

    for k in range(1, len(s)):
        if k > rt:
            n = 0
            while n + k < len(s) and s[n] == s[n + k] and n < k:
                n += 1
            Z[k] = n
            if n > 0:
                lt = k
                rt = k + n - 1
        else:

            p = k - lt
            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] and i-k+1 < k:
                    i += 1
                Z[k] = i - k

                lt = k
                rt = i - 1
    return Z

N = int(input())
S = input()
answer = 0
for i in range(N-1):
    ZZ = z_arr(S[i:])
    # print(ZZ)
    temp_max = max(ZZ[1:])
    if answer < temp_max:
        answer = temp_max
print(answer)

Submission status: Wrong Answer

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

def solve():
  minlen = 0
  for start in range(N):
    if start+minlen > N:
      return minlen
    length = minlen+1
    while start+length<=N:
      part_s = S[start: start+length]
      remain_s = S[start+length:]
      if part_s in remain_s:
        minlen = length
        length += 1
      else:
        break

print(solve())

Submission status: Wrong Answer

Solution code:
def z_arr(s):

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

    rt = 0
    lt = 0

    for k in range(1, len(s)):
        if k > rt:
            n = 0
            while n + k < len(s) and s[n] == s[n + k] and n < k:
                n += 1
            Z[k] = n
            if n > 0:
                lt = k
                rt = k + n - 1
        else:

            p = k - lt
            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] and i-k < k:
                    i += 1
                Z[k] = i - k

                lt = k
                rt = i - 1
    return Z

N = int(input())
S = input()
answer = 0
for i in range(N-1):
    ZZ = z_arr(S[i:])
    # print(ZZ)
    temp_max = max(ZZ[1:])
    if answer < temp_max:
        answer = temp_max
print(answer)

Submission status: Wrong Answer

Solution code:
def z_arr(s):

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

    rt = 0
    lt = 0

    for k in range(1, len(s)):
        if k > rt:
            n = 0
            while n + k < len(s) and s[n] == s[n + k] and n < k:
                n += 1
            Z[k] = n
            if n > 0:
                lt = k
                rt = k + n - 1
        else:

            p = k - lt
            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] and i < k:
                    i += 1
                Z[k] = i - k

                lt = k
                rt = i - 1
    return Z

N = int(input())
S = input()
answer = 0
for i in range(N-1):
    ZZ = z_arr(S[i:])
    # print(ZZ)
    temp_max = max(ZZ[1:])
    if answer < temp_max:
        answer = temp_max
print(answer)

Submission status: Wrong Answer

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

def solve():
  minlen = 0
  for start in range(N):
    if start+minlen >= N:
      return minlen
    length = minlen+1
    while start+length<=N:
      part_s = S[start: start+length]
      remain_s = S[start+length:]
      if part_s in remain_s:
        minlen = length
        length += 1
      else:
        break

print(solve())

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] and 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

N = int(input())
S = input()
answer = 0
for i in range(N-1):
    ZZ = z_arr(S[i:])
    temp_max = max(ZZ[1:])
    if answer < temp_max:
        answer = temp_max
print(answer)

Submission status: Wrong Answer

Solution code:

n = int(input())
ab = str(input())

ans = set([0])
lenab = len(ab)

for h in range(lenab):
    abc = ab[h:]
    lenabc = len(abc)
    i = 1; j = 0
    A = [0]*lenabc
    A[0] = lenabc
    while i < lenabc:
        while i+j < lenabc and abc[j] == abc[i+j] and j < i:
            j += 1
        if j == 0:
            i += 1
        else:
            A[i] = j
            ans.add(j)
            k = 1
            while lenabc - i > k < j - A[k] and j < i - k + 1:
                A[i + k] = A[k]
                k += 1
            i += k;
            j -= k

print(max(ans))

Submission status: Wrong Answer

Solution code:
n = int(input())
ab = str(input())

ans = set([0])
lenab = len(ab)

for h in range(lenab):
    abc = ab[h:]
    lenabc = len(abc)
    i = 1; j = 0
    A = [0]*lenabc
    A[0] = lenabc
    while i < lenabc:
        while i+j < lenabc and abc[j] == abc[i+j] and j < i:
            j += 1
        if j == 0:
            i += 1
        else:
            A[i] = j
            ans.add(j)
            k = 1
            while lenabc - i > k < j - A[k] and j < i:
                A[i + k] = A[k]
                k += 1
            i += k;
            j -= k

print(max(ans))

Submission status: Wrong Answer

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

    base = 37; mod = 10**9 + 9
    pw = None
    def rolling_hash(s):
        l = len(s)
        h = [0]*(l + 1)
        v = 0
        for i in range(l):
            h[i+1] = v = (v * base + ord(s[i])) % mod
        return h
    def setup_pw(l):
        nonlocal pw
        pw = [1]*(l + 1)
        v = 1
        for i in range(l):
            pw[i+1] = v = v * base % mod
    def get(h, l, r):
        return (h[r] - h[l] * pw[r-l]) % mod

    h = rolling_hash(S)
    setup_pw(len(S))

    ans = 0
    H = [set() for i in range(N//2+2)]
    D = [0]*N
    E = [0]*N
    for l in range(1, N//2+1):
        p = pw[l]
        D[:] = [None]*N
        for i in range(min(l, N-2*l+1)):
            D[i] = (h[l+i] - h[i]*p) % mod
        s = set()
        ok = 0
        for i in range(l, N-l+1):
            s.add(D[i-l])
            D[i] = v = (h[l+i] - h[i]*p) % mod
            if v in s:
                ok = 1
                break
        if ok:
            ans = l
            E[l] = 1
    print(ans)
solve()

Submission status: Wrong Answer

Solution code:
n = int(input())
ab = str(input())

ans = [0]
lenab = len(ab)

for h in range(lenab):
    abc = ab[h:]
    lenabc = len(abc)
    i = 1; j = 0
    while i < lenabc:
        while i+j < lenabc and abc[j] == abc[i+j] and j < i:
            j += 1
        if j == 0:
            i += 1
        else:
            ans.append(j)
            i += j
            j=0

print(max(ans))

Submission status: Wrong Answer

Solution code:

n = int(input())
sarr = input()

i, maxlen = 0, 0

while i + maxlen < n:
  s = sarr[i]
  j, l = 1, 1
  while i + j < n:
    candidate = sarr[i + j]
    if s == candidate:
      l = 1
      while (i + j + l < n) and (i + l < i + j) and (sarr[i + l] == sarr[i + j + l]):
        l += 1
      if l > maxlen:
        maxlen = l
    j += l
  i += l

print(maxlen)

Submission status: Wrong Answer

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

ans = 0
left, right = 0, 1

while right < N:
    s = S[left:right]
    if s in S[right:]:
        right += 1
        ans = max(ans, len(s))
    else:
        left, right = right, right + 1

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
ab = str(input())

ans = [0]
lenab = len(ab)
for h in range(lenab):
    abc = ab[h:]
    lenabc = lenab - h
    i = 1; j = 0
    while i < lenabc:
        while i+j < lenabc and abc[j] == abc[i+j] and j < i:
            j += 1
        if not j:
            i += 1
            continue
        ans.append(j)
        i = i+j
        j=0

print(max(ans))

Submission status: Wrong Answer

Solution code:

n = int(input())
sarr = input()

maxlen = 0

i = 0
while i < n:
  s = sarr[i]
  j, l = 1, 1
  while i + j < n:
    candidate = sarr[i + j]
    if s == candidate:
      l = 1
      while (i + j + l < n) and (i + l < i + j) and (sarr[i + l] == sarr[i + j + l]):
        l += 1
      if l > maxlen:
        maxlen = l
    j += l + 1
  i += l

print(maxlen)

Submission status: Wrong Answer

Solution code:
n = int(input())
ab = str(input())

ans = [0]
lenab = len(ab)
for h in range(lenab):
    abc = ab[h:]
    lenabc = lenab - h
    i = 1; j = 0
    while i < lenabc:
        while i+j < lenabc and abc[j] == abc[i+j] and j < i:
            j += 1
        if not j:
            i += 1
            continue
        ans.append(j)
        i = i+j

print(max(ans))

Submission status: Wrong Answer

Solution code:
n = int(input())
ab = str(input())

ans = set([0])
lenab = len(ab)
for h in range(lenab):
    abc = ab[h:]
    lenabc = lenab - h
    i = 1; j = 0
    while i < lenabc:
        while i+j < lenabc and abc[j] == abc[i+j] and j < i:
            j += 1
        if not j:
            i += 1
            continue
        ans.add(j)
        i = i+j

print(max(ans))

Submission status: Wrong Answer

Solution code:

n = int(input())
sarr = input()

maxlen = 0

i = 0
while i < n:
  s = sarr[i]
  j, l = 1, 1
  while i + j < n:
    candidate = sarr[i + j]
    if s == candidate:
      l = 1
      while (i + j + l < n) and (i + l < i + j) and (sarr[i + l] == sarr[i + j + l]):
        l += 1
      if l > maxlen:
        maxlen = l
    j += l
  i += l

print(maxlen)

Submission status: Wrong Answer

Solution code:
n = int(input())
ab = str(input())

ans = set([0])
lenab = len(ab)
for h in range(lenab):
    abc = ab[h:]
    lenabc = lenab - h
    A = [0] * lenabc
    i = 1; j = 0
    midlen = lenabc//2
    while i < lenabc:
        while i+j < lenabc and abc[j] == abc[i+j] and j < i:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        ans.add(j)
        i += i+j
        #k= 1
        # while lenabc-i > k < j - A[k]:
        #     A[i+k] = A[k]
        #     k += 1
        # i += k; j -= k

print(max(ans))

Submission status: Wrong Answer

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

slen = len(sarr)
maxlen = 0

i = 0
while i < n:
  s = sarr[i]
  for j, candidate in enumerate(sarr[i+1:]):
    if s == candidate:
      l = 1
      while (i + 1 + j + l < slen) and (i + l < i + 1 + j) and (sarr[i + l] == sarr[i + 1 + j + l]):
        l += 1
      if l > maxlen:
        maxlen = l
      i += l
      break
  i += 1

print(maxlen)

Submission status: Wrong Answer

Solution code:


class String:
    def __init__(self, s, hash):
        self.s = s
        self.hash = hash

    def __eq__(self, o):
        return self.s == o.s

    def __hash__(self):
        return self.hash

def main():
    from bisect import bisect_right
    import sys
    input = sys.stdin.readline
    N = int(input())
    S0 = input().strip()
    S = [ord(c) -ord('a')+1 for c in S0]
    H = 2**31-1
    B = 100

    m = 0
    for l in range(1, N//2+1)[::-1]:
        D = {}
        bl = B
        for i in range(l-1):
            bl = (bl * B) % H
        #print(l, "bl=",bl)
        h = 0
        for k in range(l):
            h = (h * B + S[k]) % H

        D[h] = 0
        #print(l, S0[:l],h)
        for i in range(1, N-l+1):
            #print("h=",h, "S[i-1]*bl",S[i-1]*bl) 
            h = (h * B - S[i-1] * bl + S[i+l-1]) % H

            if h in D:
                j = D[h]
                #print(l, i, j)
                if j + l <= i:
                    print(l)
                    return
                else:
                    #print("overlap", S0[i:i+l])
                    pass
            else:
                D[h] = i
        #print(l, S0, D)
        #print()
    print(m)

            


    

def gen():
    import random
    N = 5*10**3
    print(N)
    a = ord('a')
    #print("".join(chr(a + random.randint(0, 3)) for i in range(N)))
    print("".join("a" if i % 2 == 1 else "b" for i in range(N)))
if 1 == 0:
    gen()
else:
    main()

Submission status: Wrong Answer

Solution code:

n = int(input())
ab = str(input())

ans = set([0])
lenab = len(ab)
for h in range(lenab):
    abc = ab[h:]
    lenabc = lenab - h
    A = [0] * lenabc
    i = 1; j = 0
    midlen = lenabc//2
    while i < lenabc:
        while i+j < lenabc and abc[j] == abc[i+j] and j < i:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        ans.add(j)
        k= 1
        while lenabc-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k

print(max(ans))

Submission status: Wrong Answer

Solution code:

n = int(input())
ab = str(input())

ans = set([0])
lenab = len(ab)
for h in range(lenab):
    abc = ab[h:]
    lenabc = lenab - h
    A = [0] * lenabc
    i = 1; j = 0
    midlen = lenabc//2
    while i < lenabc:
        while i+j < lenabc and abc[j] == abc[i+j] and j < midlen:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        ans.add(j)
        k= 1
        while lenabc-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k

print(max(ans))

Submission status: Wrong Answer

Solution code:

n = int(input())
ab = str(input())

ans = set([0])
lenab = len(ab)
for h in range(lenab):
    abc = ab[h:]
    lenabc = lenab - h
    A = [0] * lenabc
    i = 1; j = 0
    midlen = lenabc//2
    while i < lenabc:
        while i+j < lenabc and abc[j] == abc[i+j] and j < midlen:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        ans.add(j)
        k= 1
        while lenabc-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k

print(max(ans))

Submission status: Wrong Answer

Solution code:
n=int(input())
s=input()
w=[[0]*n for i in range(n)]
ans=chk=0
for i in range(n-1,-1,-1):
    for j in range(n-1,-1,-1):
        if s[i]==s[j]:
            if i==n-1 or j==n-1:
                w[i][j]=1
            else:
                w[i][j]=w[i+1][j+1]+1
#print(w)
for i in range(1,n):
    for j in range(i):
        ans=max(ans,w[i][j])
        #ans=max(ans,w[i][j]-[0,w[i][j]-(i+1-j-w[i][j])][j+w[i][j]>=i])
print(ans)

Submission status: Wrong Answer

Solution code:

n = int(input())
ab = str(input())

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

lenab = len(ab)
for i in range(0, lenab):
    if ans > lenab - i - 1:
        break
    S = ab[i:]
    o = z_algo(S)
    ans = max(ans, o)

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
ab = str(input())

ans = 0
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

lenab = len(ab)
for i in range(0, lenab):
    if ans > lenab - i - 1:
        break
    S = ab[i:]
    o = z_algo(S)
    p = o[1:]
    p.append(ans)
    ans = max(p)

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
d = {}
for i in range(n):
  for j in range(i,n):
    if s[i:j+1] not in d:
      d[s[i:j+1]]=1
    else:
      d[s[i:j+1]]+=1
maxi=0
for i in d:
  if d[i]>1:
    maxi=max(maxi,len(i))
print(maxi)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
from heapq import *
sys.setrecursionlimit(200000)
input = sys.stdin.readline

N, = map(int, input().split())
# L = [int(v) for v in input().split()]
# L = [int(input()) for _ in range(Q)]
S = input().strip()

class RollingHash:
    def __init__(self, data):
        self.len = len(data)
        self.row = [0] * self.len
        for i in range(self.len):
            self.row[i] = ord(data[i]) * 73

    def build(self, count):
        self.data = [0] * (self.len - count + 1)
        first = 0
        for i in range(count):
            c = 10 ** (count - i - 1)
            first += self.row[i] * c

        self.data[0] = first

        for i in range(1, len(self.data)):
            c = self.data[i - 1] - self.row[i - 1] * (10 ** (count - 1))
            self.data[i] = c * 10 + self.row[i + count - 1]

    def get(self, index):
        return self.data[index]

roll = RollingHash(S)
t = N // 2 + 1
l = 0
r = t
for _ in range(20):
    i = (l + r) // 2
    roll.build(i)

    f = False
    for j in range(t - i + 1):
        ll = j
        rr = N - i + 1
        data = [v for v in roll.data[ll:ll+rr]]
        data.sort()

        ff = False
        target = roll.get(j)
        for _ in range(20):
            m = (ll + rr) // 2
            bb = roll.get(m)
            if target < bb:
                rr = m
            elif target > bb:
                ll = m
            else:
                ff = True
                break

        if ff:
            f = True
            break

    if f:
        l = i
    else:
        r = i

print((l + r) // 2)

Submission status: Wrong Answer

Solution code:

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

    for i in range(N // 2, max(N // 2 - 500, 0), -1):
        for j in range(N - i + 1):
            if S.find(S[j: i + j], i + j) > 0:
                print(i)
                exit()

    ok, ng = 0, N // 2 + 1 - 500
    while abs(ok - ng) > 1:
        x = (ok + ng) // 2
        for i in range(N - x + 1):
            if S.find(S[i: i + x], i + x) > 0:
                ok = x
                break
        else:
            ng = x

    print(ok)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
from heapq import *
sys.setrecursionlimit(200000)
input = sys.stdin.readline

N, = map(int, input().split())
# L = [int(v) for v in input().split()]
# L = [int(input()) for _ in range(Q)]
S = input().strip()

class RollingHash:
    def __init__(self, data):
        self.len = len(data)
        self.row = [0] * self.len
        for i in range(self.len):
            self.row[i] = ord(data[i]) * 73

    def build(self, count):
        self.data = [0] * (self.len - count + 1)
        first = 0
        for i in range(count):
            c = 10 ** (count - i - 1)
            first += self.row[i] * c

        self.data[0] = first

        for i in range(1, len(self.data)):
            c = self.data[i - 1] - self.row[i - 1] * (10 ** (count - 1))
            self.data[i] = c * 10 + self.row[i + count - 1]

    def get(self, index):
        return self.data[index]

roll = RollingHash(S)
t = N // 2 + 1
l = 0
r = t
for _ in range(20):
    i = (l + r) // 2
    roll.build(i)

    f = False
    for j in range(t - i + 1):
        for k in range(j + i, N - i + 1):
            if roll.get(j) == roll.get(k):
                f = True
                break

    if f:
        l = i
    else:
        r = i

print((l + r) // 2)

Submission status: Wrong Answer

Solution code:
import random

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

#長さnの文字列s
base1 = 1007
base2 = 2009
mod1 = 1000000007
mod2 = 1000000009

"""
modTank1 = [8570647,8570659,8570671,8570677,8570687,8570701,8570719,8570761,8570797,8571799]
modTank2 = [7777709,7777727,7777753,7777769,7777801,7777811,7777813,7777843,7777849,7777853]
mod1 = modTank1[random.randint(0,10)]
mod2 = modTank2[random.randint(0,10)]
"""

hash1 = [0]*(n+1)
power1 = [1]*(n+1)
hash2 = [0]*(n+1)
power2 = [1]*(n+1)

for i,e in enumerate(s):
    hash1[i+1] = (hash1[i]*base1 + ord(e))%mod1
    power1[i+1] = (power1[i]*base1)%mod1
    hash2[i+1] = (hash2[i]*base2 + ord(e))%mod2
    power2[i+1] = (power2[i]*base2)%mod2


res = 0
tank1 = set()
tank2 = set()
for i in range(1,n+1):
    for j in range(i+1,n+1):
        hash_key1 = (hash1[j]-hash1[i]*power1[j-i]%mod1)%mod1
        hash_key2 = (hash2[j]-hash2[i]*power2[j-i]%mod2)%mod2
        if hash_key1 in tank1 and hash_key2 in tank2:
            res = max(res,j-i)
        else:
            tank1.add(hash_key1)
            tank2.add(hash_key2)
print(res)

Submission status: Wrong Answer

Solution code:

def main():
    import time
    start_time = time.time()

    N = int(input())
    S = input()
    ok, ng = 0, N + 1
    while abs(ok - ng) > 1:
        x = (ok + ng) // 2
        for i in range(N - x + 1):
            if time.time() - start_time > 1.7:
                print(0)
                exit()

            if S.find(S[i: i + x], i + x) > 0:
                ok = x
                break
        else:
            ng = x

    print(ok)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import collections
mod=10**9+7
base=37
n=int(input())
S=list(ord(s)-96 for s in input())
B=[0]*(n+1)
B[0]=1
for i in range(n):
  B[i+1]=(B[i]*base)%mod

def chk(x):
  ret=False
  h=0
  bx=B[x]
  d=collections.defaultdict(int)
  for i in range(x):
    h=(h*base+S[i])%mod
  d[h]=x
  for i in range(x,n):
    h=(h*base+S[i]-S[i-x]*bx)%mod
    if d[h]==0:
      d[h]=i+1
    elif d[h]<=i-x+1:
      ret=True
  return ret

l,r=0,n//2
while r-l>1:
  m=(l+r)//2
  if chk(m):
    l=m
  else:
    r=m
print(r if chk(r) else l)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
high = n//2
low = 1
ans = 0

while low <= high:
    i = (high+low)//2
    s2 = set()
    for j in range(n-i*2+1):
        s2.add(s[i+j:])
        if s[j:i+j] in s2:
            if ans < i:
                ans = i
                low = i+1
                break
    if ans < i:
        high = i-1
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
mod=10**9+7
base=37
n=int(input())
S=list(ord(s)-96 for s in input())
B=[0]*(n+1)
B[0]=1
for i in range(n):
  B[i+1]=(B[i]*base)%mod

def chk(x):
  ret=False
  h=0
  bx=B[x]
  d=collections.defaultdict(int)
  for i in range(x):
    h=(h*base+S[i])%mod
  d[h]=x
  for i in range(x,n):
    h=(h*base+S[i]-S[i-x]*bx)%mod
    if d[h]==0:
      d[h]=i
    elif d[h]<=i-x:
      ret=True
  return ret

l,r=0,n//2
while r-l>1:
  m=(l+r)//2
  if chk(m):
    l=m
  else:
    r=m
print(r if chk(r) else l)

Submission status: Wrong Answer

Solution code:
import collections
mod=10**9+7
base=37
n=int(input())
S=list(ord(s)-96 for s in input())
B=[0]*(n+1)
B[0]=1
for i in range(n):
  B[i+1]=(B[i]*base)%mod

def chk(x):
  ret=False
  h=0
  bx=B[x]
  d=collections.defaultdict(int)
  for i in range(x):
    h=(h*base+S[i])%mod
  d[h]=x
  for i in range(x,n):
    h=(h*base+S[i]-S[i-x]*bx)%mod
    if d[h]==0:
      d[h]=i
    elif d[h]<=i-x:
      ret=True
  return ret

l,r=0,n//2
while r-l>1:
  m=(l+r)//2
  if chk(m):
    l=m
  else:
    r=m
print(l)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

n = I()
s = S()


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


ret = 0
for i in range(n):
    ret = max(ret, max(z_algo(s[i:])))



print(ret)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline


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

        dp = [[0] * (N + 1)] * (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

        ans = 0
        for i in range(N)[::-1]:
            for j in range(N)[::-1]:
                if i >= j:
                    continue
                else:
                    ans = max(ans, min(dp[i][j], j - i))
        print(ans)


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

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline


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

        dp = [[0] * N] * N
        ans = 0
        for i in range(N)[::-1]:
            for j in range(N)[::-1]:
                if i == N - 1 or j == N - 1:
                    if S[i] == S[j]:
                        dp[i][j] = min(1, abs(i - j))
                        ans = max(ans, dp[i][j])
                else:
                    if S[i] == S[j]:
                        dp[i][j] = min(dp[i + 1][j + 1] + 1, abs(i - j))
                        ans = max(ans, dp[i][j])
        print(ans)


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

Submission status: Wrong Answer

Solution code:
import sys

stringCount = int(input())
targetString = input()

maxCount = stringCount // 2

for exclusionCount in range(maxCount):
    count = maxCount - exclusionCount

    for i in range(maxCount):
        if (i + count * 2) > stringCount:
            break

        word = targetString[i:count]
        if (targetString.count(word) > 1):
            print('{}'.format(count))
            sys.exit()

print('0')

Submission status: Wrong Answer

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

def build_suffix_array(s):
  sa = []
  for i in range(len(s)):
    sa.append((s[i:],i+1))
  sa.sort()
  return sa

ans = 0
sa = build_suffix_array(S)
for i in range(N-1):
  s1,k1 = sa[i+0]
  s2,k2 = sa[i+1]
  #print('{}({}) vs {}({})'.format(s1,k1,s2,k2))
  for n in range(1,1+min(len(s1),len(s2))):
    #print('    {}: {} vs {}'.format(n,s1[:n],s2[:n]))
    #print('    {}: {} vs {}'.format(n,(k1,k1+n-1),(k2,k2+n-1,)))
    if s1[n-1] != s2[n-1]:
      break
    if not min(k1,k2)+n-1 < max(k1,k2):
      break
    #print('    OK! n={}'.format(n))
    ans = max(ans,n)
print(ans)

Submission status: Wrong Answer

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

def build_suffix_array(s):
  sa = []
  for i in range(len(s)):
    sa.append((s[i:],i+1))
  sa.sort()
  return sa

ans = 0
sa = build_suffix_array(S)
for i in range(N-1):
  s1,k1 = sa[i+0]
  s2,k2 = sa[i+1]
  #print('{}({}) vs {}({})'.format(s1,k1,s2,k2))
  for n in range(1,1+min(len(s1),len(s2))):
    #print('    {}: {} vs {}'.format(n,s1[:n],s2[:n]))
    #print('    {}: {} vs {}'.format(n,(k1,k1+n-1),(k2,k2+n-1,)))
    if s1[n-1] != s2[n-1]:
      break
    if min(k1,k2)+n-1 >= max(k1,k2):
      break
    #print('    OK! n={}'.format(n))
    ans = max(ans,n)
print(ans)

Submission status: Wrong Answer

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

for i in range(n):
    for j in range(i+1, n+1):
        if (s[i:j] in s[j:]) == True and ans < len(s[i:j]):
            ans = len(s[i:j])
        else:
            break
print(ans)