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) 回しか移動しない）。

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

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