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

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

    if i==j:
        i+=1
        j+=2
print(a)

Submission status: Accepted

Solution code:
def ok(l):
    # 長さlの連続部分列で重ならずに2回以上現れるものがある
    D = {}
    for i in range(n-l+1):
        h = hash(S[i:i+l])
        try:
            if D[h] + l <= i:
                return True
        except:
            D[h] = i
    return False


n = int(input())
S = input()
# 二分探索でTrueになる最大のkを求める
l, r = 0, n+1
while r-l > 1:
    c = (l+r)//2
    if ok(c):
        l = c
    else:
        r = c
print(l)

Submission status: Accepted

Solution code:
def ok(l):
    # 長さlの連続部分列で重ならずに2回以上現れるものがある
    D = {}
    for i in range(n-l+1):
        try:
            if D[S[i:i+l]]+l <= i:
                return True
        except:
            D[S[i:i+l]] = i
    return False


n = int(input())
S = input()
# 二分探索でTrueになる最大のkを求める
l, r = 0, n+1
while r-l > 1:
    c = (l+r)//2
    if ok(c):
        l = c
    else:
        r = c
print(l)

Submission status: Accepted

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

def solve(SS):
	n = len(SS)
	Z = [0] * n
	Z[0] = n
	i, j = 1, 0
	while i < n:
		while (i + j < n) and (SS[j] == SS[i + j]):
			j += 1
		Z[i] = j
		if j == 0:
			i += 1
			continue
		else:
			k = 1
			while (i + k < n) and (k + Z[k] < j):
				Z[i + k] = Z[k]
				k += 1
			i += k
			j -= k

	out = 0
	for i in range(n):
		tmp = min(Z[i], i)
		out = max(out, tmp)
	return out

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

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

def judge(x):
    d = defaultdict(int)
    
    for i in range(N-x+1):
        k = hash(S[i:i+x])
        
        if k not in d:
            d[k] = i
        else:
            if i-d[k]>=x:
                return True
    
    return False

def binary_search():
    l, r = 0, N
    
    while l<=r:
        m = (l+r)//2
        
        if judge(m):
            l = m+1
        else:
            r = m-1
    
    return r

N = int(input())
S = input()[:-1]

print(binary_search())

Submission status: Accepted

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

def f(m):
    se = set()
    arr = [None]*N
    for i in range(0,N-m+1):
        if i >= m:
            se.add(arr[i-m])
        arr[i] = S[i:i+m]
        if arr[i] in se:
            return True
    return False

l = 0
r = N//2+1
while (r-l)>1:
    mid = (r+l)//2
    if f(mid):
        l = mid
    else:
        r = mid
print(l)

Submission status: Accepted

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

def f(m):
    se = set()
    arr = [None]*N
    for i in range(0,N-m+1):
        if i >= m:
            se.add(arr[i-m])
        arr[i] = hash(S[i:i+m])
        if arr[i] in se:
            return True
    return False

l = 0
r = N//2+1
while (r-l)>1:
    mid = (r+l)//2
    if f(mid):
        l = mid
    else:
        r = mid
print(l)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
from collections import deque

def f(m):
    se = set()
    q = deque()
    for i in range(0,N-m+1):
        h = hash(S[i:i+m])
        q.append(h)
        if h in se:
            return True
        if len(q) >= m:
            se.add(q.popleft())
    return False

l = 0
r = N//2+1
while (r-l)>1:
    mid = (r+l)//2
    if f(mid):
        l = mid
    else:
        r = mid
print(l)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
dp = [[0]*N for _ in range(N)]
ans = 0
for i in range(N-1,0,-1):
    for j in range(i-1,-1,-1):
        if S[i] == S[j]:
            if i < N-1 and j < i-1:
                dp[i][j] = min(dp[i+1][j+1]+1, i-j)
            else:
                dp[i][j] = 1
        ans = max(ans, dp[i][j])
print(ans)

Submission status: Accepted

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

mod = 10**20 + 7
base = 12345

def ok(l):
    array = {}
    rolling_hash = 0
    for i in range(n):
        rolling_hash *= base
        rolling_hash += ord(s[i])
        if i - l >= 0:
            rolling_hash -= ord(s[i-l]) * pow(base, l, mod)
        rolling_hash %= mod
        if i >= l-1:
            if rolling_hash in array.keys():
                array[rolling_hash].append(i)
            else:
                array[rolling_hash] = [i]
    for check in array.values():
        if max(check) - min(check) >= l:
            return True
    return False

top = n
bottom = 0

while top - bottom > 1:
    mid = (top + bottom)//2
    if ok(mid):
        bottom = mid
    else:
        top = mid
print(bottom)

Submission status: Accepted

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

N = int(input())
S = input()
ans = 0
for i in range(N):
    s = S[i:]
    ans = max(ans, zarg(N-i, s))
print(ans)

Submission status: Accepted

Solution code:
def z_algorithm(S):
    l=len(S)
    A=[0]*n
    i=1;j=0
    while i<l:
        while(i+j<l and S[j]==S[i+j]):
            j+=1
        A[i]=j
        if j==0:
            i+=1
            continue
        k=1
        while i+k<l and k+A[k]<j:
            A[i+k]=A[k]
            k+=1
        i+=k
        j-=k
    return A
n=int(input())
s=input()
ans=0
for i in range(n-1):
    a=z_algorithm(s[i:])
    for j in range(len(a)):
        if(a[j]<=j):
            ans=max(ans,a[j])
print(ans)

Submission status: Accepted

Solution code:
#ABC141-E Who Says a Pun?
"""
最長共通部分文字列を求める問題。
最長共通接頭辞(z-algorithm)を用いて、O(N**2)で求まる。
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

def Z_algorithm(s):
    N = len(s)
    Z_alg = [0]*N
    Z_alg[0] = N
    i = 1
    j = 0
    res = 0 #文字列非重複の場合の最大共通部分
    while i < N:
        while i+j < N and s[j] == s[i+j]:
            j += 1
        if i+1 > j:
            res = max(res,j)
        else:
            res = max(res,i)
        Z_alg[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k + Z_alg[k]<j:
            Z_alg[i+k] = Z_alg[k]
            k += 1
        i += k
        j -= k
    return res
n = int(readline())
s = readline().rstrip().decode('utf-8')
ans = 0
i = 0
while True:
    ans = max(ans,Z_algorithm(s))
    if len(s)<=2:
        break
    s = s[1:]
    i += 1

print(ans)

Submission status: Accepted

Solution code:
# Zalgo
# https://drken1215.hatenablog.com/entry/2019/09/16/014600


def z_algo(s: str) -> list:
    """LCP(0,i)のlist"""
    N = len(s)
    ret = [-1] * N
    ret[0] = N
    i, j = 1, 0
    while i < N:
        while i + j < N and s[j] == s[i + j]:
            j += 1
        ret[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < N and k + ret[k] < j:
            ret[i + k] = ret[k]
            k += 1
        i += k
        j -= k
    return ret


def main():
    N = int(input())
    s = input()

    ans = 0

    t = ''
    for c in reversed(s):
        t = c + t
        lcp = z_algo(t)
        for d, x in enumerate(lcp):
            ans = max(ans, min(x, d))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# 解説

def main():
    N = int(input())
    s = input()

    dp = [[0] * (N + 1) for _ in range(N + 1)]
    ans = 0
    for i in reversed(range(N)):
        for j in reversed(range(i, N)):
            if s[i] == s[j]:
                dp[i][j] = min(dp[i + 1][j + 1] + 1, j - i)
                ans = max(ans, dp[i][j])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# 解説

def main():
    N = int(input())
    s = input()

    dp = [[0] * N for _ in range(N)]
    ans = 0
    for i in reversed(range(N)):
        for j in reversed(range(i, N)):
            if s[i] == s[j]:
                if i + 1 < N and j + 1 < N:
                    dp[i][j] = min(dp[i + 1][j + 1] + 1, j - i)
                    ans = max(ans, dp[i][j])
                else:
                    dp[i][j] = 1
            else:
                dp[i][j] = 0
    print(ans)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Accepted

Solution code:
N = int(input())
S = input()
lb, ub = 0, N
while ub - lb > 1:
    m = (lb + ub) // 2
    ok = False
    dic = {}
    for i in range(N-m+1):
        s = S[i:i+m]
        if s not in dic:
            dic[s] = i
        elif dic[s] + m <= i:
            ok = True
            break
    if ok:
        lb = m
    else:
        ub = m
print(lb)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
from decimal import Decimal
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

def z_algo(S):
    N = len(S)
    A = [0] * N
    i = 1; j = 0
    A[0] = l = N
    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 = inp()
s = input()
res = 0
for i in range(n-1):
    a = z_algo(s[i:])
    ln = n-i
    for j,x in enumerate(a):
        tmp = min(j,x)
        res = max(res, tmp)
print(res)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
dp = [[0]*(n+1) for _ in range(n+1)]
res = 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
        res = max(res,min(dp[i][j],j-i))
print(res)

Submission status: Accepted

Solution code:
from collections import *
from heapq import *
import sys

sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]
dij = [(1, 0), (-1, 0), (0, 1), (0, -1)]

def LcpByZ(target):
    len_t = len(target)
    lcp = [-1] * len_t
    top = 1  # 右の箱において、左の箱の0に対応する点
    left = 0  # 左の箱の左端(本当はここでので宣言は不要だけど理解の為)
    right = 0  # 左の箱の右端
    lcp[0] = 0
    while top < len_t:
        # 箱を右に広げていく
        while top + right < len_t and target[right] == target[top + right]:
            right += 1
        # 右の箱左端のlcpを記録
        lcp[top] = right
        left = 1
        # 箱の幅が0だったらtopを動かして、このターン終了
        if right == 0:
            top += 1
            continue
        # lcpを記録しながら箱を左に縮めていく（最初の条件重要）
        while left + lcp[left] < right and left < right:
            lcp[top + left] = lcp[left]
            left += 1
        # topを右の箱の左端にして、左の箱を0まで戻す
        top += left
        right -= left
        left = 0  # これも本当は不要
    return lcp

def main():
    n=II()
    s=SI()
    ans=0
    for i in range(n):
        lcp=LcpByZ(s[i:])
        for j in range(len(lcp)):
            if lcp[j]>ans and j>=lcp[j]:ans=lcp[j]
    print(ans)

main()

Submission status: Accepted

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

def condition(num):
    data=[]
    for i in range(0,N-num+1):
        data.append((S[i:i+num],i))

    data.sort()
    if len(data)==1:
        return False

    small=data[0][1]
    large=data[0][1]
    for i in range(0,len(data)-1):
        if data[i][0]==data[i+1][0]:
            large=data[i+1][1]
        else:
            if large-small>=num:
                return True
            else:
                small=data[i+1][1]
                large=data[i+1][1]

    if large-small>=num:
        return True

    return False

start=0
end=N
while end-start>1:
    test=(end+start)//2
    if condition(test):
        start=test
    else:
        end=test

if condition(end):
    print(end)
else:
    print(start)

Submission status: Accepted

Solution code:
from collections import deque

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

def exists(length):
    que = deque()
    V = set()
    for left in range(N - length + 1):
        if left > length - 1:
            V.add(que.popleft())
        T = S[left: left + length]
        if T in V:
            return True
        que.append(T)
    return False

ok = 0
ng = N
while ng - ok > 1:
    mid = (ok + ng) // 2

    if exists(mid):
        ok = mid
    else:
        ng = mid

print(ok)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


class RollingHash:
    def __init__(self, s: str, base=1007, mod=10 ** 9 + 7):
        self.mod = mod
        length = len(s)
        self.pw = [1] * (length + 1)
        self.h = [0] * (length + 1)
        
        v = 0
        for i in range(length):
            self.h[i + 1] = v = (v * base + ord(s[i])) % mod
        v = 1
        for i in range(length):
            self.pw[i + 1] = v = v * base % mod
    
    def query(self, left, right):
        return (self.h[right] - self.h[left] * self.pw[right - left]) % self.mod


def solve():
    N = int(rl())
    S = input()
    
    rh = RollingHash(S)
    
    def check(t):
        dist = dict()
        for i in range(N - t + 1):
            h = rh.query(i, i + t)
            if h in dist:
                if t <= i - dist[h]:
                    return True
            else:
                dist[h] = i
        return False
    
    ok, ng = 0, N // 2 + 1
    while 1 < ng - ok:
        mid = (ok + ng) // 2
        if check(mid):
            ok = mid
        else:
            ng = mid
    print(ok)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
alphabet={moji:alphabetlist.index(moji) for moji in alphabetlist}

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

def condition(num):
    if num==0:
        return True

    data=[]
    x=0
    for i in range(num):
        x+=alphabet[S[i]]*26**i

    data.append((x,0))

    for i in range(0,N-num+1):
        if i==0:
            continue
        else:
            x=x//26+alphabet[S[i+num-1]]*26**(num-1)
            data.append((x,i))

    data.sort()
    min=data[0][1]
    max=data[0][1]
    for i in range(0,len(data)-1):
        if data[i][0]==data[i+1][0]:
            max=data[i+1][1]
        else:
            if max-min>=num:
                return True
            min=data[i+1][1]
            max=data[i+1][1]

    if max-min>=num:
        return True

    return False

start=0
end=N
while end-start>1:
    test=(end+start)//2
    if condition(test):
        start=test
    else:
        end=test

if condition(end):
    print(end)
else:
    print(start)

Submission status: Accepted

Solution code:
n = int(input())
s = input() #sys.stdin.readlineは最後が改行

right=0
ans = 0
for left in range(n):
    while right<n:
        word = s[left:right+1]
        if word in s[right+1:]:
            ans = max(ans, len(word))
        else:
            break
        right+=1

print(ans)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq


def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def main():
    r = solve()
    print(r)

def solve():
    N = iip(False)
    S = input()

    dp = [[0]*(N+1) for _ in range(N+1)]
    for i in reversed(range(N)):
        for j in reversed(range(N)):
            if S[j] == S[i]:
                dp[i][j] = dp[i+1][j+1]+1

    ans = 0
    for i in range(N):
        for j in range(N):
            if i >= j:
                continue

            cnt = dp[i][j]
            if cnt+i > j:
                continue
            ans = max(ans, cnt)

    return ans


#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq


def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def main():
    r = solve()
    print(r)

def z_algo(s):
    n = len(s)
    LCP = [0]*n
    c = 0 #最も末尾側までLCPを求めたindex
    for i in range(1, n): # i番目からのLCPが以前計算したcからのLCPに含まれている場合
        if i+LCP[i-c] < c+LCP[c]:
            LCP[i] = LCP[i-c]
        else:
            j = max(0, c+LCP[c]-i)
            while i+j < n and s[j] == s[i+j]:
                j += 1
            LCP[i] = j
            c = i
    LCP[0] = n
    return LCP


def solve():
    N = iip(False)
    S = input()

    ans = 0
    for i in range(N):
        LCP = z_algo(S[i:])
        #print(LCP)

        for j, k in enumerate(LCP):
            left = k
            if left > j:
                #print("ng", i, k, j)
                continue
            else:
                #print("ok", i, k)
                ans = max(ans, k)

    return ans


#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Submission status: Accepted

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

MOD = 10 ** 18 + 7
A = 123456

def ok(l):
    rolling_hash = 0
    strings = {}
    for i in range(n):
        rolling_hash *= A
        rolling_hash += ord(s[i])
        if i - l >= 0: rolling_hash -= ord(s[i-l]) * pow(A, l, MOD)
        rolling_hash %= MOD
        if i < l-1:continue
        if rolling_hash not in strings:
            strings[rolling_hash] = []
        strings[rolling_hash].append(i)

    for string in strings:
        if strings[string][-1] - strings[string][0] >= l:
            return True
    return False
    

bottom, top = 0, n

while top - bottom > 1:
    mid = (top + bottom) // 2
    if ok(mid): bottom = mid
    else: top = mid

print(bottom)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq


def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def main():
    r = solve()
    print(r)

def solve():
    N = iip(False)
    S = input()
    S = [ord(i) for i in S]

    ln = len(S)

    def same(l):
        h1 = 0
        h2 = 0
        b1 = 26
        b2 = 27
        k1 = 1
        k2 = 1
        bl1 = power(b1, l, mod2)
        bl2 = power(b2, l, mod2)
        for i in range(l):  # 最初の検索対象のhashを作る
            ht = S[l - 1 - i]
            h1 += ht * k1
            h2 += ht * k2
            k1 *= b1
            k2 *= b2

            h1 %= mod2
            h2 %= mod2
            k1 %= mod2
            k2 %= mod2

        hl1 = [h1]
        hl2 = [h2]
        for i in range(l, ln):
            h1 = h1 * b1 + S[i] - S[i-l]* bl1
            h2 = h2 * b2 + S[i] - S[i-l]* bl2
            h1 %= mod2
            h2 %= mod2
            hl1.append(h1)
            hl2.append(h2)

        #print(hl1)
        lnh = len(hl1)
        for i in range(lnh):
            for j in range(lnh):
                if i-j < l:
                    continue
                if hl1[i] == hl1[j] and hl2[i] == hl2[j]:
                    return True


        return False


    mn = 0
    mx = ln // 2+1
    while mx - mn > 1:
        l = (mx+mn) // 2

        is_same = same(l)

        if is_same:
            mn = l
        else:
            mx = l

    #print(mn, mx)
    return mn


#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Submission status: Accepted

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

A = 1234567
MOD = 10000000000000007

def ok(length):
    rolling_hash = 0
    head = pow(A, length, MOD)
    occurence = {}
    for i in range(n):
        rolling_hash = (rolling_hash * A + ord(s[i])) % MOD
        if i - length >= 0:
            rolling_hash = (rolling_hash - head * ord(s[i-length])) % MOD
        if rolling_hash not in occurence:
            occurence[rolling_hash] = []
        occurence[rolling_hash].append(i)

    for key in occurence:
        if occurence[key][-1] - occurence[key][0] >= length:
            return True
    return False

bottom, top = 0, n

while top - bottom > 1:
    mid = (top + bottom) // 2
    if ok(mid):bottom = mid
    else: top = mid

print(bottom)

Submission status: Accepted

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

def Z_algorithm(s):
  N=len(s)
  Z_alg=[0]*N
  Z_alg[0]=N
  i=1
  j=0
  while i<N:
    while i+j<N and s[j]==s[i+j]:
      j+=1
    Z_alg[i]=j
    if j==0:
      i+=1
      continue
    k=1
    while i+k<N and k+Z_alg[k]<j:
      Z_alg[i+k]=Z_alg[k]
      k+=1
    i+=k
    j-=k
  return Z_alg

ans=0
for i in range(n):
  S=s[i:n]
  z=Z_algorithm(S)
  for j in range(len(z)):
    if z[j]<=j:
      if ans<z[j]:
        ans=z[j]
print(ans)

Submission status: Accepted

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

def Z_algorithm(s):
  N=len(s)
  Z_alg=[0]*N
  Z_alg[0]=N
  i=1
  j=0
  while i<N:
    while i+j<N and s[j]==s[i+j]:
      j+=1
    Z_alg[i]=j
    if j==0:
      i+=1
      continue
    k=1
    while i+k<N and k+Z_alg[k]<j:
      Z_alg[i+k]=Z_alg[k]
      k+=1
    i+=k
    j-=k
  return Z_alg

ans=[0]
for i in range(n):
  S=s[i:n]
  z=Z_algorithm(S)
  for j in range(len(z)):
    if z[j]<=j:
      ans.append(z[j])
print(max(ans))

Submission status: Accepted

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

def search(x):
    d = set()
    for i in range(n-2*x+1):
        d.add(s[i:i+x])
        if s[i+x:i+2*x] in d:
            return True
    return False

l = 0
r = n//2+1
while r > l+1:
    mid = (r+l)//2
    if search(mid):
        l = mid
    else:
        r = mid
print(l)

Submission status: Accepted

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

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

print(count)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    s = input()
    dp = [[0]*(n+1) for i in range(n+1)]
    ans = 0
    for i in range(n-1)[::-1]:
        for j in range(i+1,n)[::-1]:
            if s[i] == s[j]:
                dp[i][j] = max(dp[i][j], dp[i+1][j+1] + 1)
                ans = max(ans, min(dp[i][j],j-i))
    print(ans)
main()