Problem:


Score : 500 points

Problem Statement

Given is a string S of length N.

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

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

l_1 + len \leq l_2

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

If there is no such integer len, print 0.

Constraints

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

|S| = N

S consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

N
S

Output

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

Sample Input 1

5
ababa

Sample Output 1

2

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

Sample Input 2

2
xy

Sample Output 2

0

No non-empty string satisfies the conditions.

Sample Input 3

13
strangeorange

Sample Output 3

5



Sample input:
5
ababa


Sample output:
2

Submission status: Accepted

Solution code:
#!/usr/bin/python3

import math
import sys


DEBUG = False


def inp():
    return sys.stdin.readline().rstrip()


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


MOD = 10 ** 9 + 7
BASE = 29


def has_dup(V, sz):
    N = len(V)

    h = 0
    p = 1
    for i in range(sz):
        h *= BASE
        h += V[i]
        h %= MOD

        p *= BASE
        p %= MOD

    h2i = {h: [0]}
    for i in range(sz, N):
        j = i - sz + 1
        h *= BASE
        h += V[i]
        h += MOD - ((p * V[i - sz]) % MOD)
        h %= MOD
        if h not in h2i:
            h2i[h] = []
        h2i[h].append(j)

    for a in h2i.values():
        alen = len(a)
        for i in range(alen):
            ii = a[i]
            for j in range(i + 1, alen):
                ji = a[j]
                if ji - ii < sz:
                    continue
                if V[ii:ii + sz] == V[ji:ji + sz]:
                    return True

    return False


def solve(N, S):
    if N <= 26:
        has_ans = False
        for v in range(ord('a'), ord('z') + 1):
            ch = chr(v)
            if S.count(ch) >= 2:
                has_ans = True
                break
        if not has_ans:
            return 0

    V = [ord(c) - ord('a') for c in S]

    lb = 1
    ub = N // 2 + 1
    while ub - lb > 1:
        mid = (lb + ub) // 2
        if has_dup(V, mid):
            lb = mid
        else:
            ub = mid

    return lb


def main():
    N = int(inp())
    S = inp()
    print(solve(N, S))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def resolve():
    import sys
    input=sys.stdin.readline
    N = int(input().rstrip())
    S = input().rstrip()

    def z_algo(s):
        """
        param 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
                R-=1 # 0-indexedでiと比較するため
            elif z[i-L]<R-i+1:
                z[i]=z[i-L]
            else:
                L=i
                R+=1 # Rまでは確定しているので、R+1から確認
                while(R<n and s[R-L]==s[R]): R+=1
                z[i]=R-L
                R-=1
        return z

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

resolve()

Submission status: Accepted

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


def check(vlen):
    part = set()
    for l1 in range(N - vlen * 2 + 1):
        part.add(S[l1:l1 + vlen])
        l2 = l1 + vlen
        if S[l2:l2 + vlen] in part:
            return True
    return False


oklen = 0
nglen = N // 2 + 1

while nglen - oklen > 1:
    midlen = (oklen + nglen) // 2
    if check(midlen):
        oklen = midlen
    else:
        nglen = midlen
print(oklen)

Submission status: Accepted

Solution code:
# ABC141E - Who Says a Pun?
def resolve():
    N = int(input())
    S = input().rstrip()
    ok, ng = 0, N // 2 + 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        flg, checked = 0, set()
        for i in range(N - 2 * mid + 1):
            checked.add(hash(S[i : i + mid]))
            if hash(S[i + mid : i + 2 * mid]) in checked:
                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


resolve()

Submission status: Accepted

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

def main():
    N = int(input())
    S = "_" + input()

    dp = [[0 for k in range(N+1)] for l in range(N+1)]
    for k in range(1,N):
        for l in range(k+1,N+1):
            if S[k] == S[l]:
                dp[k][l] = dp[k-1][l-1] + 1

    ans = 0
    for k in range(1,N):
        for l in range(k+1,N+1):
            if l-k >= dp[k][l]:
                ans = max(ans,dp[k][l])

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

def main():
    def input():
        return sys.stdin.readline()
    N = int(input())
    S = "_" + input()

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

    for k in range(1,N):
        for l in range(k+1,N+1):
            if S[k] == S[l]:
                dp[k][l] = dp[k-1][l-1] + 1
    ans = 0
    for k in range(1,N):
        for l in range(k+1,N+1):
            if l-k >= dp[k][l]:
                ans = max(ans,dp[k][l])

    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def z_arr(s):

    Z = [0] * len(s)
    Z[0] = len(s)

    rt = 0
    lt = 0

    for k in range(1, len(s)):
        if k > rt:
            n = 0
            while k + n < len(s) and s[n] == s[k + n]:
                n += 1

            Z[k] = n
            if n > 0:
                lt = k
                rt = k + n - 1
        else:

            p = k - lt
            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

N = int(input())
S = input()
answer = 0
for i in range(N-1):
    ZZ = z_arr(S[i:])
    temp_max = 0
    for j in range(len(ZZ)):
        if min(ZZ[j], j) > temp_max:
            temp_max = min(ZZ[j], j)

    if answer < temp_max:
        answer = temp_max
print(answer)

Submission status: Accepted

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

l1 = l2 = length = 0

while l2 + length < n:
  if s[l1 : l2] in s[l2:]:
    length = l2 - l1
    l2 += 1
  else:
    l1 += 1
    l2 = l1 + length + 1

print(length)

Submission status: Accepted

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

def z_algorithm_no_overlap(S_):
    N_ = len(S_)
    Z_ = [0] * N_
    L_ = R_ = 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_
            R_ -= 1
        else:
            k = i - L_
            if Z_[k] < R_ - i + 1:
                Z_[i] = Z_[k]
            else:
                L_ = i
                while R_ < N_ and S_[R_-L_] == S_[R_]:
                    R_ += 1
                Z_[i] = R_ - L_
                R_ -= 1
    for i, z in enumerate(Z_):
        if z > i:
            Z_[i] = i
    return Z_
        
# print(max(max(z_algorithm_no_overlap(S[i:])) for i in range(N-1)))
ans = 0
for i in range(N-1):
    m = max(z_algorithm_no_overlap(S[i:]))
    ans = max(ans, m)
    if ans >= (N - i) // 2:
        break
print(ans)

Submission status: Accepted

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

dp = [[None for j in range(N)] for i in range(N)]
vlen = 0
for i in range(N-1):
    for j in range(i + 1, N):
        if S[i] != S[j]:
            dp[i][j] = 0
        elif i - 1 >= 0 and j - 1 >= 0:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = 1
        if i + dp[i][j] <= j:
            vlen = max(vlen, dp[i][j])
print(vlen)

Submission status: Accepted

Solution code:
n,s=open(0)
a=i=j=0
while s[j:]:f=s[i:j]in s[j:];a=max(a,j*f-i);j+=f;i+=f^1
print(a)

Submission status: Accepted

Solution code:

n = int(input())
ab = str(input())

ans = set([0])
lenab = len(ab)

for h in range(lenab):
    abc = ab[h:]
    lenabc = len(abc)
    i = 1; j = 0
    A = [0]*lenabc
    A[0] = lenabc
    while i < lenabc:
        while i+j < lenabc and abc[j] == abc[i+j] and j < i:
            j += 1
        if j == 0:
            i += 1
        else:
            A[i] = j
            ans.add(j)
            k = 1
            while lenabc - i > k < j - A[k] and j < i - k :
                A[i + k] = A[k]
                k += 1
            i += k;
            j -= k

print(max(ans))

Submission status: Accepted

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

    def rolling_hash(s, mod, base = 37):
        l = len(s)
        h = [0]*(l + 1)
        v = 0
        for i in range(l):
            h[i+1] = v = (v * base + ord(s[i])) % mod
        pw = [1]*(l + 1)
        v = 1
        for i in range(l):
            pw[i+1] = v = v * base % mod
        return h, pw

    def chk(S, mod, D = [0]*N):
        h, pw = rolling_hash(S, mod)
        left = 0; right = N//2+1
        while left+1 < right:
            l = mid = (left + right) >> 1
            p = pw[l]
            for i in range(min(l, N-2*l+1)):
                D[i] = (h[l+i] - h[i]*p) % mod
            s = set()
            ok = 0
            for i in range(l, N-l+1):
                s.add(D[i-l])
                D[i] = v = (h[l+i] - h[i]*p) % mod
                if v in s:
                    ok = 1
                    break
            if ok:
                left = mid
            else:
                right = mid
        return left

    print(chk(S, 10**9 + 9))
solve()

Submission status: Accepted

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

    def rolling_hash(s, mod, base = 37):
        l = len(s)
        h = [0]*(l + 1)
        v = 0
        for i in range(l):
            h[i+1] = v = (v * base + ord(s[i])) % mod
        pw = [1]*(l + 1)
        v = 1
        for i in range(l):
            pw[i+1] = v = v * base % mod
        return h, pw

    def chk(S, mod, D = [0]*N):
        h, pw = rolling_hash(S, mod)
        left = 0; right = N//2+1
        while left+1 < right:
            l = mid = (left + right) >> 1
            p = pw[l]
            for i in range(min(l, N-2*l+1)):
                D[i] = (h[l+i] - h[i]*p) % mod
            s = set()
            ok = 0
            for i in range(l, N-l+1):
                s.add(D[i-l])
                D[i] = v = (h[l+i] - h[i]*p) % mod
                if v in s:
                    ok = 1
                    break
            if ok:
                left = mid
            else:
                right = mid
        return left

    res1 = chk(S, 10**9 + 9)
    res2 = chk(S, 10**9 + 7)
    print(min(res1, res2))
solve()

Submission status: Accepted

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

    def rolling_hash(s, mod, base = 37):
        l = len(s)
        h = [0]*(l + 1)
        v = 0
        for i in range(l):
            h[i+1] = v = (v * base + ord(s[i])) % mod
        pw = [1]*(l + 1)
        v = 1
        for i in range(l):
            pw[i+1] = v = v * base % mod
        return h, pw

    def chk(S, mod, D = [0]*N):
        h, pw = rolling_hash(S, mod)
        left = 0; right = N//2+1
        while left+1 < right:
            l = mid = (left + right) >> 1
            p = pw[l]
            for i in range(min(l, N-2*l+1)):
                D[i] = (h[l+i] - h[i]*p) % mod
            s = set()
            ok = 0
            for i in range(l, N-l+1):
                s.add(D[i-l])
                D[i] = v = (h[l+i] - h[i]*p) % mod
                if v in s:
                    ok = 1
                    break
            if ok:
                left = mid
            else:
                right = mid
        return left

    res1 = chk(S, 10**9 + 9)
    res2 = chk(S, 10**9 + 7)
    res3 = chk(S, 1004535809)
    print(min(res1, res2, res3))
solve()

Submission status: Accepted

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

ans = 0
left, right = 0, 1

while right < N:
    s = S[left:right]
    if s in S[right:]:
        right += 1
        ans = max(ans, len(s))
    else:
        left += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

N = int(input())
S = np.array([ord(x) for x in input().rstrip()],dtype=np.int64)

MOD = 10**9 + 7
base = 1234

def cumprod(arr):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr,Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    return arr.ravel()[:L]

x = np.full(N,base,np.int64); x[0] = 1
power = cumprod(x)
x = np.full(N,pow(base,MOD-2,MOD),np.int64); x[0] = 1
power_inv = cumprod(x)

H = S * power % MOD
Hcum = H.cumsum() % MOD

def test(n):
    x = (Hcum[n-1:N] - Hcum[:N-n+1] + H[:N-n+1]) % MOD
    x *= power_inv[:N-n+1]
    x %= MOD
    ind = np.lexsort((np.arange(N-n+1),x))
    x = x[ind]
    is_left_end = np.zeros(N-n+1,np.bool)
    is_left_end[1:] = (x[1:] != x[:-1])
    is_left_end[0] = 1
    is_right_end = np.zeros(N-n+1,np.bool)
    is_right_end[:-1] = (x[:-1] != x[1:])
    is_right_end[-1] = 1
    gap = ind[is_right_end] - ind[is_left_end]
    return gap.max() >= n

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

answer = left
print(answer)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
w=[[0]*n for i in range(n)]
ans=chk=0
for i in range(n-1,-1,-1):
    for j in range(n-1,-1,-1):
        if s[i]==s[j]:
            if i==n-1 or j==n-1:
                w[i][j]=1
            else:
                w[i][j]=w[i+1][j+1]+1
for i in range(1,n):
    for j in range(i):
        #ans=max(ans,w[i][j])
        ans=max(ans,w[i][j]-[0,w[i][j]-(i-j-w[i][j]+1)][j+w[i][j]>=i+1])
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
 
def main():
    n = int(input())
    s = input()
    high = n//2
    low = 1
    ans = 0

    while low <= high:
        t = set()
        i = (high+low)//2
        for j in range(n-i*2+1):
            t.add(s[j:i+j])
            if s[i+j:j+2*i] in t:
                if ans < i:
                    ans = i
                    low = i+1
                    break
        if ans < i:
            high = i-1
    print(ans)

if __name__ == '__main__':
    main()