ハッシュ化とは

• 任意サイズのデータから固定長の値を得るもの。
• 実物の代わりにハッシュを用いることで計算量の削減ができる。
• ハッシュを使って、例えば一致性判定ができる

ローリングハッシュ

ローリングハッシュは数列をハッシュ化する。

ローリングハッシュの計算方法

数列 $(x_0, \ldots, x_{n-1})$ に対して、$x_0 b^{n-1} + x_1 b^{n-2} + \cdots + x_{n-2} b + x_{n-1} \bmod p$ をハッシュ値とする。

• mod $2^{61} -1$ にして、base $b$ をランダムに取るのがよいとされている。
  • 安全で爆速なRollingHashの話 #競技プログラミング - Qiita
• ある $i$ で $x_i = 0$ だとだめ。
  • 例えば $(0, 0,0,1)$ と $(0, 1)$ のローリングハッシュが同じになってしまうため。
• 多項式を評価したものと見るとよさげ。
• 添字と指数部分を足したら $n-1$ になる（畳み込みのノリ）

ローリングハッシュでできること

• 2つの数列が一致
• 連続部分列のハッシュ値の計算
  • 前処理として、$(x_0,\ldots, x_{i-1})$ のハッシュ値 s(i) を持っておく
    • 累積和みたいなもの
    • prefix のハッシュ値
  • $(x_i, \ldots, x_{j-1})$ のハッシュ値は $s(j) - b^{j-i} s(i)$ で求まる。(mod p で計算)
    • 導出
• 2つの数列を連結させたときのハッシュ値の計算
  • 2つの数列 $x, y$ に対して、$x$ と $y$ を連結させた数列のハッシュ値は $b^{|y|} H(x) + H(y)$ である。
  • この意味でローリングハッシュはモノイドをなす (参考: モノイド)
    • つまりセグ木に乗る
    • さらに 素数 mod を考えている場合は群を成す

ローリングハッシュの利用例