Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 285 B問題 Longest Uncommon Prefix

AtCoder ABC285 ABC B問題 200 pts

問題

問題

提出解答

問題の概要

長さ $N$ の英小文字列 $S$ が与えられる. 以降では $S$ の $x$ 文字目を $S_x$ と表す.

$i=1,2, \dots, N-1$ それぞれに対して, 以下の条件をともに満たす最大の整数 $l$ を求めよ.

$l+i \leq N$
$1 \leq k \leq l$ となる全ての整数 $k$ に対して, $S_k \neq S_{k+i}$ である.

制約

$2 \leq N \leq 5000$
$S$ は長さ $N$ の英小文字列

解法

$i$ に対して, $2$ つの非負整数 $l,l'$ が $l \leq l'$ であり, $l'$ が条件を満たすならば, $l$ も必ず条件を満たす.

よって, $k=1, \dots, N-i$ の順に $S_k \neq S_{k+i}$ であるかどうかを確認し, 次のようになる.

$S_k=S_{k+i}$ となる $k$ が存在する場合, そのような $k$ のうちの最小を $m$ としたとき, 答えは $(m-1)$ である.
$k=1,2, \dots, N-i$ 全てに対して, $S_k \neq S_{k+i}$ だった場合, 答えは $(N-i)$ である.

これを $i=1,2, \dots, N-1$ の順に行うことで, 計算量 $O(N^2)$ で全て求めることができる.