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: Accepted

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

# Build LCP array by Z-algorithm
def build_lcp(s):
  lcp = [0]*len(s)
  j = 0
  for i in range(1,len(s)):
    if i+lcp[i-j] < j+lcp[j]:
      lcp[i] = lcp[i-j]
    else:
      k = max(0,j+lcp[j]-i)
      while i+k < len(s) and s[k] == s[i+k]:
        k += 1
      lcp[i] = k
      j = i
  lcp[0] = len(s)
  return lcp

ans = 0
for i in range(N):
  lcp = build_lcp(S[i:])
  #print('{}: {}'.format(i,S[i:]))
  #print('{}: {}'.format(i,lcp))
  for j in range(1,len(S[i:])):
    #print('    j={} lcp[j]={}  {}'.format(j,lcp[j],i+lcp[j]))
    if lcp[j] <= j:
      #print('    OK!')
      ans = max(ans,lcp[j])
print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    S = input()
    ok, ng = 0, N + 1
    while abs(ok - ng) > 1:
        x = (ok + ng) // 2
        check = set()
        for i in range(N - x + 1):
            check.add(S[i: i + x])
            if S[i + x: i + 2 * x] in check:
                ok = x
                break
        else:
            ng = x

    print(ok)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

dp = [[0]*(n+1) for _ in range(n+1)]
res = 0
for i in range(n-1,-1,-1):
    for j in range(n-1,i,-1):
        if s[i]==s[j]:
            dp[i][j] = dp[i+1][j+1]+1
        res = max(res, min(dp[i][j], j-i))

print(res)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

ok = 0
ng = n//2+1

while ng-ok>1:
    mid = (ok+ng)//2

    d = {}
    isOk = False
    for l in range(n-mid+1):
        ss = s[l:l+mid]
        if ss not in d:
            d[ss] = l
        else:
            l2 = d[ss]
            if l2+mid<=l:
                isOk = True
                break

    if isOk:
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Accepted

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:
      if S[d[h]-x:d[h]]==S[i-x+1:i+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: Accepted

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

dp = [[0] * (n + 1) for _ in range(n + 1)]

res = 0
for i in range(n - 1, -1, -1):
    for j in range(n - 1, i, -1):
        if s[i] == s[j]:
            dp[i][j] = dp[i + 1][j + 1] + 1
            # dp[i][j] = max(dp[i][j], dp[i + 1][j + 1] + 1)
        res = max(res, min(dp[i][j], j - i))
print(res)

Submission status: Accepted

Solution code:
import collections
mod=10**9+7
base=257
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: Accepted

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


    ret = 0
    for p in range(l):
        if p >= A[p] > ret:
            ret = A[p]
    return ret


ans = 0
for i in range(n):
    ans = max(ans, z_algorithm(s[i:]))



print(ans)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

sn = lambda : stdin.readline().rstrip()
an = lambda : map(int, stdin.readline().split())
ni = lambda : int(sn())

def main():
  n = ni()
  s = sn()

  i, j = 0, 1
  ans = 0
  while j < n:
    if s[i:j] in s[j:]:
      ans = max(ans, len(s[i:j]))
      j += 1
    else:
      i += 1
    if i == j:
      i += 1
      j += 2
  print(ans)

main()