Kazun の競プロ記録

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

AtCoder Beginner Contest 287 E問題 Karuta

AtCoder ABC287 ABC E問題 500 pts

問題
提出解答
問題の概要
- 制約
解法

問題

提出解答

問題の概要

$N$ 個の英小文字からなる文字列 $S_1, \dots, S_N$ が与えられる.

2つの文字列 $A,B$ に対して, $\operatorname{lcp}(A,B)$ を以下を満たす最大の非負整数 $n$ と定義する.

$\lvert A \rvert, \lvert B \rvert \geq n$
$A,B$ の先頭 $n$ 文字が一致する.

このとき, $i=1,2, \dots, N$ に対して, 以下の $F_i$ を求めよ.

$\displaystyle F_i:=\max_{\substack{1 \leq j \leq N \\ j \neq i}} \operatorname{lcp}(S_i, S_j)$

制約

$2 \leq N \leq 5 \times 10^5$
$S_i$ は英子文字列
$\displaystyle \sum_{i=1}^N \lvert S_i \rvert \leq 5 \times 10^5$

解法

各 $i$ に対して, 非負整数 $m$ において $m \leq \lvert S_i \rvert$ とする. このとき, 以下は同値である.

$F_i \geq m$
$S_i$ の先頭 $m$ 文字を prefix とするような文字列が $S_1, \dots, S_N$ の中に ( $S_i$ を含めて) $2$ つ以上存在する.

このとき, $S_1, \dots, S_N$ のうち, prefix が $X$ であるような文字列の個数を求めるとき, Trie 木を利用することによって, $O(\lvert X \rvert)$ 時間で判定できる.

このことを利用して, 次のようにすることで正解できる.

$S_1, \dots, S_N$ から Trie 木 $T$ を生成する.
の順に以下を実行する.
- $j=1,2, \dots, \lvert S_i \rvert$ の順に以下を実行する: $S_i$ における $j$ 文字目を表している頂点 $p$ へ移動する *1. $p$ を根とする部分木において, 末端文字を担う頂点の数が $2$ 未満になるならば, $F_i=j-1$ として, 繰り返しを終了する.
- $j=\lvert S_i \rvert$ でも $F_i$ が確定しなかった場合は $F_i=\lvert S_i \rvert$ である.

この方法によって, $\displaystyle O\left( \sum_{i=1}^N \lvert S_i \rvert \right)$ 時間で $F_1, \dots, F_N$ を求めることができた.

*1: $T$ の作り方から必ず存在する.