列のハッシュ(ローリングハッシュ)

まえがき

この記事は投稿者(NokonoKotlin)の個人サイトの記事から Qiita 用に移植 & 加筆したものです。 (この文言は記事が剽窃でないことを周知するためのものであり、個人サイトの宣伝ではないことをあらかじめご了承ください。)

Roloing Hash

ローリングハッシュとは、列 $S$ をハッシュ化 (数値として表す) することで、列の一致判定を $O(1)$ 時間で処理するためのアルゴリズムです。

適当なパラメータ $(b,M)$ を用いて、長さ $N$ の列 $S$ のハッシュ $H_S$ を以下で定義します。

• $H_S := \sum_{0\leq i \leq N-1} S_i×b^{N-1-i} \mod M = S_0×b^{N-1} + S_1×b^{N-2} + ... + S_{N-1}×b^0 \mod M $
• ($H_S$ は $S_i$ と $b^{i}$ の添字の和の畳み込みの第 $N-1$ 項です。)

ただし、$S_i$ が $0$ にならないように注意してください ($0$ の要素が存在する場合、全体に適当な値を足した値をハッシュ計算に用いてください)。

列 $S,T$ のハッシュ値 $H_S,H_T$ について、以下が成り立ちます。

• $S = T \rightarrow H_S = H_T$
• $S \neq T $ でも $H_S \neq H_T$ とは限らない (ハッシュの衝突)

ハッシュの衝突さえ起こらなければ、列 $S,T$ をそれぞれのハッシュ $H_S,H_T$ と対応づけることができ、ハッシュで列の一致判定や辞書順比較を行うことができます。

ハッシュの衝突確率を小さくする

$\mathrm{mod}$ をとる値 $M$ を大きくすることでハッシュの衝突確率をより小さくできます。また $M$ は素数が良いです。

$\mathrm{mod} \space M$ における積の計算を簡単にするため、整数型の上限が $M^2$ 以上であるものとします。C++ では $M$ は int (32bit 整数) に収まる素数とします ($M^2$ が long long に収まる範囲)。

しかしハッシュが int の範囲内 ($10^9$ ぐらい) なのは心もとないです。そこで列 $S$ のハッシュを、二種類のパラメータの組 $(b_1,M_1) , (b_2 , M_2)$ に対して計算し、それを ${H_1}(S) ,{H_2}(S) $ とします。これら二つのハッシュから、以下の新しいハッシュを定義します。

• $H_S = {H_1}(S)\cdot M_2 + {H_2}(S) $

このハッシュは整数の組 $({H_1}(S) , {H_2}(S))$ と一対一対応しています。よって、${H_1}(S)$ と ${H_2}(S)$ のどちらかでハッシュの衝突が発生しても、$H_S$ では衝突は発生しません (両方同時に発生してしまうとダメです)。

注意

ハッシュのパラメータ $(b,m)$ がわかっていると、意図的にハッシュを衝突させるケースを作ることができます。Codeforces などのハックで落とされてしまう可能性があるので、パラメータは実行時に決定される様にするのが好ましいです。

実装

$S$ の先頭 $x$ 個の要素からなる接頭辞のハッシュを $p_x$ とします。配列 $p$ は以下のように計算できます。

• $p_{0} = 0$
• $p_{i+1} = p_i\times b + S_i\mod{M}$

この配列 $p$ を用いて、$S$ の区間 $[l,r)$ の連続部分列のハッシュを以下で計算できます ($l,r$ は 0-index )。

• $p_r-p_l\cdot b^{r-l} \mod{M}$ (負にならないように注意)

あらかじめ $p$ と $\mathrm{bpow}[x] := b^x$ を計算しておくことで、区間のハッシュを $O(1)$ 時間で計算することができます。

また列 $S$ , $T$ に関して、$S+T$ ($S$ , $T$ をこの順に連結した列) のハッシュ値は $H_S\cdot b^{|T|}+H_T$ として計算できます。

列の辞書順比較

列 $S$ と $T$ の辞書順での大小判定は、$S,T$ の共通の接頭辞の最大の長さが分かれば、その次の index の要素の大小で判定できます。以下の二分探索を行います。

• $S$ , $T$ それぞれの先頭 $m$ 文字 (接頭辞) のハッシュ $HS_m$ , $HT_m$ を計算する
• $HS_m = HT_m$ ならば $m$ を右側領域に移動し、
• $HS_m ≠ HT_m$ ならば $m$ を左側領域に移動する。
• 最終的に $m$ 付近を調べると $HS_i = HT_i$ となる最大の $i$ がわかる。
• $S , T$ の $i+1$ 文字目の大小関係が $S , T$ の大小関係である。

$S,T$ のハッシュを構築すると、ナイーブな辞書順比較の計算量 $O(\mathrm{min}(|S|,|T|))$ と同じ計算量になってしまいますが、$S,T$ が共に何らかの列 $A$ の連続部分列の場合、$S,T$ の接頭辞ハッシュの計算が $O(1)$ 時間の処理なので、辞書順比較を $O(\log{\mathrm{min}(|S|,|T|)})$ 時間で行うことができます。

Suffix Array

列 $S$ の接尾辞を辞書順に並べたものを $S$ の Suffix Array と言います。ただし、接尾辞を明示的に保持すると空間計算量が $O(|S|^2)$ になってしまうので、Suffix Array は接尾辞の開始位置の index を、対応する接尾辞の辞書順で並べたものを指します。

接尾辞は $S$ の連続部分列なので、接尾辞同士の辞書順比較は先の議論によって $O(\log{|S|})$ 時間で処理することができます。ソートの計算量と合わせて Suffix Array を $O(|S|\log^{2}{|S|})$ 時間で計算することができます。