No.469

ローリングハッシュなどで数列のハッシュを作り, クエリごとにハッシュを更新する. 更新したハッシュは連想配列にクエリの位置とともに入れておく.

適当な数から配列 $P_i$ を用意し, ハッシュを

$$H(x) = \sum_{i=0}^{N-1} x_i P_i$$

とする. これならばハッシュの更新は

$$H(x^{\prime}) = H(x) + K \sum_{i=L}^R P_i$$

となり, $P_i$ の累積和を計算しておけば $O(1)$ で更新できる.

$P_i$ をどう選ぶかが衝突回避のためには重要だが, ここでは10000以上の素数を乱択したものを採用する.