Kimariji Key Keeper

2 secs 1024 MB

解法1：set と隣接する文字列の LCP

文字列 $s,t$ の最長共通接頭辞の長さを $\operatorname{LCP}(s,t)$ とします。

文字列 $s$ の決まり字の長さは、ほかの文字列との LCP の最大値に $1$ を加えたものです。つまり、

A_s=1+\max_{t\in T,\ t\neq s}\operatorname{LCP}(s,t)

となります。

各文字列の最後には 0 が付いているため、ある文字列が別の文字列の接頭辞になることはありません。したがって、この値が $|s|$ を超えることはありません。

ただし、この方針では文字列長の総和を $M=\sum_{i=1}^{Q}|S_i|$ とすると、全体の計算量は $O(M^2)$ となり、間に合いません。計算量の削減を考える必要があります。

実は、文字列を辞書順に並べたとき、文字列 $s$ との LCP が最大になる文字列は、 $s$ の直前または直後に存在します。

実際、 $s$ と長さ $k$ の接頭辞が一致する文字列は、辞書順で連続して並びます。そのような文字列が存在するなら、 $s$ の直前または直後の少なくとも一方も同じ接頭辞をもちます。

したがって、 $s$ の直前の文字列を $l$ 、直後の文字列を $r$ とすると、存在しない文字列との LCP を $0$ として、

A_s=1+\max(\operatorname{LCP}(l,s),\operatorname{LCP}(s,r))

と求められます。

現在の文字列を set で辞書順に管理します。

新しい文字列 $s$ を追加し、その直前を $l$ 、直後を $r$ とします。追加前には $l$ と $r$ が隣接していましたが、追加後には $l,s,r$ の順に並びます。

このとき、隣接関係が変化するのは $l,s,r$ だけです。そのため、決まり字の長さが変化する可能性がある文字列もこの $3$ つだけです。

よって、追加前の $l,r$ の決まり字の長さを総和から引き、 $s$ を追加した後の $l,s,r$ の決まり字の長さを加えれば、答えを更新できます。

隣接する文字列間の LCP も管理しておけば、新しく計算する必要があるのは $\operatorname{LCP}(l,s)$ と $\operatorname{LCP}(s,r)$ だけです。

set への挿入には $O(\log Q)$ 回の文字列比較が必要であるため、文字列長の総和を $M=\sum_{i=1}^{Q}|S_i|$ とすると、全体の計算量は $O(M\log Q)$ です。

文字列を Trie 木に追加していくことを考えます。

Trie 木の各頂点 $v$ について、 $cnt_v$ を「頂点 $v$ が表す文字列を接頭辞にもつ、現在の集合 $T$ 内の文字列数」とします。

文字列 $s$ の長さ $k$ の接頭辞に対応する頂点の $cnt$ が $1$ なら、その接頭辞によって $s$ を一意に特定できます。

$s$ の経路上では、根から進むにつれて $cnt$ は増加しないため、決まり字より短い接頭辞の $cnt$ はすべて $2$ 以上です。

したがって、文字列 $s$ の決まり字の長さは、

A_s = 1+ \left| \left\{ v \;\middle|\; v\text{ は }s\text{ の接頭辞であり、}cnt_v\geq 2 \right\} \right|

と表せます。

これをすべての文字列について足し合わせると、求める総和は

|T|+\sum_{\substack{v\neq \mathrm{root}\\ cnt_v\geq 2}} cnt_v

となります。

$cnt_v\geq2$ の頂点 $v$ は、その頂点を通る $cnt_v$ 個の文字列それぞれの決まり字の長さに $1$ ずつ寄与するためです。

新しい文字列を追加すると、その文字列に対応する経路上の各頂点で $cnt_v$ が $1$ 増えます。

頂点 $v$ の総和への寄与は、 $cnt_v\leq1$ なら $0$ 、 $cnt_v\geq2$ なら $cnt_v$ です。そのため、更新前の $cnt_v$ によって答えの変化量は次のようになります。

また、文字列数 $|T|$ が $1$ 増えるため、各クエリの最初に答えを $1$ 増やします。

その後、新しい文字列の各文字を Trie 木に追加しながら、経路上の各頂点について上記の更新を行えばよいです。

各文字列の各文字について Trie 木を一度進むため、時間計算量と空間計算量はともに、文字列長の総和を $M=\sum_{i=1}^{Q}|S_i|$ とすると $O(M)$ です。