Prefix Free Subset | CS Academy #30 (Div. 2 only)

文字列a,ab,abc,abdが与えられているとする。上図のようなtrieを描いてみよう。

簡単のため、文字列の最大の長さは考えないでみる。

K=1とすると明らかにaだけを使えばいい。

では、K=2の場合は？

K=1のときと同じようにaを使おうとすると、うまくいかない。aの子孫にあたる単語はすべてaをprefixとして含むため使えない。つまり、ab,abc,abdはすべて使えない。よってaは使わない。下図。

今度はabを使おうとすると、同様にabc,abdを使えない。これもK=2に届かない。

こうしてtrieを根から見ていくと、最終的に{abc, abd}を得る。

結局、自分を含まない先祖にあたるprefixを使ってない場合、ある単語について2通りの選択がある。

(1)その単語を使う

この場合はその子孫にあたる、その単語をprefixとして含む単語は使えない

(2)その単語を使わない

この場合はその子孫に当たる、その単語をprefixとして含む単語を使える。

(1),(2)を再帰でうまく処理する。最も長い単語の長さを二分探索で固定すれば、全体で

O(max(|S[i]|)*Σ|S[j]|)

の実行時間で間に合う。

 雑記

trieを使うのすぐに気付けなかった。ライブラリは持っておくべき。ちなみに、trieのことをprefix treeとも呼ぶらしく、解法を連想しやすいかも。