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 = list(input())

def z_algorithm(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
    tmp = 0
    for index, a in enumerate(A):
        if a <= index:
            tmp = max(tmp, a)
    # print (A)
    return tmp

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

print (ans)

Submission status: Accepted

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


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


ans = 0
for i in range(n - 1):
    r = z_algo(s[i:])
    for j in range(1, len(r)):
        if r[j] <= j:
            ans = max(ans, r[j])
print(ans)

Submission status: Accepted

Solution code:
#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

p = 10 ** 9 + 7
p2 = 10 ** 9 + 9
q = 1007
q2 = 2009

def rollingHash(N, M, A, ans):
	mul1 = 1
	mul2 = 1
	for i in range(M):
		mul1 = (mul1 * q) % p
		mul2 = (mul2 * q2) % p2

	Droll1 = defaultdict(lambda:-1)
	Droll2 = defaultdict(lambda:-1)
	val1 = 0
	val2 = 0
	for i in range(M):
		val1 = val1 * q + A[i]
		val1 %= p
		val2 = val2 * q2 + A[i]
		val2 %= p2

	Droll1[val1] = 0
	Droll2[val2] = 0
	rolling_Hash1 = [None] * (N - M + 1)
	rolling_Hash1[0] = val1
	rolling_Hash2 = [None] * (N - M + 1)
	rolling_Hash2[0] = val2

	for i in range(N - M):
		val1 = (val1 * q - A[i] * mul1 + A[i + M]) % p
		val2 = (val2 * q2 - A[i] * mul2 + A[i + M]) % p2
		rolling_Hash1[i + 1] = val1
		rolling_Hash2[i + 1] = val2

		if Droll1[val1] == -1:
			Droll1[val1] = i + 1
		else:
			if rolling_Hash1[i + 1] == rolling_Hash1[Droll1[val1]] and rolling_Hash2[i + 1] == rolling_Hash2[Droll1[val1]] and i + 1 - Droll1[val1] >= M:
				return M

	return ans

#処理内容
def main():
	N = int(input())
	S = list(input())
	for i in range(N):
		S[i] = ord(S[i]) - 97

	ans = 0
	for i in range(1, int(N // 2) + 1):
		ans = rollingHash(N, i, S, ans)

	print(ans)



if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
N = int(input())
S = input()
ans = 0
for i in range(N):
    k = ans + 1
    for j in range(k, N-i):
        if S[i:i+j] in S[i+j:]:
            ans = max(ans, j)
        else:
            break
print(ans)

Submission status: Accepted

Solution code:
class RollingHash():
    def __init__(self, s):
        self.length = len(s)
        self.base = 1009
        self.mod = (1 << 127) - 1
        self.hash = [0] * (self.length + 1)
        self.pow = [1] * (self.length + 1)
 
        for i in range(self.length):
            self.hash[i+1] = (self.hash[i] + ord(s[i])) * self.base % self.mod
            self.pow[i+1] = self.pow[i] * self.base % self.mod
 
    def get(self, l, r):
        t = self.hash[r] - self.hash[l] * self.pow[r-l] % self.mod
        t = (t + self.mod) % self.mod
        return t

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

RH = RollingHash(S)

from collections import defaultdict

def check(length):
    if length==0:
        return True
    dd = defaultdict(int)
    flag = False
    for i in range(N-length+1):
        rh = RH.get(i,i+length)
        if dd[rh]==0:
            dd[rh] = i+1
        else:
            if dd[rh]+length<=i+1:
                flag=True
                break
    return flag

l = 0
r = N

while r-l>1:
    if check((l+r)//2):
        l = (l+r)//2
    else:
        r = (l+r)//2

print(l)

Submission status: Accepted

Solution code:
def z_algo(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
        A[i] = j
        if not j:
            i += 1
            continue
        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(input())
s = input()
ans = 0
for i in range(n):
  A = z_algo(s[i:])
  for j in range(1, n-i):
    m = min(j, A[j])
    ans = max(m, ans)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

class ModInt():
    def __init__(self, n):
        self.n = n

    def __add__(self, x):
        x = ModInt.xn(x)
        return ModInt((self.n+x) % mod)

    def __sub__(self, x):
        x = ModInt.xn(x)
        return ModInt((self.n-x) % mod)

    def __mul__(self, x):
        x = ModInt.xn(x)
        return ModInt((self.n*x) % mod)

    def __truediv__(self, x):
        x = ModInt.xn(x)
        return ModInt(self.n * pow(x, mod-2, mod) % mod)

    @classmethod
    def xn(cls, x):
        if isinstance(x, ModInt):
            return x.n
        return x

    def __str__(self):
        return str(self.n)

def M(n): return ModInt(n)

class RollingHash():
    def __init__(self, s):
        self.N = n = len(s)
        a = [ord(c) for c in s]
        self.A1 = a1 = [M(a[0])]
        self.A2 = a2 = [M(a[0])]
        for c in a[1:]:
            a1.append(a1[-1] * 997 + c)
            a2.append(a2[-1] * 991 + c)

    def get(self, l, r):
        if l == 0:
            return (self.A1[r].n, self.A2[r].n)
        t1 = (self.A1[r] - self.A1[l-1] * pow(997, r-l+1, mod)).n
        t2 = (self.A2[r] - self.A2[l-1] * pow(991, r-l+1, mod)).n
        return (t1, t2)

def bs(f, mi, ma):
    mm = -1
    while ma > mi:
        mm = (ma+mi) // 2
        if f(mm):
            mi = mm + 1
        else:
            ma = mm
    if f(mm):
        return mm + 1
    return mm

def main():
    n = I()
    s = S()
    rh = RollingHash(s)

    def f(i):
        s = set()
        for j in range(i,n-i+1):
            t = rh.get(j-i,j-1)
            s.add(t)
            k = rh.get(j,j+i-1)
            if k in s:
                return True
        return False

    r = bs(f,1, n)

    return r - 1


print(main())

Submission status: Accepted

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N=II()
S=input()

DP = [[0]*(N+1) for i in range(N+1)]
for j in range(1, N)[::-1]:
    for i in range(0, j)[::-1]:
        if S[i] == S[j]:
            DP[i][j] = DP[i+1][j+1] + 1
        else:
            DP[i][j] = 0

# print(DP)
res = 0
for i in range(N-1):
    for j in range(i+1,N):
        res = max(res, min(DP[i][j], j-i))
print(res)

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):
    res = z_algo(s[i:])
    for i, num in enumerate(res):
        ans = max(ans, min(num, i))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
def Z_algo(S):
    n = len(S)
    LCP = [0]*n
    i = 1
    j = 0
    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
    for i in range(1,n):
        if i <= LCP[i]:
            LCP[i] = i
    return LCP
ans = 0
for i in range(N):
    T = S[i:]
    R = Z_algo(T)
    R.pop(0)
    R.append(0)
    ans = max(max(R),ans)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N=int(input())
S=input().strip()
"""dp=[[0]*(N+1) for _ in range(N+1)]
for i in range(N-1,-1,-1):
    for j in range(N-1,i,-1):
        if S[i]==S[j]:
            dp[i][j]=max(dp[i][j],dp[i+1][j+1]+1)
#print(dp)
ans=0
for i in range(N):
    for j in range(N):
        ans=max(ans,min(dp[i][j],j-i))
print(ans)
"""

def Z_algo(S):
    n = len(S)
    LCP = [0]*n
    i = 1
    j = 0
    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

ans=0
for i in range(N):
    LCP=Z_algo(S[i:])
    #print(LCP)
    for j , l in enumerate(LCP):
        tmp=min(l,j)
        ans=max(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N=int(input())
S=input().strip()
dp=[[0]*(N+1) for _ in range(N+1)]
for i in range(N-1,-1,-1):
    for j in range(N-1,i,-1):
        if S[i]==S[j]:
            dp[i][j]=max(dp[i][j],dp[i+1][j+1]+1)
#print(dp)
ans=0
for i in range(N):
    for j in range(N):
        ans=max(ans,min(dp[i][j],j-i))
print(ans)

Submission status: Accepted

Solution code:
class RollingHash(object):
    """
    construct: O(N)
    query:
        hash: O(1)
        lcp: O(logN)
        search: O(N)
    """
    __base1=1007; __mod1=10**9
    __base2=1009; __mod2=10**7
 
    def __init__(self,s):
        """
        s: str
        """
        n=len(s)
        self.__s=s
        self.__n=n
        b1=self.__base1; m1=self.__mod1
        b2=self.__base2; m2=self.__mod2
        H1,H2=[0]*(n+1),[0]*(n+1)
        P1,P2=[1]*(n+1),[1]*(n+1)
        for i in range(n):
            H1[i+1]=(H1[i]*b1+ord(s[i]))%m1
            H2[i+1]=(H2[i]*b2+ord(s[i]))%m2
            P1[i+1]=P1[i]*b1%m1
            P2[i+1]=P2[i]*b2%m2
        self.__H1=H1; self.__H2=H2
        self.__P1=P1; self.__P2=P2
 
    @property
    def str(self):
        return self.__s
 
    @property
    def len(self):
        return self.__n
 
    def hash(self,l,r=None):
        """
        l,r: int (0<=l<=r<=n)
        return (hash1,hash2) of S[l:r]
        """
        m1=self.__mod1; m2=self.__mod2
        if r is None: r=self.__n
        assert 0<=l<=r<=self.__n
        return ((self.__H1[r]-self.__P1[r-l]*self.__H1[l]%m1)%m1,
                (self.__H2[r]-self.__P2[r-l]*self.__H2[l]%m2)%m2)
 
    @classmethod
    def lcp(cls,rh1,rh2,l1,l2,r1=None,r2=None):
        """
        rh1,rh2: RollingHash object
        l1,l2,r1,r2: int 0<=l1<=r1<=r1.len,0<=l2<=r2<=rh2.len
        return lcp length between rh1[l1:r1] and rh2[l2:r2]
        """
        if r1 is None: r1=rh1.__n
        if r2 is None: r2=rh2.__n
        assert 0<=l1<=r1<=rh1.__n and 0<=l2<=r2<=rh2.__n
        L=0
        R=min(r1-l1,r2-l2)
        if rh1.hash(l1,l1+R)==rh2.hash(l2,l2+R): return R
        while(R-L>1):
            H=(L+R)//2
            if rh1.hash(l1,l1+H)==rh2.hash(l2,l2+H): L=H
            else: R=H
        return L
 
    @classmethod
    def search(cls,pattern,text):
        """
        pattern,text: RollingHash object
        return list of index i's satisfying text[i:] starts with pattern
        """
        n=text.__n; m=pattern.__n
        res=[]
        for i in range(n-m+1):
            if text.hash(i,i+m)==pattern.hash(0,m):
                res.append(i)
        return res
    
#------------
from collections import defaultdict

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

rh = RollingHash(S)

#長さlenが上位園を満たすか二分探索
#条件を満たすためには，S[i:i+len]のhash値を計算．S[i:i+len]==S[j:j+len] and j-i>=lenならok
#ここで，i,jでループを回すのではなく，iで回してその時の{ハッシュ値:i}を辞書に持っておく．

#長さlが条件を満たすか？
def test(len):
    dd = defaultdict(int)
    for i in range(N-len+1):
        h=rh.hash(i,i+len)
        if dd[h]!=0:
            if i-dd[h]+1>=len:#+1の理由は下記のコメントを参照
                return True
        else:
            dd[h]=i+1#本当はiにしたいけど，i=0でやばい
    return False
        

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

print(ok)

Submission status: Accepted

Solution code:
def Z(s):
    n=len(s)
    lcp=[0]*n
    lcp[0]=n
    L,R=0,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
            lcp[i]=R-L
        elif(lcp[i-L]<R-i): # 過去の結果を再利用
            lcp[i]=lcp[i-L]
        else: # 過去の結果を一部再利用
            L=i
            while(R<n and s[R-L]==s[R]):
                R+=1
            lcp[i]=R-L
    return lcp

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

ans=0
#Zalgorithmでは先頭からしか見れないので，開始位置をずらしてN通り，j文字目を先頭にした時
for j in range(N):
    T=S[j:]
    lcp=Z(T)
    lcp[0]=0
    l=0
    for k in range(len(lcp)):
        l=max(l,min(lcp[k],k))
    ans=max(ans,l)
print(ans)

Submission status: Accepted

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

#dp[i][j]はi文字目からスタートする文字列と，j文字目からスタートする文字列の共通部分長
dp=[[0]*(N+1) for _ in range(N+1)]

ans=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]=max(dp[i][j],dp[i+1][j+1]+1)
            ans = max(ans,min(dp[i][j],j-i))
        else:
            dp[i+1][j+1]=0

print(ans)

Submission status: Accepted

Solution code:
import sys
#import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
S = rs()

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

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

print(left)

Submission status: Accepted

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

T = [[0 for _ in range(N)] for _ in range(N)]

for i in range(N):
  for j in range(i + 1, N):
    if S[i] == S[j]:
      T[i][j] += T[i - 1][j - 1] + 1

answer = 0
for i in range(N):
  for j in range(N):
    if T[i][j] and j - i >= T[i][j]:
      answer = max(answer, T[i][j])
print(answer)

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

n = int(input())
s = input()
def ceil(a, b):
   return a // b + (a % b > 0)
ans = 0
for i in range(n-1):
   for idx, j in enumerate(z_algo(s[i:])):
      ans = max(min(idx, j), ans)

print(ans)

Submission status: Accepted

Solution code:
class RollingHash():
    def __init__(self, string):
        self.n = len(string)
        self.BASE = 1234
        self.MOD = (1 << 61) - 1
        self.hash = [0] * (self.n + 1)
        self.pow = [1] * (self.n + 1)
        
        for i, char in enumerate(string):
            self.hash[i+1] = (self.hash[i] + ord(char)) * self.BASE % self.MOD
            self.pow[i+1] = (self.pow[i] * self.BASE) % self.MOD
            
    def get_hash(self, l, r):
        res = (self.hash[r] - self.hash[l] * self.pow[r-l]) % self.MOD
        return res
      
    def get_lcp(self, l1, r1, l2, r2):
        ng = min(r1 - l1, r2 - l2) + 1
        ok = 0
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            if self.get_hash(l1, l1 + mid) == self.get_hash(l2, l2 + mid):
                ok = mid
            else:
                ng = mid
        return ok
        
n = int(input())
s = input()

rh = RollingHash(s)

s = 0
def solve(mid):
    length = mid
    set_ = set()
    for l in range(n):
        # [l, l + length), [l + length, l + 2*length)
        if l + 2*length > n:
            break
        set_.add(rh.get_hash(l, l + length))
        tmp = rh.get_hash(l + length, l + 2*length)
        if tmp in set_:
            ans = length
            return True
    return False
  
ok = 0
ng = n//2 + 1
while abs(ng - ok) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Accepted

Solution code:
class RollingHash():
    def __init__(self, string):
        self.n = len(string)
        self.BASE = 1234
        self.MOD = (1 << 61) - 1
        self.hash = [0] * (self.n + 1)
        self.pow = [1] * (self.n + 1)
        
        for i, char in enumerate(string):
            self.hash[i+1] = (self.hash[i] + ord(char)) * self.BASE % self.MOD
            self.pow[i+1] = (self.pow[i] * self.BASE) % self.MOD
            
    def get_hash(self, l, r):
        res = (self.hash[r] - self.hash[l] * self.pow[r-l]) % self.MOD
        return res

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

rh = RollingHash(s)

ans = 0
def solve(mid):
    length = mid
    set_ = set()
    for l in range(n):
        # [l, l + length), [l + length, l + 2*length)
        if l + 2*length > n:
            break
        set_.add(rh.get_hash(l, l + length))
        tmp = rh.get_hash(l + length, l + 2*length)
        if tmp in set_:
            ans = length
            return True
    return False
  
ok = 0
ng = n//2 + 1
while abs(ng - ok) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Accepted

Solution code:
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    s = str(readline().rstrip().decode('utf-8'))
    mt = 0
    for i in range(n):
        zs = s[i:]
        zln = len(zs)
        zl = [0] * zln
        zi = 1
        zj = 0
        while zi < zln:
            while zi + zj < zln and zs[zj] == zs[zi+zj]:
                zj += 1
            zl[zi] = zj
            if zj == 0:
                zi += 1
                continue
            zk = 1
            while zi + zk < zln and zk + zl[zk] < zj:
                zl[zi+zk] = zl[zk]
                zk += 1
            zi += zk
            zj -= zk
        for j in range(len(zl)):
            if zl[j] <= j:
                mt = max(mt, zl[j])
    print(mt)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

BASE = 10**9 + 7
MOD = 2**61 - 1

def genRollingHash_AllRight(Ss, lenInit, BASE, MOD):
    As = [ord(S) for S in Ss]
    hashS = 0
    for A in As[:lenInit]:
        hashS = (hashS*BASE + A) % MOD
    yield hashS

    powB_L = pow(BASE, lenInit, MOD)
    for Aadd, Asub in zip(As[lenInit:], As[:len(As)-lenInit]):
        hashS = (hashS*BASE + Aadd - Asub*powB_L) % MOD
        yield hashS

def isOK(k):
    hashSs = list(genRollingHash_AllRight(Ss, k, BASE, MOD))
    setHashS = set()
    for i in range(k, N-k+1):
        setHashS.add(hashSs[i-k])
        if hashSs[i] in setHashS:
            return True
    return False

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

print(ok)

Submission status: Accepted

Solution code:
def main():
    class rolling_hash():
        def __init__(self, sequence, char_list=None):
            self.sequence = sequence  # 文字列
            self.seq_size = len(self.sequence)  # 文字列の長さ
            self.mod = 2**61-1  # mod
            if char_list is None:  # 使われている文字のリスト
                self.char_list = "abcdefghijklmnopqrstuvwxyz"
            else:
                self.char_list = char_list
            self.base = len(self.char_list)+1  # 文字の種類数
            self.char_dict = {j: i+1 for i,
                              j in enumerate(self.char_list)}  # 文字と数値の対応表
            self.Hash_0start = [0]*(self.seq_size+1)  # 先頭からi-1文字目までのハッシュ値
            for i in range(self.seq_size):
                self.Hash_0start[i+1] = self.Hash_0start[i] + \
                    self.char_dict[self.sequence[i]] * \
                    pow(self.base, i, self.mod)

        def calc_hash(self, l, r):  # l文字目からr-1文字目までのハッシュ値
            return ((self.Hash_0start[r] - self.Hash_0start[l])
                    * pow(self.base, l*(self.mod-2), self.mod)) % self.mod

    n = int(input())
    s = input()
    h_s = rolling_hash(s)

    def value(num):
        h_dict = {}
        for i in range(len(s)-num+1):
            j = h_s.calc_hash(i, i+num)
            if j not in h_dict:
                h_dict[j] = i
            else:
                if i-h_dict[j] >= num:
                    return True
        return False

    def b_search(a, b, value):
        while a+1 < b:
            med = (a+b)//2
            if value(med):
                a = med
            else:
                b = med-1
        if a == b:
            return a
        elif a+1 == b:
            if value(b):
                return b
            else:
                return a

    print(b_search(0, len(s), value))


main()

Submission status: Accepted

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

def isOK(k):
    strAs = ['' for _ in range(N)]
    strBs = ['' for _ in range(N)]
    for L in range(N-k+1):
        R = L+k-1
        ss = Ss[L:R+1]
        strAs[R] = ss
        strBs[L] = ss

    strCands = set()
    for iEn in range(N-1):
        if strAs[iEn] != '':
            strCands.add(strAs[iEn])
        if strBs[iEn+1] != '' and strBs[iEn+1] in strCands:
            return True

    return False


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

print(ok)

Submission status: Accepted

Solution code:
def z_algo(S):
    N = len(S)

    A = [0] * N
    A[0] = N
    i = 1
    j = 0

    while i < N:
        while i + j < N and S[j] == S[i + j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while N - i > k < j - A[k]:
            A[i + k] = A[k]
            k += 1
        i += k
        j -= k
    return A


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

ans = 0
for i in range(N):
    A = z_algo(S[i:])
    for idx, ls in enumerate(A):
        if idx - ls >= 0:
            ans = max(ans, ls)

print(ans)

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(i,n):
            l = min(j-i,z[j-i])
            if ans < l:
                ans = l
    print(ans)
    return

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

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
        j = 0
        for i in range(1,n):
            while i+j < n and s[j] == s[i+j]:
                j += 1
            z[i] = j
            if j == 0:
                i += 1
                continue
            k = 1
            while i+k < n and k+z[k] < j:
                z[i+k] = z[k]
                k += 1
            i += k
            j -= k
        return z
    n = I()
    s = input()
    ans = 0
    for i in range(n):
        z = Z_algorithm(s[i:])
        for j in range(i,n):
            l = min(j-i,z[j-i])
            if ans < l:
                ans = l
    print(ans)
    return

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

Submission status: Accepted

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

#Z algorithm

def Z_algorithm(s):
    n = len(s)
    Z = [0]*n
    Z[0] = n
    i,j = 1,0
    while i < n:
        while i+j < n and s[j] == s[i+j]:
            j += 1
        Z[i] = j
        if j == 0:
            i += 1
            continue
        k = 1

        #再利用部分
        while i+k < n and k+Z[k] < j:
            Z[i+k] = Z[k]
            k += 1
        i += k
        j -= k
    return Z

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

ans = 0
for i in range(n):
    z = Z_algorithm(s[i:])
    for j,k in enumerate(z):
        if j >= k:
            ans = max(ans,k)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    def zalgo(S):
        A=[0]*len(S)
        A[0]=len(S)
        i,j=1,0
        while i<len(S):
            while i+j<len(S) and S[j]==S[i+j]:
                j+=1
            A[i]=j 
            if j==0:
                i+=1
                continue
            k=1
            while i+k<len(S) and k+A[k]<j:
                A[i+k]=A[k]
                k+=1
            i+=k
            j-=k
        return A
    N=int(input())
    S=input()
    ans=0
    for i in range(N-1):
        A=zalgo(S[i:])
        for j,x in enumerate(A):
            if x>j:
                ans=max(ans,j)
            else:
                ans=max(ans,x)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()

class RollingHash(object):
    __base1=1007; __mod1=10**9+9
    __base2=1009; __mod2=10**9+7

    def __init__(self,s):
        self.__s=s; self.__n=len(s)
        b1=self.__base1; m1=self.__mod1
        b2=self.__base2; m2=self.__mod2
        H1,H2=[0]*(self.__n+1),[0]*(self.__n+1)
        P1,P2=[1]*(self.__n+1),[1]*(self.__n+1)
        for i in range(self.__n):
            H1[i+1]=(H1[i]*b1+ord(s[i]))%m1
            H2[i+1]=(H2[i]*b2+ord(s[i]))%m2
            P1[i+1]=P1[i]*b1%m1
            P2[i+1]=P2[i]*b2%m2
        self.__H1=H1; self.__H2=H2
        self.__P1=P1; self.__P2=P2

    def __getitem__(self,x):
        if(isinstance(x,int)): x=slice(x,x+1)
        assert(isinstance(x,slice) and ((x.step is None) or (x.step==1)))
        l=x.start; r=x.stop;
        assert(l<=r)
        return ((self.__H1[r]-self.__P1[r-l]*self.__H1[l]%self.__mod1)%self.__mod1,
                (self.__H2[r]-self.__P2[r-l]*self.__H2[l]%self.__mod2)%self.__mod2)

def bisection(l,r,f,left=True,discrete=True):
    eps=1 if(discrete) else 10**-8
    if((not left)^f(r)): return r if(left) else r+1
    elif(left^f(l)): return l-1 if(left) else l
    while(r-l>eps):
        h=(l+r)//2 if(discrete) else (l+r)/2
        if((not left)^f(h)): l=h
        else: r=h
    return (l+r)/2 if(not discrete) else l if(left) else r

from collections import defaultdict
def resolve():
    n=int(input())
    rh=RollingHash(input())

    def check(k):
        D=defaultdict(lambda:-1)
        for i in range(n-k+1):
            h=rh[i:i+k]
            if(D[h]!=-1):
                if(i-D[h]>=k):
                    return True
            else:
                D[h]=i
        return False

    print(bisection(0,n,check))
resolve()