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:
def solve(n, s, d, MOD):
    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)

    l, r = 0, n // 2 + 1
    while l < r:
        m = (l + r + 1) // 2
        if search(m, d, ttc, MOD):
            l = m
        else:
            r = m - 1

    return l


def search(w, d, ttc, MOD):
    appeared = []
    comparing = set()
    w2 = w * 2
    p = 1

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

    return False


n = int(input())
s = input()
MOD = 10 ** 9 + 7
print(min(solve(n, s, d, MOD) for d in (29, 31)))

Submission status: Accepted

Solution code:
def solve(n, s, d, MOD):
    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)

    l, r = 0, n
    while l < r:
        m = (l + r + 1) // 2
        if search(m, d, ttc, MOD):
            l = m
        else:
            r = m - 1

    return l


def search(w, d, ttc, MOD):
    appeared = []
    comparing = set()
    w2 = w * 2
    p = 1

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

    return False


n = int(input())
s = input()
MOD = 10 ** 9 + 7
print(min(solve(n, s, d, MOD) for d in (26, 29, 31)))

Submission status: Accepted

Solution code:
n = int(input())
s = input()
dp = [0]*n
j = 1

for i in range(n):
    while s[i:j] in s[j:n]:
        j += 1
    dp[i] = j-i-1
print(max(dp))

Submission status: Accepted

Solution code:
N = int(input())
S = input()
i = j = 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)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
l=0
r=n//2
while r-l>=1:
    m=(r+l+1)//2
    d={}
    flg=False
    for i in range(n-m+1):
        t=s[i:i+m]
        if t in d:
            if d[t]+m-1<i:
                flg=True
                break
        else:
            d[t]=i
    if flg:
        l=m
    else:
        r=m-1
print(l)

Submission status: Accepted

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

ans = 0
lenS = 1
for i in range(n):
	tempS = s[i:i+lenS]
	while (tempS in s[i+lenS:]):
		lenS += 1
		tempS = s[i:i+lenS]
		ans += 1
	if (i + 2*lenS>= n):
		break
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
from collections import deque

def is_ok(l):
    hs = set()
    q = deque()
    for i in range(N-l+1):
        h = S[i:i+l]
        if h in hs:
            return True
        q.append(h)
        if len(q) >= l:
            hs.add(q.popleft())
    return False

ok = 0
ng = N//2+1
while ng-ok > 1:
    m = (ng+ok)//2
    if is_ok(m):
        ok = m
    else:
        ng = m
print(ok)

Submission status: Accepted

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

# Z-algorithm (A[i] = (Longest Common Profix of S and S[i:]))
# demonstrate in the case S = 'aaabaaab'
def LCP(S, N):
    A = [N] + [0] * (N - 1)
    max_length = 0
    i, j = 1, 0
    while i < N:
        while i + j < N and S[j] == S[i + j]:
            j += 1
        A[i] = j
        max_length = min(max(max_length, j), i)
        if j == 0:
            i += 1
            continue
        else:
            k = 1
            while i + k < N and k + A[k] < j:
                A[i + k] = A[k]
                max_length = min(max(max_length, A[k]), i + k)
                k += 1
            i += k
            j -= k
    return max_length

ans = 0
for i in range(N):
    cand = LCP(S[i:], N - i)
    ans = max(ans, cand)

print(ans)

Submission status: Accepted

Solution code:
n,s=open(0);a=i=j=0
while s[j:]:f=s[i:j]in s[j:];a=max(a,j*f-i);j+=f;i+=f^1
print(a)

Submission status: Accepted

Solution code:
import math
import collections
import itertools
import sys
import bisect
from heapq import heappop,heappush
sys.setrecursionlimit(10**6)
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

n = INT()
s = input()

a=0
i=0
j=1

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

print(a)

Submission status: Accepted

Solution code:
n,s=open(0);a=i=j=0
while j<int(n):f=s[i:j]in s[j:];a=max(a,j*f-i);j+=f;i+=f^1
print(a)

Submission status: Accepted

Solution code:
n,s=open(0);a=i=j=0
while j<int(n):f=s[i:j]in s[j:];a=max(a,(j-i)*f);j+=f;i+=f^1
print(a)

Submission status: Accepted

Solution code:
n,s=open(0);a=i=j=0
while j<int(n):
 if s[i:j]in s[j:]:a=max(a,j-i);j+=1
 else:i+=1
print(a)

Submission status: Accepted

Solution code:
n,s=open(0);a=i=j=0
while j<int(n):
 t=s[i:j]
 if t in s[j:]:a=max(a,j-i);j+=1
 else:i+=1
print(a)

Submission status: Accepted

Solution code:
def z_algorithm(s):
    N = len(s)
    A = [0]*N
    A[0] = N
    i,j = 1,0
    while i < N:
        while i+j < N and s[j] == s[i+j]:
            j += 1
        if j == 0:
            i += 1
            continue
        A[i] = j
        k = 1
        while i+k < N and k+A[k] < j:
            A[i+k] = A[k]
            k += 1
        i += k
        j -= k
    return A

N = int(raw_input())
S = raw_input()

ans = 0
for i in range(N):
    s = S[i:]
    lcp = z_algorithm(s)
    for j,p in enumerate(lcp):
        t = min(j, p)
        ans = max(ans, t)

print ans

Submission status: Accepted

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

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

dp = [[0] * N for i in range(N)]
max_leng2 = 0 
for i in range(0, N):
    leng2 = 0

    j = i - 1
    while j > -1:
        if S[i] == S[j]:
            sta_j = j
            if j != 0:
                leng2 = dp[i-1][sta_j-1] + 1
            else: 
                leng2 = 1
            
            if i - sta_j < leng2:
                leng2 = i - sta_j
                
            dp[i][sta_j] = leng2
            max_leng2 = max(max_leng2, leng2)
        j -= 1
print(max_leng2)

Submission status: Accepted

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

ans = 0
lenS = 1
for i in range(n):
	tempS = s[i:i+lenS]
	while (tempS in s[i+lenS:]):
		lenS += 1
		tempS = s[i:i+lenS]
		ans += 1

print(ans)

Submission status: Accepted

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 += 1

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-



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

r,i,j = 0,0,0
while j < N:
  t = S[i:j]
  if t in S[j:]:
    r = max(r,j-i)
    j += 1
  else:
    i += 1
print(r)

Submission status: Accepted

Solution code:
def main():
  n=int(input())
  s=t=input()
  a=0
  for i in range(n):
    c=0
    for v,w in zip(s,t):
      if v==w:c+=1
      else:c=0
      if c>i:break
      if c>a:a=c
    t=t[1:]
  print(a)
main()

Submission status: Accepted

Solution code:
N = int(input())
S = list(input())
#LCSRe i番目とj番目でそれぞれ終わるような共通文字列の長さ
#i < j であるi文字目とj文字目が等しいならLCSRe[i + 1][j + 1] = LCSRe[i][j] + 1
#res_lengthよりLCSReの更新した値が大なら、その時のindexをiへ、res_lengthも更新

def longestRepeatedSubstring(s): 
  n = len(s) 
  LCSRe = [[0 for _ in range(n + 1)] for _ in range(n + 1)] 
  res = "" 
  res_length = 0
  index = 0
  for i in range(1, n + 1): 
    for j in range(i + 1, n + 1): 
      if s[i - 1] == s[j - 1] and LCSRe[i - 1][j - 1] < j - i: 
        LCSRe[i][j] = LCSRe[i - 1][j - 1] + 1
        if LCSRe[i][j] > res_length: 
          res_length = LCSRe[i][j] 
          index = max(i, index) 
      else: 
        LCSRe[i][j] = 0
  #print(LCSRe)
  if res_length > 0: 
    for i in range(index - res_length + 1, index + 1): 
      res = res + s[i - 1] 
  return res_length
print(longestRepeatedSubstring(S))

Submission status: Accepted

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:]:
        ans = max(ans, len(s))
        right += 1
    else:
        left += 1

print(ans)

Submission status: Accepted

Solution code:
from subprocess import*
with open('e.cpp','w')as f:f.write(r"""
#include<iostream>
using namespace std;
main(){
  int n;
  string s;
  cin>>n>>s;
  int a=0;
  for(int i=0;i<n;++i){
    int t=0;
    for(int j=0;j<n-i;++j){
      t=(t+1)*(s[j]==s[j+i]);
      a=max(a,min(t,i));
    }
  }
  cout<<a;
}""")
call(('g++','e.cpp'))
call('./a.out')

Submission status: Accepted

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

ok, ng = 0, n//2+1
while ng-ok > 1:
	x = (ok+ng)//2
	possible = False
	d = set()
	for i in range(n-2*x+1):
		d.add(hash(s[i:i+x]))
		if hash(s[i+x:i+2*x]) in d:
			possible = True
			break
	if possible:
		ok = x
	else:
		ng = x
print(ok)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# input=sys.stdin.readline
def resolve():
    n=int(input())
    s=input()
    dp=[[0]*(n+1) for _ in range(n+1)]
    from itertools import product
    for i,j in product(reversed(range(n)),repeat=2):
        if i>=j: continue # i<j
        if s[i]==s[j]:
            dp[i][j]=dp[i+1][j+1]+1
        else:
            dp[i][j]=0
    ans=0
    for i,j in product(reversed(range(n)),repeat=2):
        if i>=j: continue
        ans=max(ans,min(j-i,dp[i][j]))
    print(ans)


resolve()

Submission status: Accepted

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

OK = 0
NG = N // 2 + 1

while abs(OK - NG) > 1:
    mid = (OK + NG) // 2
    if check(mid):
        OK = mid
    else:
        NG = mid

print(OK)

Submission status: Accepted

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

F = [1] * (N//2 + 2)
for i in range(1, len(F)):
    F[i] = F[i] * 26

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

OK = 0
NG = N // 2 + 1

while abs(OK - NG) > 1:
    mid = (OK + NG) // 2
    if check(mid):
        OK = mid
    else:
        NG = mid

print(OK)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
r,i,j=0,0,0
while j<n:
    t=s[i:j]
    if t in s[j:]:r=max(r,j-i);j +=1
    else:i +=1
print(r)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
def check(l):
  D = {}
  for i in range(N-l+1):
    s = S[i:i+l]
    if s not in D:
      D[s] = i
      continue
    if D[s]+l <= i:
      return True
  return False
a = 1
b = N
while a < b:
  i = (a + b)//2
  if not check(i):
    b = i
  else:
    if a == i:
      break
    a = i
r = b-1
print(r)

Submission status: Accepted

Solution code:
import sys
import heapq
import bisect

mod = 10**9+7
dd = ((-1,0),(1,0),(0,-1),(0,1))

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def S(): return(list(sys.stdin.readline())[:-1])

def main():
    N = I()
    s = S()
    dp = [[0 for _ in range(N)] for _ in range(N)]

    for i in range(N-1,-1,-1):
        for j in range(N-1,-1,-1):
            if s[i] == s[j]:
                if i+1<=N-1 and j+1<=N-1:
                    dp[i][j] = dp[i+1][j+1]+1
                else:
                    dp[i][j] = 1

    ans = 0
    for i in range(N):
        for j in range(N):
            if dp[i][j] > ans and i + dp[i][j] <= j:
                ans = dp[i][j]
    return(ans)

if __name__ == "__main__":
    print(main())

Submission status: Accepted

Solution code:
n = int(input())
S = input()
N = [0]*n
j = 0
 
for i in range(n):
  while S[i:j] in S[j:n]:
    N[i] = j-i
    j += 1
    
print(max(N))

Submission status: Accepted

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

def main():
    N = int(input())
    S = input()
    #N = 5000
    #S = "a"*N
    import time
    star = time.time()
    A = [[] for i in range(N)]
    for i in range(N):
        A[i] = [0]*i + z_algo(S[i:])
    ans = 0
    for i in range(N):
        for j in range(N):
            if i + A[i][j] <= j and ans < A[i][j]:
                ans = A[i][j]
    
    g = time.time()
    #print(g-star)
    print(ans)
    
main()

Submission status: Accepted

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

Submission status: Accepted

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

r=0
i=j=0
while j < N:
    t = S[i:j]
    if t in S[j:]:
        r = max(r, j-i)
        j += 1
    else:
        i += 1
print(r)

Submission status: Accepted

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:N] - Hcum[:N-n+1] + H[:N-n+1]) % MOD
    x *= power_inv[:N-n+1]
    x %= MOD
    # 距離n以上離れたところで連番が存在しないといけない
    ind = np.lexsort((np.arange(N-n+1),x))
    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] = 1
    is_right_end = np.zeros(N-n+1,np.bool)
    is_right_end[:-1] = (x[:-1] != x[1:])
    is_right_end[-1] = 1
    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: Accepted

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

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

left = 0
right = N // 2 + 1
while right - left > 1:
  mid = left + (right - left) // 2
  if check(mid):
    left = mid
  else:
    right = mid
print(left)

Submission status: Accepted

Solution code:
n = int(input())
S = input()
N = [0]*n
j = 0

for i in range(n):
  while S[i:j] in S[j:n]:
    N[i] = j-i
    j += 1
    
print(max(N))

Submission status: Accepted

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

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

n = 1
ans = 0
for i in range(N):
    s = S[i:i + n]
    while S[i + n:].find(s) != -1:
        n += 1
        s = S[i:i + n]
        ans += 1

print(ans)

Submission status: Accepted

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

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

n = 1
ans = 0
for i in range(N):
    s = S[i:i + n]
    while s in S[i + n:]:
        n += 1
        s = S[i:i + n]
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
l=0;r=0;ans=0
while r<n:
  t=s[l:r]
  if t in s[r:n]:
    ans=max(ans,len(t))
    r+=1
  else:
    l+=1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
r = 0
i = j = 0
while j < N:
  t = S[i:j]
  if t in S[j:]:
    r = max(r, j-i)
    j += 1
  else:
    i += 1
print(r)

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
s = input()
dp = [[0]*(n+1) for _ in range(n+1)]
dp[-1][-1] = 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):
    for j in range(n):
        ans = max(ans,min(i-j,dp[i][j]))
print(ans)

Submission status: Accepted

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:N] - Hcum[:N-n+1] + H[:N-n+1]) % MOD
    x *= power_inv[:N-n+1]
    x %= MOD
    for i,a in np.ndenumerate(x):
        if (x[i[0]+n:] == a).any():
            return True
    return False

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

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

ok, ng = 0, n//2+1
while ng-ok > 1:
	x = (ok+ng)//2
	possible = False
	d = set()
	for i in range(n-2*x+1):
		d.add(s[i:i+x])
		if s[i+x:i+2*x] in d:
			possible = True
			break
	if possible:
		ok = x
	else:
		ng = x
print(ok)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
r = 0
i = j = 0
while j < N:
  t = S[i:j]
  if t in S[j:]:
    r = max(r, j-i)
    j += 1
  else:
    i += 1
print(r)

Submission status: Accepted

Solution code:
tmp = 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
print(max_len)

Submission status: Accepted

Solution code:
P = 123456789012419
x = 31
ix = pow(x, P-2, P)
N = int(input())
A = [ord(s)-95 for s in input()]

def chk(k):
    D = {}
    s = 0
    for i in range(k):
        s = (s * x) % P
        s += A[i]
    X = [s]
    D[s] = k-1
    for i in range(k, N):
        s = ((s - pow(x, k-1, P) * A[i-k]) * x + A[i]) % P
        X.append(s)
        if s in D:
            if i - D[s] >= k:
                return 1
        else:
            D[s] = i
    return 0

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

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque


def check(num, s, left, right):

    if right - left <= 1:
        print(left)
        sys.exit()

    half = (left + right) // 2

    data_set = set()

    for i in range(num -2 * half  + 1):
        now_str = s[i:i + half]
        data_set.add(now_str)
        if s[i + half : i + 2 * half] in data_set:
            check(num, s, half, right)
    check(num, s, left, half)

def main():
    num = int(input())
    s = input()

    left, right = 0, num // 2 + 1

    check(num, s, left, right)




if __name__ == '__main__':
    main()

Submission status: Accepted

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

r = 0
ans = 0

for l in range(N):

    while True:
        
        if S.rfind(S[l:r+1]) >= r+1:
            r += 1
            ans = max(ans, r-l)
        else:
            break

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
S=input()
a=i=j=0
while j<N:
  t=S[i:j]
  if t in S[j:]:
    a=max(a,len(t))
    j+=1
  else:
    i+=1
print(a)

Submission status: Accepted

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


r = 0
ans = 0
for l in range(N):

    while True:
        # print(S.rfind(S[l:r+1]), S[l:r+1], l, r)
        
        if S.rfind(S[l:r+1]) >= r+1:
            r += 1
            ans = max(ans, r-l)
        else:
            break

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
m=0
for i in range(1,n):
    d,c=0,0
    for j in range(i,n):
        if s[j-i]==s[j]:c+=1
        else:
            d=max(c,d)
            c=0
    m=min(max(c,d,m),i)
print(m)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    N = int(input())
    S = input()
    dp = [0] * N
    j = 1
    for i in range(N):
        while S[i:j] in S[j:N]:
            dp[i] = j-i
            j += 1
    print(max(dp))

Submission status: Accepted

Solution code:
n,s=open(0);n=int(n);a=i=j=0
while j<n:
	t=s[i:j]
	if t in s[j:]:a=max(a,len(t));j+=1
	else:i+=1
print(a)

Submission status: Accepted

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

res = 0

for k in range(1,n):
    d = [0]*n
    for i in range(n-k):
        if i+k <= n-1 and s[i] == s[i+k]:
            d[i] = min(k,d[i-1]+1)
            res = max(res,d[i])
print(res)

Submission status: Accepted

Solution code:
n,s=open(0);n=int(n)
a=i=0;j=1
while j<n:
	if s[i:j]in s[j:]:a=max(a,len(s[i:j]));j+=1
	else:i+=1
print(a)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
l,r=n//2+1,0
while l-r>1:
    t=(l+r)//2
    g=s[:t]
    q={}
    q[s[t:2*t]]=1
    d=s[t:2*t]
    for i in range(2*t,n):
        d=d[1:]+s[i]
        if d in q:
            q[d]+=1
        else:
            q[d]=1
    if g in q:
        r=t
    else:
        d=s[t:2*t]
        for i in range(t,n-t):
            q[d]-=1
            if q[d]==0:
                del q[d]
            d=d[1:]+s[i+t]
            g=g[1:]+s[i]
            if g in q:
                r=t
                break
        else:
            l=t
print(r)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
S = input()
from collections import deque

def is_ok(l):
    hs = set()
    q = deque()
    for i in range(N-l+1):
        h = hash(S[i:i+l])
        if h in hs:
            return True
        q.append(h)
        if len(q) >= l:
            hs.add(q.popleft())
    return False

ok = 0
ng = N//2+1
while ng-ok > 1:
    m = (ng+ok)//2
    if is_ok(m):
        ok = m
    else:
        ng = m
print(ok)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

# Rolling Hash
LEN=len(S)

p=26# 文字の種類
mod=(1<<50)+1# Hashがぶつからない, pと互いに素な数を適当に指定

TABLE=[0]# Rolling Hashのテーブル. 最初は0

for i in range(LEN):
    TABLE.append((p*TABLE[-1]%mod+ord(S[i])-97)%mod)# テーブルを埋める

def hash_ij(i,j): # [i,j)のハッシュ値を求める
    return (TABLE[j]-TABLE[i]*pow(p,j-i,mod))%mod


MIN=0
MAX=LEN//2

from collections import defaultdict

while MIN!=MAX:
    x=(MIN+MAX+1)//2
    DICT=defaultdict(list)

    for i in range(LEN-x+1):
        DICT[hash_ij(i,i+x)].append(i)

    #print(DICT,MIN,MAX,x)

    for l in DICT:
        if max(DICT[l])-min(DICT[l])>=x:
            MIN=x
            break
    else:
        MAX=x-1

print(MIN)

Submission status: Accepted

Solution code:
n,s=open(0);n=int(n)
a=i=0;j=1
while j<n:
	if s[i:j]in s[j:]:a=max(a,len(s[i:j]));j+=1
	else:i+=1
	if i==j:i+=1;j+=2
print(a)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
ans = 0
right = 0
for left in range(N):
    while S[left:right + 1] in S[right + 1:]:
        ans = max(ans, right + 1 - left)
        right += 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs , heapq as hq
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k][0] ==  x:
        return True
    else:
        return False

def search(a,n):
    se = dict()
    for i in range(0,len(a)-n+1):
        kkk = a[i:i+n]
        kkk = "".join(kkk)
        if kkk in se:
            if se[kkk] <= i-n:
                    return True
        else:
            se[kkk] = i
    return False


n = onem()

s = list(input())
l = 0
r = n//2
while True:
    mid = -(-(l+r)//2)
    ans = search(s,mid)
    if l == mid:
        break
    if ans:
        l = mid
    else:
        r = mid-1
print(l)

Submission status: Accepted

Solution code:
"""
N = int(input())
A, B = map(int,input().split())
A = list(map(int,input().split())) ## 横一列
A = [int(input()) for _ in range(N)] ## 縦一列
lst = [list(map(int,input().split())) for i in range(M)] ## 二次元
"""

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

#N = int(5e3)
#S = 'a' *N

ans = 0
for circ in range(1, N):
  cnt = 0
  solver = [0]
  for i in range(N-circ):
    if S[i] == S[i+circ]:
      cnt += 1
    else:
      solver.append(cnt)
      cnt = 0
  else:
    solver.append(cnt)
  ans = max(ans, min(circ, max(solver)))

print(ans)




"""
ans = 0
for i in range(N-1):
  if i+1+ans >= N:
    break
  lst = [0]
  for j in range(i+1+ans,N):
    cnt = 0
    if S[i] == S[j]:
      cnt += 1
      for k in range(1,min(j-i, N-j)):
        if S[i+k] == S[j+k]:
          cnt += 1
        else:
          break
    lst.append(cnt)
    #print(i, j, cnt)
  ans = max(ans, max(lst))
  
print(ans)
"""

Submission status: Accepted

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


r = 1
ans = 0
for l in range(N):

    while True:
        #print(S.rfind(S[l:r+1]), S[l:r+1], l, r)

        if S.rfind(S[l:r+1]) >= r+1:
            r += 1
            ans = max(ans, r-l)
        else:
            break

print(ans)

Submission status: Accepted

Solution code:
import sys

def main():
    _,S = open(0).read().split()
    s1 = S[:int(len(S)*3/4)+1]

    maxLen = 0
    lenS1 = len(s1)
    for i in range(lenS1):
        for j in range(i+1+maxLen,lenS1):
            # print(s1[i:j], S[j:], j,i)
            if len(s1[i:j]) > len(S[j:]):
                break
            if s1[i:j] in S[j:]:
                maxLen = j-i
            else:
                break

    print(maxLen)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import re
import sys


def solve(N: int, S: str):
    max_length = 1
    found = False
    for i in range(N):
        is_break = False
        if i + max_length > N:
            break
        while not is_break:
            org = S[i:i + max_length]
            rest = S[i + max_length:N]
            # print(org, rest)
            if org in rest:
                max_length += 1
            else:
                is_break = True
    print(max_length - 1)
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)

if __name__ == '__main__':
    main()

Submission status: Accepted

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[j] == S[i+j]:
            cnt += 1
            if cnt == i:
                ans = max(ans, i)
                break
        else:
            ans = max(ans, cnt)
            cnt = 0
    ans = max(ans, cnt)
print(ans)