読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Educational Codeforces Round 16: F - String Set Queries

問題ページ

問題概要

  1. 文字列 s をリストに追加
  2. 文字列 s をリストから削除
  3. 文字列 s の中にリスト中の文字列がいくつ存在するか数える

という 3 種類のクエリを順次処理せよ。オンラインクエリ。

解法

Aho-Corasick でオートマトンを作って数え上げればいい。動的にオートマトンを作るには以下のテクニックを使う。

Decomposable searching problem - yukicoder

原理は二進カウンタが O(n) 動くのと似たような感じだと思う(マージテクの方が近いかも。各要素は O(log n) 回しか移動しない)。

削除クエリで真面目に削除するのは面倒なので、削除された文字列で別途オートマトンを構成してその分を引く。

機械的に使えるテクニック。汎用性が高そう。