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:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def Z_algorithm(s):
        n = len(s)
        z = [0]*n
        z[0] = n
        c = 1
        for i in range(1,n):
            if i+z[i-c] < c+z[c]:
                z[i] = z[i-c]
            else:
                j = max(0,c+z[c]-i)
                while i+j < n and s[j] == s[i+j]:
                    j += 1
                z[i] = j
                c = i
        return z
    n = I()
    s = input()
    ans = 0
    for i in range(n):
        z = Z_algorithm(s[i:])
        for j in range(n-i):
                ans = max(ans,min(j,z[j]))
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
n=int(input())
s=list(map(ord,list(input())))
for i in range(n):s[i]-=97

from random import randint
roli_mod=1370757747362922367
roli_r=randint(2,roli_mod-2)
roli=[0]
roli_rr=1
for i in range(n):
  roli.append((roli[-1]+roli_rr*s[i])%roli_mod)
  roli_rr*=roli_r
  roli_rr%=roli_mod
def roli_hash(i,j):return ((roli[j+1]-roli[i]+roli_mod)%roli_mod)*pow(roli_r,roli_mod-1-i,roli_mod)%roli_mod
def roli_check(i1,j1,i2,j2):return roli_hash(i1,j1)==roli_hash(i2,j2)

ok=0
ng=(n+1)//2+1
while ok+1!=ng:
  i=(ok+ng)//2
  d={}
  f=False
  for j in range(n-i+1):
    h=roli_hash(j,j+i-1)
    if h in d:
      if j-d[h]>=i:
        f=True
        break
    else:d[h]=j
  if f:ok=i
  else:ng=i
print(ok)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
dp = [[0] * (n + 1) for _ in range(n + 1)]
ans = 0
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        if s[i] == s[j]:
            dp[i + 1][j + 1] = dp[i][j] + 1
            ans = max(ans, min(abs(i - j), dp[i][j]+1))
print(ans)

Submission status: Accepted

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

#二分探索
N = ir()
S = sr()

def check(x):
    # x文字右側にずらした場所を調べる
    candidate = set()
    for i in range(N - 2*x + 1):
        candidate.add(S[i:i+x])
        if S[i+x:i+2*x] in candidate:
            return True
    return False

ok = 0; ng = N
while abs(ng-ok) > 1:
    mid = (ok+ng) // 2
    if check(mid):
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Accepted

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


n = int(input())
s = input()
ans = 0
for i in range(n):
    lcp = Z_algo(s[i:])
    for j, p in enumerate(lcp):
        tmp = min(j, p)
        ans = max(ans, tmp)
print(ans)

Submission status: Accepted

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

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

for i in reversed(range(N)):
    for j in reversed(range(N)):
        if i >= j:
            continue
        if S[i] != S[j]:
            dp[i][j] = 0
        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):
        if i >= j:
            continue
        now = min([dp[i][j], j-i])
        ans = max(ans, now)

print(ans)

Submission status: Accepted

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

def main():
    N = int(input())
    s = input()
    a,i,j = 0,0,1
    
    while j < N:
        if s[i:j] in s[j:]:
            a = max(a,j-i)
            j += 1
        else:
            i += 1
        if i == j:
            j += 1
            
    print(a)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np

n = int(input())
s = np.array(list(input()))

l = s.size

dp = np.zeros(l, dtype=np.int16)
ans = 0
for i, e in enumerate(s, 1):
    dp_prev = dp.copy()
    mx = np.arange(1, l + 1) - i
    idx = np.hstack([np.full(i, False), s[i:] == e]).astype(np.bool)
    idx_prev = np.roll(idx, -1)
    dp = np.zeros(l, dtype=np.int16)
    dp[idx] = np.minimum(dp_prev[idx_prev] + 1, mx[idx])
    ans = max(ans, dp.max())

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

n = int(input())
s = np.array(list(input()))

l = s.size

dp = np.zeros(l, dtype=np.int16)
ans = 0
for i, e in enumerate(s, 1):
    dp_prev = dp[:]
    mx = np.arange(1, l + 1) - i
    idx = np.hstack([np.full(i, False), s[i:] == e]).astype(np.bool)
    idx_prev = np.hstack([np.full(i-1, False), s[i:] == e, False]).astype(np.bool)
    dp = np.zeros(l, dtype=np.int16)
    dp[idx] = np.minimum(dp_prev[idx_prev] + 1, mx[idx])
    ans = max(ans, dp.max())

print(ans)

Submission status: Accepted

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

l = len(s)

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

ans = 0
for i, ei in enumerate(s, 1):
    for j, ej in enumerate(s[i:], i+1):
        if ei == ej:
            dp[i][j] = min(dp[i-1][j-1] + 1, j - i)
            ans = max(ans, dp[i][j])

print(ans)

Submission status: Accepted

Solution code:
#141_E
n = int(input())
s = input()

x = 0
for i in range(n):
    s_ = s[:i+1]
    if s_[i - x:] in s_[: i - x]:
        x += 1

print(x)

Submission status: Accepted

Solution code:
def main():
    import sys
    input=sys.stdin.buffer.readline
    n=int(input())
    b,M=37,998244353
    x,y=1,0
    f,h=[1],[0]
    f_add,h_add=f.append,h.append
    for c in input():
        x=x*b%M
        f_add(x)
        y=(y*b+c)%M
        h_add(y)
    ok,ng=0,n//2+1
    while ng-ok>1:
        mid=ok+ng>>1
        d={}
        for i in range(n-mid+1):
            k=(h[i+mid]-h[i]*f[mid])%M
            if k in d:
                if d[k]+mid<=i:
                    ok=mid
                    break
            else:
                d[k]=i
        else:
            ng=mid
    print(ok)
main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input=sys.stdin.buffer.readline
    n=int(input())
    b,M=37,998244353
    x,y=1,0
    f,h=[1],[0]
    f_add,h_add=f.append,h.append
    for i,c in enumerate(input()):
        x=x*b%M
        f_add(x)
        y=(y*b+c)%M
        h_add(y)
    ok,ng=0,n//2+1
    while ng-ok>1:
        mid=ok+ng>>1
        d={}
        for i in range(n-mid+1):
            k=(h[i+mid]-h[i]*f[mid])%M
            if k in d:
                if d[k]+mid<=i:
                    ok=mid
                    break
            else:
                d[k]=i
        else:
            ng=mid
    print(ok)
main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input=sys.stdin.buffer.readline
    n=int(input())
    b=37
    M=998244353
    x,y=1,0
    f=[x]*(n+2)
    h=[y]*(n+2)
    for i,c in enumerate(input()):
        f[i+1]=x=x*b%M
        h[i+1]=y=(y*b+c)%M
    ok,ng=0,n//2+1
    while ng-ok>1:
        mid=ok+ng>>1
        d={}
        for i in range(0,n-mid+1):
            k=(h[i+mid]-h[i]*f[mid])%M
            if k in d:
                if d[k]+mid<=i:
                    ok=mid
                    break
            else:
                d[k]=i
        else:
            ng=mid
    print(ok)
main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input=sys.stdin.buffer.readline
    n=int(input())
    b=129
    M=2**61-1
    x,y=1,0
    f=[x]*(n+2)
    h=[y]*(n+2)
    for i,c in enumerate(input()):
        f[i+1]=x=x*b%M
        h[i+1]=y=(y*b+c)%M
    ok,ng=0,n//2+1
    while ng-ok>1:
        mid=ok+ng>>1
        d={}
        for i in range(0,n-mid+1):
            k=(h[i+mid]-h[i]*f[mid])%M
            if k in d:
                if d[k]+mid<=i:
                    ok=mid
                    break
            else:
                d[k]=i
        else:
            ng=mid
    print(ok)
main()

Submission status: Accepted

Solution code:
class RollingHash():
    def __init__(self,s):
        self.n=n=len(s)
        self.b=b=129
        self.M=M=2**61-1
        x,y=1,0
        self.f=f=[x]*(n+1)
        self.h=h=[y]*(n+1)
        for i,c in enumerate(s.encode()):
            f[i+1]=x=x*b%M
            h[i+1]=y=(y*b+c)%M
    def get(self,l,r):
        return(self.h[r]-self.h[l]*self.f[r-l])%self.M
def main():
    n=int(input())
    s=RollingHash(input())
    ok,ng=0,n
    while ng-ok>1:
        mid=ok+ng>>1
        d={}
        for i in range(0,n-mid+1):
            k=s.get(i,i+mid)
            if k in d:
                if d[k]+mid<=i:
                    ok=mid
                    break
            else:
                d[k]=i
        else:
            ng=mid
    print(ok)
main()

Submission status: Accepted

Solution code:
class RollingHash():
    def __init__(self,s):
        self.n=n=len(s)
        self.b=b=129
        self.M=M=2**61-1
        x,y=1,0
        self.f=f=[x]*(n+1)
        self.h=h=[y]*(n+1)
        for i,c in enumerate(s.encode()):
            f[i+1]=x=x*b%M
            h[i+1]=y=(y*b+c)%M
    def get(self,l,r):
        return(self.h[r]-self.h[l]*self.f[r-l])%self.M
def check(x):
    d={}
    for i in range(0,n-x+1):
        k=s.get(i,i+x)
        if k in d:
            if d[k]+x<=i:
                return True
        else:
            d[k]=i
    return False
n=int(input())
s=RollingHash(input())
ok,ng=0,n
while ng-ok>1:
    mid=ok+ng>>1
    if check(mid):
        ok=mid
    else:
        ng=mid
print(ok)

Submission status: Accepted

Solution code:
from collections import deque
import copy

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

dq_s = deque([])
for x in s:
    dq_s.append(x)

dq_s_shift = copy.deepcopy(dq_s)

ans = 0

for i in range(n):
    dq_s_shift.appendleft('_')
    count = 0
    # print(s)
    # print(s_shift)

    for j in range(i+1,n):
        if dq_s[j] == dq_s_shift[j]:
            count += 1
        else:
            count = 0
        if count >= ans and count <= i+1:
            ans = count
    # print('-'*30)
    # print(ans)

print(ans)

Submission status: Accepted

Solution code:
def z_algo(s):
    """文字列sについて、各iについて「SとS[i:|S|]の最長共通接頭辞の長さ」
    を記録した配列をO(|S|)で構築する
    """
    res = [0] * len(s)
    res[0] = len(s)
    i = 1
    j = 0
    while i < len(s):
        while i + j < len(s) and s[j] == s[i + j]:
            j += 1
        res[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < len(s) and k + res[k] < j:
            res[i + k] = res[k]
            k += 1
        i += k
        j -= k
    return res


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

ans = 0
for i in range(n):
    t = z_algo(s[i:n])
    for i, num in enumerate(t):
        ans = max(ans, min(num, i))
print(ans)

Submission status: Accepted

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

n = int(input())
s = input().rstrip()

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

ans = 0

for i in range(n):
    s_ = s[i:]
    z_s = z_algo(s_)
    for j in range(len(z_s)):
        ans = max(ans, min(j, z_s[j]))

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
r=n//2
l=-1
while r-l>1:
  mid=(r+l)//2
  d=dict()
  ok=False
  for i in range(n-mid):
    ss=s[i:i+mid+1]
    if ss not in d:
      d[ss]=i
    else:
      if d[ss]+mid<i:
        ok=True
  if ok:
    l=mid
  else:
    r=mid
print(r)

Submission status: Accepted

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
ans = 0
for i in range(n-1):
	tmp = z_algo(s[i:])
	for j,zj in enumerate(tmp):
		if j+1 > zj:
			ans = max(ans,zj)

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
import collections
l=0
h=n//2+1
ans=0
while h>l+1:
    t=(h+l)//2
    d=collections.defaultdict(int)
    for i in range(n-t+1):
        c=s[i:i+t]
        if d[c]==0:
            d[c]=i+1
        else:
            if d[c]+t<=i+1:
                l=t
                break
    else:
        h=t
print(l)

Submission status: Accepted

Solution code:
BASE = 9973
MOD1 = 10 ** 9 + 7
MOD2 = 998244353


class RollingHash:
    # 文字列Sのローリングハッシュを構築
    # 計算量: O(N)
    def __init__(self, S, MOD):
        self.MOD = MOD
        # acc[i]はS[0:i]のハッシュ値となる
        self.acc = [0]
        a = 0
        # 累積和を計算するイメージ
        for i, c in enumerate(S):
            h = ord(c) - ord("a") + 1
            offset = pow(BASE, i, MOD)
            a = (a + (h * offset)) % MOD
            self.acc.append(a)

    # S[i:j]のハッシュ値を返す
    # 計算量: O(1)
    def hash(self, i, j):
        # 累積和を用いて部分区間の和を計算するイメージ
        # 注意: 基数によるオフセットをキャンセルする必要がある
        offset = pow(BASE, i, self.MOD)
        # 素数MODを法とする剰余類における除算は逆元を乗算することで計算できる
        # 素数MODを法とする剰余類におけるxの逆元はx^(MOD - 2)に等しい
        offset_inv = pow(offset, self.MOD - 2, self.MOD)
        return ((self.acc[j] - self.acc[i]) * offset_inv) % self.MOD


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

# Sのローリングハッシュを計算しておく
rolling1 = RollingHash(S, MOD1)
rolling2 = RollingHash(S, MOD2)

# 長さmのダジャレがSに含まれるならば、長さm-1のダジャレも含まれる
# つまり、長さmのダジャレがSに含まれるならば真となる述語をP(m)とすると、以下を満たす整数cが存在する:
#   - 0以上c以下の整数mについてP(m)は真
#   - cより大きい整数mについてP(m)は偽
# ※ Pは単調関数ということ
# このcを二分探索で発見すれば高速化できる！

# P(ok)は真
ok = 0
# P(ng)は偽
ng = N
while ng - ok > 1:
    # 区間[ok, ng)の中央値をmとする
    m = (ok + ng) // 2

    # 長さmのダジャレが存在するか判定する
    # 長さmのformerのハッシュ値のキャッシュ
    former_cache1 = set()
    former_cache2 = set()
    p = False
    # latterに着目してループを回す
    for i in range(m, N):
        # ダジャレ長を決め打ちしているのでjを直接計算できる
        j = i + m
        # S[i:j]がSをはみ出したらループ終了
        if j > N:
            break
        # formerのハッシュ値をキャッシュする
        former_cache1.add(rolling1.hash(i - m, i))
        former_cache2.add(rolling2.hash(i - m, i))
        # キャッシャに同一のハッシュ値が存在する場合（ハッシュ値が衝突した場合）、ダジャレになっていると判定できる
        # ハッシュ値の計算、キャッシュ存在判定は共にO(1)で処理できる！
        if (
            rolling1.hash(i, j) in former_cache1
            and rolling2.hash(i, j) in former_cache2
        ):
            p = True
    # 区間[ok, ng) を更新
    if p:
        ok = m
    else:
        ng = m
# whileループを抜けると区間[ok, ng)は[c, c + 1) になっている
ans = ok

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
l=0
r=n
while r-l>1:
  mid=(r+l)//2
  dic={}
  flag=False
  for i in range(n-mid+1):
    tmp=s[i:i+mid]
    if tmp not in dic:
      dic[tmp]=i+mid
    else:
      if dic[tmp]<=i:
        flag=True
        break
  if flag:
    l=mid
  else:
    r=mid
print(l)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
"""
def lcs(s, t):
    ls, lt = len(s), len(t)
    dp = [[0] * (lt+1) for _ in range(ls+1)]
    for i in range(ls):
        for j in range(lt):
            #prev = dp[i+1][j+1]
            if s[i] == t[j]:
                dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1)
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j])
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1])
    return dp[ls][lt]
"""
def z_algorithm(s):
    ls = len(s)
    Z = [0] * ls
    Z[0] = ls
    i, j = 1, 0
    while i < ls:
        while i + j < ls and s[j] == s[i+j]:
            j += 1
        Z[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < ls and k + Z[k] < j:
            Z[i + k] = Z[k]
            k += 1
        i += k
        j -= k
    return Z

ans = 0
for i in range(n):
    #print(s[i:])
    z = z_algorithm(s[i:])
    for j, zj in enumerate(z):
        if j+1 > zj:
            ans = max(ans, zj)
    #print(z)
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
import math
import collections
import itertools
from inspect import currentframe
INF = 10 ** 10
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def gcd(x, y) : return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y) : return (x * y) // gcd(x, y)
def I() : return int(input())
def MI() : return map(int, input().split())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def chkprint(*args) : names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}; print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

N = I()
S = input()

def Z_alg(s):
    n = len(s)
    z = [0]*n
    z[0] = n

    L = 0
    R = 0
    for i in range(1, n):
        if(i >= R):  # 過去の結果が全く使えない
            L = i
            R = i
            while(R < n and s[R-L] == s[R]):
                R += 1
            z[i] = R-L
        elif(z[i-L] < R-i):  # 過去の結果が全て使える
            z[i] = z[i-L]
        else:  # 過去の結果が一部使える
            L = i
            while(R < n and s[R-L] == s[R]):
                R += 1
            z[i] = R-L

    return z

ans = 0
for i in range(N):
    z = Z_alg(S[i:])
    
    for j, l in enumerate(z):
        ans = max(ans, min(j, l))

print(ans)

Submission status: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353
class RollingHash:
    # Verify: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B
    def __init__(self, seq, base=10 ** 9 + 7, mod=2 ** 89 - 1):
        """
        :param str|typing.Sequence[int] seq:
        :param int base:
        :param int mod:
        """
        if isinstance(seq, str):
            self._seq = seq = list(map(ord, seq))
        else:
            self._seq = seq
        self._base = base
        self._mod = mod

        hashes = [0] * (len(seq) + 1)
        power = [1] * (len(seq) + 1)
        for i, c in enumerate(seq):
            hashes[i + 1] = (hashes[i] * base + c) % mod
            power[i + 1] = power[i] * base % mod
        self._hashes = hashes
        self._power = power

    def get(self, L, r):
        """
        [L, r) のハッシュ値を取得します
        :param int L:
        :param int r:
        """
        if L >= r:
            return 0
        return (self._hashes[r] - self._hashes[L] * self._power[r - L]) % self._mod


N = int(sys.stdin.buffer.readline())
S = sys.stdin.buffer.readline().decode().rstrip()
rh = RollingHash(S)


def test(size):
    l = 0
    r = size
    hist = {}
    while r <= N:
        h = rh.get(l, r)
        if h in hist:
            pl, pr = hist[h]
            if pr <= l:
                return True
        else:
            hist[h] = l, r
        l += 1
        r += 1
    return False


ok = 0
ng = N
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if test(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353
class RollingHash:
    # Verify: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B
    def __init__(self, seq, base=10 ** 9 + 7, mod=2 ** 89 - 1):
        """
        :param str|typing.Sequence[int] seq:
        :param int base:
        :param int mod:
        """
        if isinstance(seq, str):
            self._seq = seq = list(map(ord, seq))
        else:
            self._seq = seq
        self._base = base
        self._mod = mod

        hashes = [0] * (len(seq) + 1)
        power = [1] * (len(seq) + 1)
        for i, c in enumerate(seq):
            hashes[i + 1] = (hashes[i] * base + c) % mod
            power[i + 1] = power[i] * base % mod
        self._hashes = hashes
        self._power = power


    # @debug
    def get(self, L, r):
        """
        [L, r) のハッシュ値を取得します
        :param int L:
        :param int r:
        """
        if L >= r:
            return 0
        return (self._hashes[r] - self._hashes[L] * self._power[r - L]) % self._mod


N = int(sys.stdin.buffer.readline())
S = sys.stdin.buffer.readline().decode().rstrip()
rh = RollingHash(S)


# @debug
def test(size):
    l = 0
    r = size
    hist = {}
    while r <= N:
        h = rh.get(l, r)
        if h in hist:
            pl, pr = hist[h]
            if pr <= l:
                return True
        else:
            hist[h] = l, r
        l += 1
        r += 1
    return False


ok = 0
ng = N
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if test(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Accepted

Solution code:
#Z-algorithm
n=int(input())
s=input()
def Zalgo(s):
    ans=0
    L=len(s)
    Z=[0]*L
    Z[0]=L
    i=1;j=0
    while i<L:
        while i+j < L and s[j]==s[i+j]:j+=1
        Z[i]=j
        if Z[i] > ans and Z[i]<=i:
            ans=Z[i]
        if j == 0:
            i+=1
            continue
        k=1
        while k<j and k+Z[k]<j:
            Z[i+k]=Z[k]
            k+=1
        i+=k
        j-=k
    return ans
ans=0
for i in range(n):
    p=Zalgo(s[i:])
    if p > ans:
        ans=p
print(ans)

Submission status: Accepted

Solution code:
def check(x, N, S):
    candidate = set()
    for i in range(N - 2*x + 1):
        candidate.add(S[i:i+x])
        if S[i+x:i+2*x] in candidate:
            return True
    return False

def main():
    n = int(input())
    s = input().rstrip()
    l = 0
    r = n
    while l < r:
        mid = (l+r+1) // 2
        if check(mid, n, s):
            l = mid
        else:
            r = mid-1
    print((l+r+1)//2)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import random
from collections import defaultdict
from itertools import accumulate
import sys
input = sys.stdin.readline
n = int(input())
s = input().rstrip()
mod = (1<<61)-1
base = 1000+random.randint(0,100)
power = [1]
for i in range(1,n):
  power.append((power[-1]*base)%mod)
hvalue = [0]
for i in range(n):
  hvalue.append((hvalue[-1]+(ord(s[i])*power[i]))%mod)
def rollinghash(l,r):
  return ((hvalue[r]-hvalue[l])*power[n-r])%mod
def pun(i):
  dc = defaultdict(int)
  if i>n//2:
    return False
  for j in range(n-i+1):
    x = rollinghash(j,i+j)
    if dc[x]:
      rg =dc[x]
      if rg<=j:
        return True
    else:
      dc[x] = i+j
  return False
l=0
r=n//2+1
while l+1<r:
  mi=(l+r)//2
  if pun(mi):
    l=mi
  else:
    r=mi
print(l)

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

class SuffixArray:

    class SparseTable:

        def __init__(self, A, func):
            self.N = len(A)
            self.func = func
            h = 0
            while 1<<h < self.N:
                h += 1
            self.dat = list2d(h, 1<<h, 0)
            self.height = [0] * (self.N+1)

            for i in range(2, self.N+1):
                self.height[i] = self.height[i>>1] + 1
            for i in range(self.N):
                self.dat[0][i] = A[i]
            for i in range(1, h):
                for j in range(self.N):
                    self.dat[i][j] = self.func(self.dat[i-1][j], self.dat[i-1][min(j+(1<<(i-1)), self.N-1)])
            
        def get(self, l, r):
            """ 区間[l,r)でのmin,maxを取得 """

            a = self.height[r-l]
            return self.func(self.dat[a][l], self.dat[a][r-(1<<a)])

    def __init__(self, S):
        self.k = 1
        self.S = S
        self.N = len(S)
        self.rank = [0] * (self.N+1)
        self.tmp = [0] * (self.N+1)
        self.sa = [0] * (self.N+1)
        self.build_sa()

    # def compare_sa(self, i, j):
    #     if self.rank[i] != self.rank[j]:
    #         return self.rank[i] < self.rank[j]
    #     else:
    #         ri = self.rank[i+self.k] if i + self.k <= self.N else -1
    #         rj = self.rank[j+self.k] if j + self.k <= self.N else -1
    #         return ri < rj

    def compare_sa(self, i, j):
        """ saの比較関数 """

        # 第1キー
        if self.rank[i] == self.rank[j]: res1 =  0
        elif self.rank[i] < self.rank[j]: res1 =  -1
        else: res1 = 1
        # 第2キー
        ri = self.rank[i+self.k] if i + self.k <= self.N else -1
        rj = self.rank[j+self.k] if j + self.k <= self.N else -1
        if ri == rj: res2 = 0
        elif ri < rj: res2 = -1
        else: res2 = 1
        # 比較
        return res1 or res2

    def build_sa(self):
        """ Suffix Arrayの構築 """
        # from functools import cmp_to_key

        # # 最初は1文字、ランクは文字コード
        # for i in range(self.N+1):
        #     self.sa[i] = i
        #     self.rank[i] = ord(self.S[i]) if i < self.N else -1

        # # k文字についてソートされているところから、　2k文字でソートする
        # k = 1
        # while k <= self.N:
        #     self.k = k
        #     self.sa = sorted(self.sa, key=cmp_to_key(self.compare_sa))
        #     k *= 2

        #     # いったんtmpに次のランクを計算し、それからrankに移す
        #     self.tmp[self.sa[0]] = 0
        #     for i in range(1, self.N+1):
        #         self.tmp[self.sa[i]] = self.tmp[self.sa[i-1]] + (1 if self.compare_sa(self.sa[i-1], self.sa[i]) else 0)
        #     for i in range(self.N+1):
        #         self.rank[i] = self.tmp[i]
        suffix_arr = [(self.S[i:], i) for i in range(self.N+1)]
        suffix_arr.sort()
        for i in range(self.N+1):
            self.sa[i] = suffix_arr[i][1]

    def build_lcp(self):
        """ LCP配列の構築 """

        self.lcp = [0] * (self.N+1)
        self.rsa = [0] * (self.N+1)
        for i in range(self.N+1):
            self.rsa[self.sa[i]] = i
        h = 0
        self.lcp[0] = 0
        for i in range(self.N):
            # 文字列内での位置iの接尾辞と、接尾辞配列内でその1つ前の接尾辞のLCPを求める
            j = self.sa[self.rsa[i]-1]

            # hを先頭の分1減らし、後ろが一致しているだけ増やす
            if h > 0:
                h -= 1
            while j+h < self.N and i+h < self.N:
                if self.S[j+h] != self.S[i+h]:
                    break
                h += 1
            self.lcp[self.rsa[i]-1] = h

        # 区間取得のためSparseTableを構築
        self.st = self.SparseTable(self.lcp, min)

    def getLCP(self, i, j):
        """ S[i:]とS[j:]の共通文字数を取得 """

        return self.st.get(min(self.rsa[i], self.rsa[j]), max(self.rsa[i], self.rsa[j]))

N = INT()
S = input()

sa = SuffixArray(S)
sa.build_lcp()

ans = 0
for i in range(N):
    for j in range(i+1, N):
        lcp = min(sa.getLCP(i, j), j - i)
        ans = max(ans, lcp)
print(ans)