Problem:


Score : 500 points

Problem Statement

Given is a string S of length N.

Find the maximum length of a non-empty string that occurs twice or more in S as contiguous substrings without overlapping.

More formally, find the maximum positive integer len such that there exist integers l_1 and l_2 ( 1 \leq l_1, l_2 \leq N - len + 1 ) that satisfy the following:

l_1 + len \leq l_2

S[l_1+i] = S[l_2+i] (i = 0, 1, ..., len - 1)

If there is no such integer len, print 0.

Constraints

2 \leq N \leq 5 \times 10^3

|S| = N

S consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the maximum length of a non-empty string that occurs twice or more in S as contiguous substrings without overlapping. If there is no such non-empty string, print 0 instead.

Sample Input 1

5
ababa

Sample Output 1

2

The strings satisfying the conditions are: a, b, ab, and ba. The maximum length among them is 2, which is the answer.
Note that aba occurs twice in S as contiguous substrings, but there is no pair of integers l_1 and l_2 mentioned in the statement such that l_1 + len \leq l_2.

Sample Input 2

2
xy

Sample Output 2

0

No non-empty string satisfies the conditions.

Sample Input 3

13
strangeorange

Sample Output 3

5



Sample input:
5
ababa


Sample output:
2

Submission status: Accepted

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

ans = 0
for i in range(N):
  j_start = ans + 1
  for j in range(j_start, N-i):
    base = S[i:i+j]
    if base in S[i+j:]:
      ans = max(ans, j)
    else:
      break


print(ans)

Submission status: Accepted

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

ans = 0
for i in range(N):
  j_start = ans + 1
  j_end = (N - i) // 2 + 1
  for j in range(j_start, j_end):
    base = S[i:i+j]
    if base in S[i+j:]:
      ans = max(ans, j)
    else:
      break


print(ans)

Submission status: Accepted

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

def z_algo(S):
    N = len(S)
    Z = [0]*N
    i = 1
    j = 0
    Z[0] = N
    while i < N:
        while i+j < N and S[j] == S[i+j]:
            j += 1
        if j == 0:
            i += 1
            continue
        Z[i] = j
        k = 1
        while i+k < N and k < j-Z[k]:
            Z[i+k] = Z[k]
            k += 1
        i += k
        j -= k
    return Z

ans = 0
l = 0
while l < N:
    temp = S[l:]
    z = z_algo(temp)
    for i in range(1, len(temp)):
        ans = max(ans, min(i, z[i]))
    l += 1
    
print(ans)

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()

ans = 0
for i in range(N):
  SS = S[i:]
  Z = z_algo(SS)
  #print(Z)
  for j in range(1,len(SS)):
    if Z[j] > j:
      l = j
    else:
      l = Z[j]
    ans = max(l,ans)
print(ans)

Submission status: Accepted

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

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

    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

ans = 0
for dl in list(range(1, N))[::-1]:
    if dl < ans: break
    cnt = 0
    ans_tmp = 0
    for l1 in range(N - dl):
        l2 = l1 + dl
        if S[l1] == S[l2]:
            # print("##", l1, l2)
            cnt += 1
        else:
            ans_tmp = max(ans_tmp, cnt)
            cnt = 0
    else:
        ans_tmp = max(ans_tmp, cnt)
    #
    # print("#", dl, ans_tmp)
    ans = max(ans, min(dl, ans_tmp))

print(ans)

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**-12
    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())
    S=input()
    rh=RollingHash(S)

    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()

Submission status: Accepted

Solution code:
# Z-Algorithm
# 計算量はO(N) ：各要素高々2回しか走査しない
def z_algo(S):
    N = len(S)
    A = [0] * N
    i = 1
    j = 0
    while (i < N):
        while (i + j < N and S[j] == S[i + j]):
            j += 1 # 一致している限りj(共通接頭辞の右端)を右に伸ばす
        A[i] = j
        # 一致が無ければ次へ
        if j == 0:
            i += 1
            continue
        
        # 共通接頭辞があった場合、それを利用する
        k = 1
        while (i + k < N and k + A[k] < j):
            # i + k < N の意味：i からkだけ離れた場所がS内に収まる
            # k+A[k] < j の意味：SとA[i]との最大共通接頭辞の長さに収まる
            A[i + k] = A[k]
            k += 1
        i += k # 後ろがはみ出していた共通接頭辞の開始位置に移動
        j -= k # はみ出しはじめに移動(S[j:]~とS[i+j:]がさっきまでの共通接頭辞からはみ出している)

    return A

def main():
    N = int(input())
    S = input()
    res = 0
    # 各iに対してS[i:]を考え、それについてZ_algoを適用する。
    # 各suffixに対して完全一致を除いた最長共通接頭辞の長さを求めれば良い。
    for i in range(N):
        lcp = z_algo(S[i:])
        for j in range(len(lcp)):
            l = min(j, lcp[j])
            res = max(res, l)
    print(res)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

# len = x となるか
def len_is_x(x):
    string = defaultdict(int)
    for i in range(x,N-x+1):
        string[S[i:i+x]] += 1
    for i in range(N-x+1):
        if i - x >= 0:
            string[S[i-x:i]] += 1
        if string[S[i:i+x]] >= 1:
            return True
        if i + x*2 <= N:
            string[S[i+x:i+x*2]] = max(string[S[i+x:i+x*2]]-1, 0) 
    return False

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

# lenのokとng
ng = N // 2 + 1
ok = 0

while (ng - ok) != 1:
    mid = (ok + ng) // 2
    if len_is_x(mid):
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Accepted

Solution code:
def main():

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

    i,j=0,1
    ans=0
    while j<n:
        if s[i:j] in s[j:]:
            if j-i>ans: ans=j-i
            j+=1
        else:
            i+=1
            j+=1

    print(ans)

            

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
tdlist = lambda i, j, value=0: [[value] * j for _ in range(i)]

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

dp = tdlist(n+1, n+1)
for i in range(1, n+1):
    for j in range(1, n+1):
        if s[i-1] == s[j-1]: dp[i][j] = dp[i-1][j-1] + 1

ans = 0
for i in range(n+1):
    for j in range(n+1):
        ans = max(ans, min(abs(i-j), dp[i][j]))

print(ans)

Submission status: Accepted

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

res = 0
for k in range(1, N):
    cnt = 0
    for i in range(N - k):
        if i + k < N and S[i + k] == S[i]:
            cnt += 1
        else:
            cnt = 0
        cnt = min(k, cnt)
        res = max(cnt, res)

print(res)

Submission status: Accepted

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

Submission status: Accepted

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

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**-12
    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

def resolve():
    n=int(input())
    S=input()
    rh=RollingHash(S)

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

    for k in range(n):
        if(not check(k)):
            print(max(0,k-1))
            return
resolve()

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**-12
    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

def resolve():
    n=int(input())
    S=input()
    rh=RollingHash(S)

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

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

Submission status: Accepted

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

Submission status: Accepted

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

ans = 0
for i in range(1, n):
    t = 0
    for j in range(n - i):
        t = t + 1 if s[j] == s[j + i] else 0
        ans = max(ans, min(i, t))

print(ans)

Submission status: Accepted

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

def check(length):
    d = set()
    for i in range(n - 2 * length + 1):
        d.add(s[i:i + length])
        if s[i + length:i + 2 * length] in d:
            return True
    return False
 
 
lo = 0
hi = n // 2 + 1
while lo + 1 < hi:
    mid = (lo + hi) // 2
    if check(mid):
        lo = mid
    else:
        hi = mid
if check(hi):
	print(hi)
else:
  	print(lo)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
ans = 0
for l in range(n):
    ss = s[l:]
    length = n - l
    i, j = 1, 0
    a = [0 for _ in range(length)]
    while i < length:
        while i + j < length and ss[j] == ss[i + j]:
            j += 1
        a[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < length and k + a[k] < j:
            a[i + k] = a[k]
            k += 1
        i += k
        j -= k
    for ll, al in enumerate(a):
        if al <= ll:
            ans = max(ans, al)
print(ans)

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(0, 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())
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:
# 2019-11-18 17:34:23(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# import re
# import heapq
# import array
# from scipy.misc import comb # (default: exact=False)
# import numpy as np 


def main():
    n, s = sys.stdin.read().split()
    n = int(n)

    res = 0
    l, r = 0, 1
    while r <= l + (n - l) // 2:
        t = s[l:r]
        if t in s[r:]:
            res = max(res, r - l)
            r += 1
        else:
            l += 1
            if l == r:
                r += 1
    print(res)

if __name__ == "__main__":
    main()

# しゃくとり法的なやつ

Submission status: Accepted

Solution code:
# 2019-11-18 17:34:23(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# import re
# import heapq
# import array
# from scipy.misc import comb # (default: exact=False)
# import numpy as np 


def main():
    n, s = sys.stdin.read().split()
    n = int(n)

    ans = 0
    i, j = 0, 1
    while j <= i + (n - i) // 2:
        if j <= i:
            j += 1
            continue
        t = s[i:j]
        if t in s[j:]:
            ans = max(ans, j - i)
            j += 1
        else:
            i += 1
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 2019-11-18 17:34:23(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# import re
# import heapq
# import array
# from scipy.misc import comb # (default: exact=False)
# import numpy as np 


def main():
    n, s = sys.stdin.read().split()
    n = int(n)

    ans = 0
    i, j = 0, 1
    while j <= i + (n - i) // 2:
        t = s[i:j]
        if t in s[j:]:
            ans = max(ans, j - i)
            j += 1
        else:
            i += 1
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 2019-11-18 17:34:23(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# import re
# import heapq
# import array
# from scipy.misc import comb # (default: exact=False)
# import numpy as np 


def main():
    n, s = sys.stdin.read().split()
    n = int(n)

    ans = 0
    i, j = 0, 1
    while j < n:
        t = s[i:j]
        if t in s[j:]:
            ans = max(ans, j - i)
            j += 1
        else:
            i += 1
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

m,j = 0,0
for i in range(n):
  if s[j:i+1] in s[i+1:]:
    m=i-j+1
  else:
    j+= 1

print(m)

Submission status: Accepted

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

def z_advanced(s):
    # Taken from https://ivanyu.me/blog/2013/10/15/z-algorithm/
    """An advanced computation of Z-values of a string."""
 
    Z = [0] * len(s)
    Z[0] = len(s)
 
    rt = 0
    lt = 0
 
    for k in range(1, len(s)):
        if k > rt:
            # If k is outside the current Z-box, do naive computation.
            n = 0
            while n + k < len(s) and s[n] == s[n+k]:
                n += 1
            Z[k] = n
            if n > 0:
                lt = k
                rt = k+n-1
        else:
            # If k is inside the current Z-box, consider two cases.
 
            p = k - lt  # Pair index.
            right_part_len = rt - k + 1
 
            if Z[p] < right_part_len:
                Z[k] = Z[p]
            else:
                i = rt + 1
                while i < len(s) and s[i] == s[i - k]:
                    i += 1
                Z[k] = i - k
 
                lt = k
                rt = i - 1
    return Z

best = 0
for i in range(N):
    lst = z_advanced(S[i:])
    for j, longest in enumerate(lst):
        best = max(best, min(j, longest))
print(best)

Submission status: Accepted

Solution code:
n = int(input())
s = input().rstrip()
 
 
def check(length):
    d = set()
    for i in range(n - 2 * length + 1):
        d.add(s[i:i + length])
        if s[i + length:i + 2 * length] in d:
            return True
    return False
 
 
lo = 0
hi = n // 2 + 1
while lo + 1 < hi:
    mid = (lo + hi) // 2
    if check(mid):
        lo = mid
    else:
        hi = mid
print(lo)

Submission status: Accepted

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

def main():
    N = int(input())
    S = input()
    # mod = 10**9+7
    # base = 1234
    # power = [1]*(N+1)
    # for i in range(1, N+1):
    #     power[i] = power[i-1]*base%mod
    def check(m):
        dic = {}
        for i in range(N-m+1):
            s = S[i:i+m]
            if s in dic.keys():
                if dic[s]+m<=i:
                    return True
            else:
                dic[s] = i
        return False
    ok = 0
    ng = N+1
    while ng-ok>1:
        mid = (ok+ng)//2

        if check(mid):
            ok = mid
        else:
            ng = mid
    print(ok)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
S = input()
mod = 10**9+7
base = 1234
power = [1]*(N+1)
for i in range(1, N+1):
    power[i] = power[i-1]*base%mod
def check(m):
    dic = {}
    for i in range(N-m+1):
        s = S[i:i+m]
        if s in dic.keys():
            if dic[s]+m<=i:
                return True
        else:
            dic[s] = i
    return False
ok = 0
ng = N+1
while ng-ok>1:
    mid = (ok+ng)//2

    if check(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Accepted

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

def solve(N: int, S: str):

    a = ""
    ans = 0
    for i in range(N):
        a += S[i]
        while(len(a) > 0):
            if a in S[i+1:]:    
                ans = max(ans,len(a))
                break
            else:               
                a = a[1:]
    print(ans)
    return


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:
import sys
input = sys.stdin.readline


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

    dp = [0] * N
    for i, s in enumerate(S):
        if i == 0:
            continue
        before_ans = dp[i-1]
        now_S = S[:i+1]
        tmp_ans = now_S[-(before_ans+1):i+1]
        # print(i, before_ans, tmp_ans)
        if tmp_ans in now_S[:-(before_ans+1)]:
            dp[i] = before_ans + 1
        else:
            dp[i] = before_ans
    print(dp[-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
S = input()
 
res = 0;
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);
    res = max(res, min(dp[i][j], j-i));
print(res)

Submission status: Accepted

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

def z_algo(n,s):
    x=[0]*n
    j=0
    for i in range(1,n):
        if i+x[i-j]<j+x[j]:
            x[i]=x[i-j]
        else:
            k=max(0,j+x[j]-i)
            while i+k<n and s[k]==s[i+k]:
                k+=1
            x[i]=k
            j=i
    ans=0
    for i in range(n):
        if x[i]>i:
            continue
        else:
            ans=max(ans,x[i])
    return ans

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

print(ans if ans<=n//2 else n//2)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
# 平衡二部探索
def bisect(l, r, f, discrete=True, left=True):
    """
        l,r: l<r int if discrete else float
        f: function defined on [l,...,r] to {False,True}
        if discrete: f defined on Z; else: R
        if left: f satisfies that there uniquely exists d such that iff i<=d then f(i)
        else: iff i>=d then f(i) is True
        return d such as those above
    """
    assert r > l
    if discrete:
        assert isinstance(l, int) and isinstance(r, int)
    eps = 1 if discrete else 10 ** -12
    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 h if not discrete else l if left else r


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):
        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
        hash1 = (self.__H1[r] - self.__P1[r - l] * self.__H1[l] % m1) % m1
        hash2 = (self.__H2[r] - self.__P2[r - l] * self.__H2[l] % m2) % m2
        return hash1, hash2

    @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

if __name__ == '__main__':
    # d=0ではtrue,d=nではfalseなので、そこでbisectする
    n = int(input())
    S = input()
    rh = RollingHash(S)
    def judge(d):
        J = {rh.hash(i, i+d): -1 for i in range(n-d+1)}
        for i in range(n-d+1):
            h = rh.hash(i, i+d)
            if J[h] != -1:
                if i-J[h] >= d: return True
            else:
                J[h] = i
        return False
    print(bisect(0, n, judge))

Submission status: Accepted

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

ans = 0
right = 1

for left in range(n):
    while s[left:right] in s[right:]:
        ans = max(ans,right-left)
        right += 1
        
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
# O(N**2)
class SuffixArray(object):
    """
    construct:
        suffix array: O(N(logN)^2)
        lcp array: O(N)
        sparse table: O(NlogN)
    query:
        lcp: O(1)
    """

    def __init__(self, s):
        """
        s: str
        """
        self.__s = s
        self.__n = len(s)
        self.__suffix_array()
        self.__lcp_array()
        self.__sparse_table()

    # suffix array
    def __suffix_array(self):
        s = self.__s;
        n = self.__n
        # initialize
        sa = list(range(n))
        rank = [ord(s[i]) for i in range(n)]
        tmp = [0] * n
        k = 1
        cmp_key = lambda i: (rank[i], rank[i + k] if i + k < n else -1)
        # iterate
        while (k <= n):
            sa.sort(key=cmp_key)
            tmp[sa[0]] = 0
            for i in range(1, n):
                tmp[sa[i]] = tmp[sa[i - 1]] + (cmp_key(sa[i - 1]) < cmp_key(sa[i]))
            rank = tmp[:]
            k <<= 1
        self.__sa = sa
        self.__rank = rank

    # LCP array
    def __lcp_array(self):
        s = self.__s;
        n = self.__n
        sa = self.__sa;
        rank = self.__rank
        lcp = [0] * n
        h = 0
        for i in range(n):
            j = sa[rank[i] - 1]
            if h > 0: h -= 1
            if rank[i] == 0: continue
            while j + h < n and i + h < n and s[j + h] == s[i + h]: h += 1
            lcp[rank[i]] = h
        self.__lcp = lcp

    # sparse table
    def __sparse_table(self):
        n = self.__n
        logn = max(0, (n - 1).bit_length())
        table = [[0] * n for _ in range(logn)]
        table[0] = self.__lcp[:]
        # construct
        from itertools import product
        for i, k in product(range(1, logn), range(n)):
            if k + (1 << (i - 1)) >= n:
                table[i][k] = table[i - 1][k]
            else:
                table[i][k] = min(table[i - 1][k], table[i - 1][k + (1 << (i - 1))])
        self.__table = table

    def lcp(self, a, b):
        """
        a,b: int 0<=a,b<n
        return LCP length between s[a:] and s[b:]
        """
        if a == b: return self.__n - a
        l, r = self.__rank[a], self.__rank[b]
        l, r = min(l, r) + 1, max(l, r) + 1
        i = max(0, (r - l - 1).bit_length() - 1)
        table = self.__table
        return min(table[i][l], table[i][r - (1 << i)])
def main():
  N = int(input())
  S = input()
  sa = SuffixArray(S)
  ans = 0
  for i in range(N):
    for j in range(i+1, N):
      ans = max(min(j-i, sa.lcp(i,j)), ans)
  print(ans)
  
if __name__ == '__main__':
  main()