公式解説ではクエリを全て受け取ってから前処理をしていますが、オンラインで解くことができます。
問題概要
文字列が $N$ 個与えられるので、以下のクエリを $Q$ 回処理
クエリ1 : 文字列 $x$ の末尾に英小文字 $c$を加える
クエリ2 : $i=1,2,...,N$ に対して $S_{i}, S_{x}$ の最長共通接頭辞の長さを求め、それらの総和を答える。
クエリを先に受け取るときの解き方(ほぼ公式解説)
文字列の頭の部分が一緒といえば Trie木 です(?)。
今回は通常の Trie木 のノードごとにそのノード $p$ を通る文字列の数 $C_{p}$を記録しています。
すると答えは $S_{x}$ の末尾を表すノードから根っこのノード間にあるノードの $C_{p}$ の和となります。
公式解説ではクエリを先に全て受け取ることで、木上の一点加算とパス上の頂点の総和の問題に帰着しています。
別解
深さ $B$ で場合わけします。
まず、Trie木 のノードごとにそのノード $p$ を通る全て文字列の index を記録した配列 $D_{p}$ を持ちます。 また、長さ $N$ の配列 $base=(base_{1},...,base_{N})$ を用意します。(初期値は0)
$base_{x}$ というのは $S_{x}$ との最長共通接頭辞の長さが $B$ 以上の全てに対して文字列 $B$ 文字目以降で一致している文字数の総和です。
ある深さ $B$ より深いノードについてはそのノードに新しく文字列 $x$ が通過する際に($D_{p}$ に $x$ を追加する前に)以下の操作をします。
- $D_{p}$ に含まれる全ての要素 $y$ に対して $base_{y}$ に1加算する。
- $base_{x}$ に $|D_{p}|+1$ を加算する。
最初の文字列を追加する際やクエリ1を処理する際は以上の操作で十分です。
クエリ2を処理する際は以下のようにします。
- まず、$ans=base_{x}$ とする。
- 文字列 $S_{x}$ の 前 $B$ 文字が通っているノード $p$ について $ans$ に$|D_{p}|$ を加算する。
なぜ、これでいいのかというと、 $base_{x}$ というのは $B$ 文字目以降で一致している文字数の総和であるため、足りないのは $B$文字目より前で一致している文字数であるからです。
計算量
最初の文字列の長さの和を $M $ とします。
まず、クエリ2については一つ当たり $O(B)$ で処理することがでるので、全体で $O(QB)$ です。
文字を追加する操作ですが、一つ当たり最悪計算量が $O(N)$ なので、一見全体で $O((M+Q)N)$ のように見えますが違います。
例えば全ての文字列が深さ $B$ のノードを通るとき、 $N\times B \leq M+Q$ を満たす必要がありますが、これは $B$ が大きくなればなるほど困難になります。
自分の考察が間違っていなければ全体で $O(\frac{(M+Q)^2}{B})$ になるはずです。
よって、 このアルゴリズム全体では計算量が $O(\frac{(M+Q)^2}{B}+QB)$ になります。
$B$ を適切な値にすることで十分高速に通ることができます。(テストケースにこの解法に強いものが存在しているのかは分かりません)
