Problem:


Score : 500 points

Problem Statement

Given is a string S of length N.

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

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

l_1 + len \leq l_2

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

If there is no such integer len, print 0.

Constraints

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

|S| = N

S consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

N
S

Output

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

Sample Input 1

5
ababa

Sample Output 1

2

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

Sample Input 2

2
xy

Sample Output 2

0

No non-empty string satisfies the conditions.

Sample Input 3

13
strangeorange

Sample Output 3

5



Sample input:
5
ababa


Sample output:
2

Submission status: Accepted

Solution code:
def z_algolithm(S, x):
    length = len(S) - x
    A = [0]*length
    B = [0]
    i = 1; j = 0
    while i < length:
        while i+j < length and S[x+j] == S[x+i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        B.append(min(j, i))
        k = 1
        while k < length - i  and k + A[k] < j :
            A[i+k] = A[k]
            k += 1
        i += k
        j -= k
    ans = max(B)
    return ans

N = int(input())
S = input()
ans = max([z_algolithm(S, x) for x in range(N)])
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
 
def z_algo(s):
    s_length = len(s)
    l, r = 0, 0
    Z = [0]*s_length
    Z[0] = s_length
    for i in range(1, s_length):
        if r<i:
            l, r = i, i
            while r<s_length and s[r]==s[r-l]:
                r += 1
            Z[i] = r-i
            r -= 1
        else:
            k = i-l
            if i+Z[k]-1<r:
                Z[i] = Z[k]
            else:
                l = i
                while r<s_length and s[r]==s[r-l]:
                    r += 1
                Z[i] = r-i
                r -= 1
    return Z

ans = 0
for i in range(N):
    z = z_algo(S[i:])
    for j in range(i, N):
        ans = max(ans, min(j-i, z[j-i]))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
 
def z_algo(s):
    s_length = len(s)
    l, r = 0, 1
    Z = [0]*s_length
    Z[0] = s_length
    for i in range(1, s_length):
        if r<i:
            l, r = i, i
            while r<s_length and s[r]==s[r-l]:
                r += 1
            Z[i] = r-i
            r -= 1
        else:
            k = i-l
            if i+Z[k]-1<r:
                Z[i] = Z[k]
            else:
                l = i
                while r<s_length and s[r]==s[r-l]:
                    r += 1
                Z[i] = r-i
                r -= 1
    return Z

ans = 0
for i in range(N):
    z = z_algo(S[i:])
    for j in range(i, N):
        ans = max(ans, min(j-i, z[j-i]))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
 
left = 0
right = 1
max_length = 0
 
while left < N:
    if right - left > N - right:
        break
    serch_str = S[left:right]
    if serch_str in S[right:]:
        max_length = max(max_length, len(serch_str))
        right += 1
    else:
        left += 1
 
print(max_length)

Submission status: Accepted

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

left = 0
right = 1
max_length = 0

while left < N:
    if right - left > N - right:
        break
    serch_str = S[left:right]
    if serch_str in S[right:]:
        max_length = max(max_length, len(serch_str))
        right += 1
    else:
        left += 1

print(max_length)

Submission status: Accepted

Solution code:
N=int(input())
S=input()
maxLen=i=j=0
while j<N:
  if j-i > N-j:
      break  

  t=S[i:j]
  if t in S[j:]:
    maxLen=max(maxLen,len(t))
    j+=1
  else:
    i+=1
print(maxLen)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import queue
import re
import math
import functools

def s_raw():
    return input().rstrip("\r")

def int_raw():
    return int(input())


def ss_raw():
    return input().split()


def ints_raw():
    return list(map(int, ss_raw()))


INF = 1 << 29


def make1d_arr(n, val=INF):
    return [val for i in range(n)]


def make2d_arr(h, w, val=INF):
    return [[val for i in range(w)]for i in range(h)]


def gcd(a, b):
    if(b == 0):
        return a
    return gcd(b, a % b)


def BFord(n,es):
    v_cost = [INF]*n
    v_cost[0] = 0
    for v in range(n*2):
        for e in es:
            frm = e[0]
            to = e[1]
            if v_cost[to] > v_cost[frm]+e[2]:
                v_cost[to] = v_cost[frm]+e[2]
                if v >= n:
                    v_cost[to] = -INF
        if v == n-1:
            prev = v_cost[:]
    v_cost = [-INF if prev[idx]!=v_cost[idx] else v_cost[idx] for idx in range(n)]
    return v_cost
    
def ZAlgo(s):
    l = len(s)
    A = [0]*l
    i =1
    j =0
    A[0]=l
    while i<l:
        while i+j<l and s[j] == s[i+j]:
            j+=1
        if j==0:
            i+=1
            continue
        A[i]=j
        k=1
        while (i+k<l) and (k+A[k]<j):
            A[i+k] =A[k]
            k+=1
        i+=k
        j-=k
    return A


def main():
    n = int_raw()
    S = s_raw()
    ans = 0
    for s_idx in range(len(S)):
        A = ZAlgo(S[s_idx:])
        ans = max([min(idx,a) for idx,a in enumerate(A)]+[ans])
    return ans


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

Submission status: Accepted

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

i = 0
j = 1
res = 0
while j < N:
    sub = S[i:j]
    main = S[j:]
    if sub in main:
        j += 1
        res = max(res, len(sub))
    else:
        i += 1
    if i == j:
        i += 1
        j += 2
print(res)

Submission status: Accepted

Solution code:
N=int(input())
S=input()
a=i=j=0
while j<N:
  if j-i > N-j:
      break  

  t=S[i:j]
  if t in S[j:]:
    a=max(a,len(t))
    j+=1
  else:
    i+=1
print(a)

Submission status: Accepted

Solution code:
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)
 
def check(l):
    place = {}
    for i in range(n - l + 1):
        hs = RH.get(i, i + l)
        if hs in place:
            if i - place[hs] >= l:
                return True
        else:
            place[hs] = i
    return False

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

print(l)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
class RollingHash():
    def __init__(self, s):
        self.mask30 = (1 << 30) - 1
        self.mask31 = (1 << 31) - 1
        self.length = len(s)
        self.base = 1009
        self.mod = (1 << 61) - 1
        self.hash = [0] * (self.length + 1)
        self.pow = [1] * (self.length + 1)

        for i in range(self.length):
            self.hash[i+1] = self.calcmod(self.mul(self.hash[i], self.base) + ord(s[i]))
            self.pow[i+1] = self.calcmod(self.mul(self.pow[i], self.base))
    
    def mul(self, l, r):
        lu = l >> 31
        ld = l & self.mask31
        ru = r >> 31
        rd = r & self.mask31
        middle = ld * ru + lu * rd
        return ((lu * ru) << 1) + ld * rd + ((middle & self.mask30) << 31) + (middle >> 30)
    
    def calcmod(self, val):
        val = (val & self.mod) + (val >> 61)
        if val > self.mod:
            val -= self.mod
        return val

    def get(self, l, r):
        t = self.calcmod(self.hash[r] - self.mul(self.hash[l], self.pow[r-l]) + self.mod)
        return t

n = int(input())
s = input()
RH = RollingHash(s)

def check(l):
    place = {}
    for i in range(n - l + 1):
        hs = RH.get(i, i + l)
        if hs in place:
            if i - place[hs] >= l:
                return True
        else:
            place[hs] = i
    return False

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

print(l)

Submission status: Accepted

Solution code:
class RollingHash():
    def __init__(self, s):
        self.mask30 = (1 << 30) - 1
        self.mask31 = (1 << 31) - 1
        self.length = len(s)
        self.base = 1009
        self.mod = (1 << 61) - 1
        self.hash = [0] * (self.length + 1)
        self.pow = [1] * (self.length + 1)

        for i in range(self.length):
            self.hash[i+1] = self.calcmod(self.mul(self.hash[i], self.base) + ord(s[i]))
            self.pow[i+1] = self.calcmod(self.mul(self.pow[i], self.base))
    
    def mul(self, l, r):
        lu = l >> 31
        ld = l & self.mask31
        ru = r >> 31
        rd = r & self.mask31
        middle = ld * ru + lu * rd
        return ((lu * ru) << 1) + ld * rd + ((middle & self.mask30) << 31) + (middle >> 30)
    
    def calcmod(self, val):
        val = (val & self.mod) + (val >> 61)
        if val > self.mod:
            val -= self.mod
        return val

    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)

def check(l):
    place = {}
    for i in range(n - l + 1):
        hs = RH.get(i, i + l)
        if hs in place:
            if i - place[hs] >= l:
                return True
        else:
            place[hs] = i
    return False

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

print(l)

Submission status: Accepted

Solution code:
class RollingHash():
    def __init__(self, s):
        self.length = len(s)
        self.base1 = 1009
        self.base2 = 1007
        self.mod1 = 10**9 + 7
        self.mod2 = 10**9 + 9
        self.hash1 = [0] * (self.length + 1)
        self.hash2 = [0] * (self.length + 1)
        self.pow1 = [1] * (self.length + 1)
        self.pow2 = [1] * (self.length + 1)

        for i in range(self.length):
            self.hash1[i+1] = (self.hash1[i] + ord(s[i])) * self.base1 % self.mod1
            self.hash2[i+1] = (self.hash2[i] + ord(s[i])) * self.base2 % self.mod2
            self.pow1[i+1] = self.pow1[i] * self.base1 % self.mod1
            self.pow2[i+1] = self.pow2[i] * self.base2 % self.mod2
        
    def get(self, l, r):
        t1 = self.hash1[r] - self.hash1[l] * self.pow1[r-l] % self.mod1
        t1 = (t1 + self.mod1) % self.mod1
        t2 = self.hash2[r] - self.hash2[l] * self.pow2[r-l] % self.mod2
        t2 = (t2 + self.mod2) % self.mod2
        return (t1, t2)

class FastRollingHash():
    def __init__(self, s):
        self.length = len(s)
        self.base = 1009
        self.mod = (1 << 61) - 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)

def check(l):
    place = {}
    for i in range(n - l + 1):
        hs = RH.get(i, i + l)
        if hs in place:
            if i - place[hs] >= l:
                return True
        else:
            place[hs] = i
    return False

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

print(l)

Submission status: Accepted

Solution code:
class RollingHash():
    def __init__(self, s):
        self.length = len(s)
        self.base1 = 1009
        self.base2 = 1007
        self.mod1 = 10**9 + 7
        self.mod2 = 10**9 + 9
        self.hash1 = [0] * (self.length + 1)
        self.hash2 = [0] * (self.length + 1)
        self.pow1 = [1] * (self.length + 1)
        self.pow2 = [1] * (self.length + 1)

        for i in range(self.length):
            self.hash1[i+1] = (self.hash1[i] + ord(s[i])) * self.base1 % self.mod1
            self.hash2[i+1] = (self.hash2[i] + ord(s[i])) * self.base2 % self.mod2
            self.pow1[i+1] = self.pow1[i] * self.base1 % self.mod1
            self.pow2[i+1] = self.pow2[i] * self.base2 % self.mod2
        
    def get(self, l, r):
        t1 = self.hash1[r] - self.hash1[l] * self.pow1[r-l] % self.mod1
        t1 = (t1 + self.mod1) % self.mod1
        t2 = self.hash2[r] - self.hash2[l] * self.pow2[r-l] % self.mod2
        t2 = (t2 + self.mod2) % self.mod2
        return (t1, t2)

class FastRollingHash():
    def __init__(self, s):
        self.length = len(s)
        self.base = 1009
        self.mod = (1 << 61) - 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 = FastRollingHash(s)

def check(l):
    place = {}
    for i in range(n - l + 1):
        hs = RH.get(i, i + l)
        if hs in place:
            if i - place[hs] >= l:
                return True
        else:
            place[hs] = i
    return False

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

print(l)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N = int(input())
S = list(input()) + ["!"]
dp = [[0] * N for _ in range(N)]
for j in range(1, N):
  if S[0] == S[j]:
    dp[0][j] = 1
res = 0
for i in range(N):
  for j in range(i, N):
    res = max(dp[i][j], res)
    if i == N - 1 or j == N - 1:
      continue
    if S[i + 1] == S[j + 1] and j - i > dp[i][j]:
      dp[i + 1][j + 1] = dp[i][j] + 1
    else:
      dp[i + 1][j + 1] = 0
print(res)

Submission status: Accepted

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

result=0
for i in range(1,n):
    ml=min(i,n-i)
    count=0
    for j in range(n-i):
        if s[j]==s[j+i]:
            count+=1
        else:
            result=max(count,result)
            count=0
        if count==ml:
            result=max(result,count)
            break
        result=max(result,count)
print(result)

Submission status: Accepted

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

result = 0
for i in range(1, n):
    maxLen = min(i, n-i)
    tmp = 0
    for j in range(n-i):
        if s[j] == s[j+i]:
            tmp += 1
        else:
            if result < tmp:
                result = tmp
            tmp = 0
        if tmp == maxLen:
            break
    if result < tmp:
        result = tmp
print(result)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
B = 127
MOD = 10 ** 11 + 7

H = [0] * (len(S) + 1)
P = [1] * (len(S) + 1)
b = pow(B, N-1)
for i in range(len(S)):
    H[i+1] = (H[i] + ord(S[i]) * b) % MOD
    P[i+1] = (P[i] * B) % MOD
    b //= B

l = 0
r = N
ans = 0
while r - l > 1:
    mid = (l + r) // 2
    tmp = {}
    for i in range(N - mid + 1):
        h = ((H[mid+i] - H[i]) * P[mid+i-1]) % MOD
        if h in tmp and i - tmp[h] >= mid:
            l = mid
            ans = mid
            break
        else:
            if not h in tmp:
                tmp[h] = i
    else:
        r = mid
        
print(ans)

Submission status: Accepted

Solution code:
# ABC141E - Who Says a Pun?
class RollingHash:
    def __init__(self, source: str, base=1007, mod=10 ** 9 + 7):
        self.source = source
        self.length = len(source)
        self.base = base
        self.mod = mod
        self.hash = self._get_hash_from_zero()
        self.power = self._get_base_pow()

    def _get_hash_from_zero(self):  # compute hash of interval [0, right)
        cur, hash_from_zero = 0, [0]
        for e in self.source:
            cur = (cur * self.base + ord(e)) % self.mod
            hash_from_zero.append(cur)
        return hash_from_zero

    def _get_base_pow(self):  # computer mod of power of base
        cur, power = 1, [1]
        for i in range(self.length):
            cur *= self.base % self.mod
            power.append(cur)
        return power

    def get_hash(self, l: int, r: int):  # compute hash of interval [left, right)
        return (self.hash[r] - self.hash[l] * self.power[r - l]) % self.mod


def main():
    N = int(input())
    S = input().rstrip()
    rh, ok, ng = RollingHash(S), 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        flg, memo = 0, set()
        for i in range(N - 2 * mid + 1):
            memo.add(rh.get_hash(i, i + mid))
            if rh.get_hash(i + mid, i + 2 * mid) in memo:
                flg = 1
                break
        if flg:
            ok = mid  # next mid will be longer
        else:
            ng = mid  # next mid will be shorter
    print(ok)  # max length of substrings appeared twice or more


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    N = int(input())
    S = input()
    left = 0
    right = 1
    ans = 0
    while left < N:
        S1 = S[left:right]
        S2 = S[right:]
        if S1 in S2:
            ans = max(ans, len(S1))
            right += 1
        else:
            left += 1
    print(ans)

if __name__ == '__main__': main()

Submission status: Accepted

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

left = 0
right = 1
ans = 0

while left < n:
    s1 = s[left:right]
    s2 = s[right:]
    if s1 in s2:
        ans = max(ans,len(s1))
        right += 1
    else:
        left += 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):
    T = S[i:]
    Ai = z_algo(T)
    for j in range(len(Ai)):
        if Ai[j] <= j:
            ans = max(ans, Ai[j])

print(ans)

Submission status: Accepted

Solution code:
import math
MOD = pow(2,61) - 1
def charToNum(char):
    return ord(char) - 96

def check(string,subLen):
    if subLen == 0: return True
    #長さsubLenの部分文字列すべてについてローリングハッシュを計算して、
    #一致するものがあるかどうかを計算する。
    # setOfRollingHash = set()
    dictOfRollingHash = {}
    totalLen = len(string)
    h = 0
    b = 1
    for i in range(subLen):
        c = string[subLen - 1 - i]
        h += charToNum(c) * b
        b *= 27
        b %= MOD
    h %= MOD
    dictOfRollingHash[h] = 0
    maxBase = pow(27,subLen - 1,MOD) 
    for i in range(1,totalLen - subLen + 1):
        h -= maxBase * charToNum(string[i - 1])
        h *= 27
        h += charToNum(string[i + subLen - 1])
        h %= MOD
        if h in dictOfRollingHash:
            if i - dictOfRollingHash[h] >= subLen:
                return True
        else:
            dictOfRollingHash[h] = i
    return False

N = int(input())
S = input()
ok = 0
ng = N + 1
while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    if check(S,mid):
        ok = mid
    else:
        ng = mid
print(ok)

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 si(): return 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

        if self.opt == 2:
            return (res1, res2)
        else:
            return res1
# END CUT HERE
if not __debug__:
    import io
    import random
    class MyStdin(io.TextIOWrapper):
        @classmethod
        def readline(cls):
            N = 1000000
            yield "{}\n".format(N)
            yield "{}\n".format(''.join([chr(random.randint(0, 25) + ord("a")) for i in range(N // 5)] * 5))
    input = MyStdin.readline().__next__

def ABC131E():
    N = ii()
    S = si()
    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__':
    if not __debug__:
        import cProfile
        cProfile.run('ABC131E()', sort=1)
    else:
        ABC131E()

Submission status: Accepted

Solution code:

import sys
import collections


def main():
    n = int(sys.stdin.readline().strip())
    s = sys.stdin.readline().strip()
    # s = 'strangeorange'
    dp = [[0] * n for _ in range(n)]

    for i in range(n):
        dp[i][i] = 1

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


main()

Submission status: Accepted

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

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

def z_algorithm(s):
    n = len(s)
    Z = [0] * n
    Z[0] = n
    L,R = 0,0 #L:=LCPの左端,R:=LCPの右端
    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
            R -= 1
        elif Z[i-L] < R-i+1:#比較結果を再利用できる
            Z[i] = Z[i - L]
        else:#比較結果を一部再利用できる
            L = i
            R += 1
            while R < n and s[R-L] == s[R]:
                R += 1
            Z[i] = R - L
            R -= 1
    return Z

n = I()
s = input()
ans = 0
for i in range(n):
    Z = z_algorithm(s[i:])
    for j,z in enumerate(Z):
        if j < z:
            continue
        ans = max(ans,z)
print(ans)

Submission status: Accepted

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

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

def z_algorithm(s):
    n = len(s)
    Z = [0] * n
    Z[0] = n
    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

n = I()
s = input()
ans = 0
for i in range(n):
    Z = z_algorithm(s[i:])
    for j,z in enumerate(Z):
        if j < z:
            continue
        ans = max(ans,z)
print(ans)

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 si(): return 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

        if self.opt == 2:
            return (res1, res2)
        else:
            return res1
# END CUT HERE

def ABC131E():
    N = ii()
    S = si()
    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()