けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

みんなのプロコン 2017 C - 検索 (400 点)

AtCoder AtCoder400点 unrated公式コン文字列制約:複数系列の長さの合計が10^5以下 prefixとsuffix N個の文字列の問題禁止文字列 Yes/No判定問題被覆最小包含・最小被覆を求める

頑張った

問題概要

$N$ 個の文字列が与えられて

そのうちの指定された $K$ 個についてについては、その prefix となっている
指定されていない $N-K$ 個については prefix にはなっていない

ような最短の文字列を求めよ。存在しない場合は -1 とせよ。

制約

$1 \le K \le N \le 10^{5}$
$N$ 個の文字列の長さの総和が $10^{5}$ 以下

考えたこと

まず $K$ 個の共通 prefix として最長のものを求めて、それを残り $N-K$ 個に対して「どこで最初にくい違うか」を求めてその index の max をとれば OK