実装の方針は kyopro_friends さんの解説 に従うことにします。

文字列をハッシュとして表すことを考えます。その中でも、 Rolling Hash （ローリングハッシュ）というものを使うと、 \(S\) の任意の連続部分列に対して、そのハッシュを高速に（前処理 \(O(|S|)\) 時間、各取得 \(O(1)\) 時間で）計算することができるため、これを使います。

Rolling Hash を使うと次の実装でこの問題を解くことができます：

• 前処理

  • 集合 \(X_H\) と、ハッシュの値をキーにとる連想配列 \(Y_H\) を用意する。
  • \(X_H\) は \(X\) に含まれる各文字列のハッシュの集合である。
  • \(Y_H\) の各要素には、そのハッシュを与える文字列が接頭辞に含まれるような \(Y\) の要素の集合が紐づけられているとする。

• 文字列 \(S\) を \(Y\) に追加するとき

  • （イメージ）\(X\) の要素のうち、 \(S\) の接頭辞になっているものがあれば、 \(S\) は \(Y\) に入らない。
  • 「\(i=1,2,\cdots, |S|\) いずれかに対し、 \(S\) の先頭 \(i\) 文字が \(X\) のハッシュの集合に含まれる」とき、何も更新する必要はない。
  • そうでないとき、 \(S\) を \(Y\) に追加する。その後、 \(i=1,2,\cdots, |S|\) それぞれについて、 \(Y_H\) に \(S\) の先頭 \(i\) 文字のハッシュを \(z_i\) としたとき、 \(Y_H[z_i]\) に \(S\) を表す値を追加する。

• 文字列 \(S\) を \(X\) に追加するとき、 \(S\) のハッシュを \(z\) とする。

  • （イメージ）\(Y\) の要素のうち、 \(S\) を接頭辞に持つものを取り除きたい。
  • \(Y_H[z]\) に含まれる各要素について、それが \(Y\) に含まれるなら、それに対応する要素を \(Y\) から取り除く。そうでなければ何もしない。その後、 \(Y_H[z]\) を空にする。

実装例 (C++)

よって、時間計算量 \(O(Q + \sum |S_i| \log (\sum |S_i|)\) 、空間計算量 \(O(Q + \sum |S_i|)\) でこの問題を解くことができます。

std::set, std::map の代わりに unordered_set や unordered_map を用いると、 \(O(Q+\sum |S_i|)\) 時間にもなります。