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:
import sys
# input関係の定義
sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def fi(): return float(input())
def mfi(): return map(float, input().rstrip().split())
def lmfi(): return list(map(float, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()
# template

# BEGIN CUT HERE
class RollingHash():
    """ロリハ。容易に衝突するので注意。"""
    BASE1 = 1007
    BASE2 = 2009
    MOD1 = 1000000007
    MOD2 = 1000000009

    def __init__(self, s, opt=2):
        self.n = len(s)
        self.opt = opt
        self.hash1 = [0] * (self.n + 1)
        self.power1 = [1] * (self.n + 1)
        if opt == 2:  # rollinghash by 2 mod
            self.hash2 = [0] * (self.n + 1)
            self.power2 = [1] * (self.n + 1)

        for i, e in enumerate(s):
            self.hash1[i + 1] = (self.hash1[i] * self.__class__.BASE1 + ord(e)) % self.__class__.MOD1
            self.power1[i + 1] = (self.power1[i] * self.__class__.BASE1) % self.__class__.MOD1
        if opt == 2:  # rollinghash by 2 mod
            for i, e in enumerate(s):
                self.hash2[i + 1] = (self.hash2[i] * self.__class__.BASE2 + ord(e)) % self.__class__.MOD2
                self.power2[i + 1] = (self.power2[i] * self.__class__.BASE2) % self.__class__.MOD2

    def get(self, l: int, r: int):
        res1 = self.hash1[r] - self.hash1[l] * self.power1[r - l] % self.__class__.MOD1
        if(res1 < 0):
            res1 += self.__class__.MOD1
        if self.opt == 2:
            res2 = self.hash2[r] - self.hash2[l] * self.power2[r - l] % self.__class__.MOD2
            if(res2 < 0):
                res2 += self.__class__.MOD2
        return (res1, res2) if self.opt == 2 else res1
# END CUT HERE

def ABC131E():
    N = ii()
    S = li()
    rh = RollingHash(S, opt=1)
    def check(n: int):
        d = dict()
        for i in range(N - n + 1):
            p = rh.get(i, i + n)
            if p in d:
                if(i - d[p] >= n):
                    return True
            else:
                d[p] = i
        return False
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if check(mid):
            ok = mid
        else:
            ng = mid
    print(ok)



if __name__ == '__main__':
    ABC131E()

Submission status: Accepted

Solution code:
import sys
# input関係の定義
sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def fi(): return float(input())
def mfi(): return map(float, input().rstrip().split())
def lmfi(): return list(map(float, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()
# template

# BEGIN CUT HERE
class RollingHash():
    BASE1 = 1007
    BASE2 = 2009
    MOD1 = 1000000007
    MOD2 = 1000000009

    def __init__(self, s):
        self.n = len(s)
        self.hash1 = [0] * (self.n + 1)
        self.hash2 = [0] * (self.n + 1)
        self.power1 = [1] * (self.n + 1)
        self.power2 = [1] * (self.n + 1)
        for i, e in enumerate(s):
            self.hash1[i + 1] = (self.hash1[i] * self.__class__.BASE1 + ord(e)) % self.__class__.MOD1
            self.hash2[i + 1] = (self.hash2[i] * self.__class__.BASE2 + ord(e)) % self.__class__.MOD2
            self.power1[i + 1] = (self.power1[i] * self.__class__.BASE1) % self.__class__.MOD1
            self.power2[i + 1] = (self.power2[i] * self.__class__.BASE2) % self.__class__.MOD2

    def get(self, l: int, r: int):
        res1 = self.hash1[r] - self.hash1[l] * self.power1[r - l] % self.__class__.MOD1
        if(res1 < 0):
            res1 += self.__class__.MOD1
        res2 = self.hash2[r] - self.hash2[l] * self.power2[r - l] % self.__class__.MOD2
        if(res2 < 0):
            res2 += self.__class__.MOD2
        return (res1, res2)
# END CUT HERE

def ABC131E():
    N = ii()
    S = li()
    rh = RollingHash(S)
    def check(n: int):
        d = dict()
        for i in range(N - n + 1):
            p = rh.get(i, i + n)
            if p in d:
                if(i - d[p] >= n):
                    return True
            else:
                d[p] = i
        return False
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if check(mid):
            ok = mid
        else:
            ng = mid
    print(ok)



if __name__ == '__main__':
    ABC131E()

Submission status: Accepted

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

class RollingHash():
    BASE1 = 1007
    BASE2 = 2009
    MOD1 = 1000000007
    MOD2 = 1000000009
 
    def __init__(self, s, opt=2):
        self.n = len(s)
        self.opt = opt
        self.hash1 = [0] * (self.n + 1)
        self.power1 = [1] * (self.n + 1)
        if opt == 2:
            self.hash2 = [0] * (self.n + 1)
            self.power2 = [1] * (self.n + 1)
        for i, e in enumerate(s):
            self.hash1[i + 1] = (self.hash1[i] * self.__class__.BASE1 + ord(e)) % self.__class__.MOD1
            self.power1[i + 1] = (self.power1[i] * self.__class__.BASE1) % self.__class__.MOD1
            if opt == 2:
                self.hash2[i + 1] = (self.hash2[i] * self.__class__.BASE2 + ord(e)) % self.__class__.MOD2
                self.power2[i + 1] = (self.power2[i] * self.__class__.BASE2) % self.__class__.MOD2
 
    def get(self, l: int, r: int):
        res1 = self.hash1[r] - self.hash1[l] * self.power1[r - l] % self.__class__.MOD1
        if(res1 < 0):
            res1 += self.__class__.MOD1
        if self.opt == 2:
            res2 = self.hash2[r] - self.hash2[l] * self.power2[r - l] % self.__class__.MOD2
            if(res2 < 0):
                res2 += self.__class__.MOD2
        return (res1, res2) if self.opt == 2 else res1


    
rh = RollingHash(S, opt=1)

def check(n: int):
    d = dict()
    for i in range(N - n + 1):
        p = rh.get(i, i + n)
        if p in d.keys():
            if(i - d[p] >= n):
                return True
        else:
            d[p] = i
    return False
    
ok, ng = 0, N // 2 + 1
while ng - ok > 1:
    mid = (ok + ng) // 2
    if check(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Accepted

Solution code:
n = int(input())
s = list(input())
ansl = []
for i in range(1,n):
    ans = 0
    count = 0
    for j in range(n-i):
        #print(s[j],s[j+i])
        if s[j] == s[j+i]:
            count += 1
        else:
            if count > 0:
                if count > ans:
                    ans = min(count,i)
                count = 0
    if count > ans:
        ans = min(count,i)
    ansl.append(ans)
print(max(ansl))

Submission status: Accepted

Solution code:
n=int(input());s=input()
ans=i=j=0
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:
def main(size, text):
    pattern = ""
    matchlen = 0

    for i in range(size):
        pattern += text[i]
        while (len(pattern) > 0 and len(pattern) <= len(text[i+1:])):
            if pattern in text[i+1:]:
                matchlen = max(matchlen, len(pattern))
                break
            else:
                pattern = pattern[1:]
    
    return matchlen

if __name__ == '__main__':
    N = int(input())
    S = input()
    print (main(N, S))

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/abc141/submissions/7539109
#Z-Algorithm
n = int(input())
s = input()
 
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)

Submission status: Accepted

Solution code:
def Z(s,ls):
    lcp = [0]*ls
    lcp[0] = ls
    i,j = 1,0
    while i < ls:
        while i+j < ls and s[j] == s[i+j]:
            j += 1
        lcp[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < ls and k + lcp[k] < j:
            lcp[i+k] = lcp[k]
            k += 1
        i += k
        j -= k
    for i in range(ls):
        lcp[i] = min(lcp[i],i)
    return max(lcp)

n = int(input())
s = list(map(ord,list(input())))
print(max(Z(s[i:],n-i) for i in range(n)))

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
# input関係の定義
sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def fi(): return float(input())
def mfi(): return map(float, input().rstrip().split())
def lmfi(): return list(map(float, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()
# template

# BEGIN CUT HERE
class RollingHash():
    BASE1 = 1007
    BASE2 = 2009
    MOD1 = 1000000007
    MOD2 = 1000000009

    def __init__(self, s):
        self.n = len(s)
        self.hash1 = [0] * (self.n + 1)
        self.hash2 = [0] * (self.n + 1)
        self.power1 = [1] * (self.n + 1)
        self.power2 = [1] * (self.n + 1)
        for i, e in enumerate(s):
            self.hash1[i + 1] = (self.hash1[i] * self.__class__.BASE1 + ord(e)) % self.__class__.MOD1
            self.hash2[i + 1] = (self.hash2[i] * self.__class__.BASE2 + ord(e)) % self.__class__.MOD2
            self.power1[i + 1] = (self.power1[i] * self.__class__.BASE1) % self.__class__.MOD1
            self.power2[i + 1] = (self.power2[i] * self.__class__.BASE2) % self.__class__.MOD2

    def get(self, l: int, r: int):
        res1 = self.hash1[r] - self.hash1[l] * self.power1[r - l] % self.__class__.MOD1
        if(res1 < 0):
            res1 += self.__class__.MOD1
        res2 = self.hash2[r] - self.hash2[l] * self.power2[r - l] % self.__class__.MOD2
        if(res2 < 0):
            res2 += self.__class__.MOD2
        return (res1, res2)
# END CUT HERE

def ABC131E():
    N = ii()
    S = li()
    rh = RollingHash(S)
    def check(n: int):
        d = dict()
        for i in range(N - n + 1):
            p = rh.get(i, i + n)
            if p in d:
                if(i - d[p] >= n):
                    return True
            else:
                d[p] = i
        return False
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if check(mid):
            ok = mid
        else:
            ng = mid
    print(ok)



if __name__ == '__main__':
    ABC131E()

Submission status: Accepted

Solution code:
import sys
# input関係の定義
sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def fi(): return float(input())
def mfi(): return map(float, input().rstrip().split())
def lmfi(): return list(map(float, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()
# template

# BEGIN CUT HERE
class RollingHash():
    BASE1 = 1007
    BASE2 = 2009
    MOD1 = 1000000007
    MOD2 = 1000000009

    def __init__(self, s, opt=2):
        self.n = len(s)
        self.opt = opt
        self.hash1 = [0] * (self.n + 1)
        self.power1 = [1] * (self.n + 1)
        if opt == 2:
            self.hash2 = [0] * (self.n + 1)
            self.power2 = [1] * (self.n + 1)
        for i, e in enumerate(s):
            self.hash1[i + 1] = (self.hash1[i] * self.__class__.BASE1 + ord(e)) % self.__class__.MOD1
            self.power1[i + 1] = (self.power1[i] * self.__class__.BASE1) % self.__class__.MOD1
            if opt == 2:
                self.hash2[i + 1] = (self.hash2[i] * self.__class__.BASE2 + ord(e)) % self.__class__.MOD2
                self.power2[i + 1] = (self.power2[i] * self.__class__.BASE2) % self.__class__.MOD2

    def get(self, l: int, r: int):
        res1 = self.hash1[r] - self.hash1[l] * self.power1[r - l] % self.__class__.MOD1
        if(res1 < 0):
            res1 += self.__class__.MOD1
        if self.opt == 2:
            res2 = self.hash2[r] - self.hash2[l] * self.power2[r - l] % self.__class__.MOD2
            if(res2 < 0):
                res2 += self.__class__.MOD2
        return (res1, res2) if self.opt == 2 else res1
# END CUT HERE

# notypehinting
def ABC131E():
    N = ii()
    S = li()
    rh = RollingHash(S, opt=1)
    def check(n: int):
        d = dict()
        for i in range(N - n + 1):
            p = rh.get(i, i + n)
            if p in d.keys():
                if(i - d[p] >= n):
                    return True
            else:
                d[p] = i
        return False
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if check(mid):
            ok = mid
        else:
            ng = mid
    print(ok)



if __name__ == '__main__':
    ABC131E()

Submission status: Accepted

Solution code:
N = int(input())
S = input()
l, r = 0, N

def pow_mod(a, b, m):
  ab = 1
  for _ in range(b):
    ab = (ab * a) % m
  return ab

def c2n(c):
  return ord(c) - 97

def hash(s, B, H):
  sh = 0
  for c in s:
    sh = (sh * B + c2n(c)) % H
  return sh

def t(n):
  B, H = 10 ** 8 + 7, 2 ** 64

  if n*2 > N:
    return False
  s, t = S[:n], S[n:n*2]
  sh, th = hash(s, B, H), hash(t, B, H)
  if sh == th:
    return True
  ss = set([sh])
  Bn = pow_mod(B, n, H)
  for i in range(0, N-2*n):
    sh = (sh * B - c2n(S[i]) * Bn + c2n(S[i+n])) % H
    th = (th * B - c2n(S[i+n]) * Bn + c2n(S[i+2*n])) % H
    ss.add(sh)
    if th in ss:
      return True
  return False

while l+1<r:
  m = (l+r)//2
  if t(m):
    l=m
  else:
    r=m

print(l)

Submission status: Accepted

Solution code:
import random
import string
N = int(input())
S = input()
l, r = 0, N

def pow_mod(a, b, m):
  ab = 1
  for _ in range(b):
    ab = (ab * a) % m
  return ab

def c2n(c):
  return ord(c) - 97

def hash(s, B, H):
  sh = 0
  for c in s:
    sh = (sh * B + c2n(c)) % H
  return sh

def t(n):
  B, H = 10 ** 8 + 7, 2 ** 64

  if n*2 > N:
    return False
  s, t = S[:n], S[n:n*2]
  sh, th = hash(s, B, H), hash(t, B, H)
  if sh == th:
    return True
  ss = set([sh])
  Bn = pow_mod(B, n, H)
  for i in range(0, N-2*n):
    sh = (sh * B - c2n(S[i]) * Bn + c2n(S[i+n])) % H
    th = (th * B - c2n(S[i+n]) * Bn + c2n(S[i+2*n])) % H
    ss.add(sh)
    if th in ss:
      return True
  return False

while l+1<r:
  m = (l+r)//2
  if t(m):
    l=m
  else:
    r=m

print(l)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
n = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip()


dp = [[0 for i in range(n)] for j in range(n)]
#初期条件
for j in range(1, n):
    if S[0] == S[j]:
        dp[0][j] = 1

#print(dp)

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

maxp = 0
for i in range(n-1):
    for j in range(i+1, n):
        if maxp < dp[i][j]:
            maxp = dp[i][j]
#print(dp)
print(maxp)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def Z(s):
    """
    s: str
    return list of int with length len(s)
    """
    # initialization
    n=len(s)
    z=[0]*n
    z[0]=n
    # construct
    L,R=0,0
    for i in range(1,n):
        if i>=R: # 過去の結果が全く使えない
            L=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
def resolve():
    n=int(input())
    s=input()
    ans=0
    for i in range(n):
        z=Z(s[i:])
        k=len(z) # k=n-i
        for j in range(k):
            ans=max(ans,min(j,z[j]))
    print(ans)
resolve()

Submission status: Accepted

Solution code:
def z(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 j == 0:
            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()
r = 0
for i in range(n):
    a = z(s[i:])
    for j in range(len(a)):
        if a[j] <= j:
            r = max(r, a[j])
print(r)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
dp = [[0] * (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
result = 0
for i in range(N):
    for j in range(i + 1, N):
        t = dp[i][j]
        if t > j - i:
            t = j - i
        if t > result:
            result = t
print(result)

Submission status: Accepted

Solution code:
# PyPy なら通る
# DP(貰うDP)
N = int(input())
S = input()

dp = [[0] * (N + 1) for _ in range(N + 1)]
result = 0
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
            t = dp[i][j]
            if t > j - i:
                t = j - i
            if t > result:
                result = t
print(result)

Submission status: Accepted

Solution code:
# PyPy なら通る
# DP(貰うDP)
N = int(input())
S = input()

dp = [[0] * (N + 1) for _ in range(N + 1)]
result = 0
for i in range(N - 1, -1, -1):
    for j in range(N - 1, -1, -1):
        if S[i] == S[j]:
            t = dp[i + 1][j + 1] + 1
            dp[i][j] = t
            if t > j - i:
                t = j - i
            if t > result:
                result = t
print(result)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
dp = [[0] * (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] = 0
        else:
            dp[i][j] = dp[i + 1][j + 1] + 1
result = 0
for i in range(N):
    for j in range(i + 1, N):
        t = dp[i][j]
        if t > j - i:
            t = j - i
        if t > result:
            result = t
print(result)

Submission status: Accepted

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

result = 0
for i in range(N - 1, 0, -1):
    if i <= result:
        break
    t = 0
    for j in range(N - i):
        if S[j] == S[j+i]:
            t += 1
            if t > result:
                result = t
            if result == i:
                break
        else:
            t = 0

print(result)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
r=[[0]*(n+1) for _ in range(n+1)]

#print(r)

maxV=0
for i in range(n):
  for j in  range(n):
    ii=n-1-i
    jj=n-1-j
    if s[ii]==s[jj]:
      r[ii][jj]=min(r[ii+1][jj+1]+1,abs(ii-jj))
      maxV=max(maxV,r[ii][jj])

print(maxV)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
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 resolve():
    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)
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 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):
            if rank[i]==0: continue
            j=sa[rank[i]-1]
            if h>0: h-=1
            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 resolve():
    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)
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    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)
resolve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter

def main():
    n = int(input().strip())
    v = input().strip()
    ans = 0
    dp = [[0] * (n+1) for _ in range(n+1)]
    for i in reversed(range(n)):
        for j in reversed(range(n)):
            if v[i] == v[j]:
                dp[i][j] = dp[i+1][j+1] + 1
                ans = max(ans, min(abs(i-j), dp[i][j]))
    print(ans)
    # print(dp)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

#output
M = [0]* N
j = 0

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
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):
        """
        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

def resolve():
    n=int(input())
    S=input()
    # d=0ではtrue,d=nではfalseなので、そこでbisectする
    rh=RollingHash(S)
    def judge(d):
        # initialize
        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))
resolve()
#%%
import sys
from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """5
ababa"""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """2
xy"""
        output = """0"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """13
strangeorange"""
        output = """5"""
        self.assertIO(input, output)

if __name__ == "__main__":
    unittest.main()