Rolling Hash
概要
何かの列があるときに, これのハッシュを取りたい. 列の要素は何かしらの方法で整数に変換されてるとする.
\[\langle c_1, c_2, \ldots, c_k \rangle\]ここで適当な数 \(a\) を基数として, 次の値をハッシュとする.
\[H(c) = \sum_{i=1}^k c_i a^{k-i} = c_1 a^{k-1} + c_2 a^{k-2} + \cdots + c_k a^0\]特に空列のハッシュ値は \(0\) とする. 列が等しいことを見るのにこのハッシュ値の値が等しいかをチェックする.
この値は指数を含むので, すぐに膨大になる. そこで適当に十分大きな素数 \(p\) を用意しておいて \(\bmod p\) で計算するのが普通.
\[H(c) = \sum_{i=1}^k c_i a^{k-i} \bmod p\]値の追加と削除
数列の頭または末尾に値を一つ追加または削除することは上の値を注意深く計算すれば, 再計算の必要なく高速に計算出来る. 特に末尾に一つ追加する場合が効率が良い形をしていて, 列 \(c\) のハッシュ値が \(H(c)\) とあるときに, この末尾に \(x\) を追加したもののハッシュ値は次で求まる.
\[H(c \ast x) = H(c) \times a + x \pmod p\]削除はこれの逆を取れば良い.
\[H(c) = (H(c \ast x) - x) \times a^{-1} \pmod p\]テク
ではその基数 \(a\) , mod \(p\) に何を使うかには自由度が残っている. \(p\) はハッシュの大きさを決めるものなので大きければ大きいほど良い. また値の削除がしたいなら \(a^{-1}\) が求まる必要があり, そのためには \(a\) と \(p\) が互いに素である必要がある. \(p\) を \(a\) より大きな素数にしておけば良い.
この辺の話は 
-
悪意ある人がハッシュ衝突を狙うような場面では基数をランダムに取ることで安全になる
- Codeforces の hack 対策
-
\(p\) にメルセンヌ素数を使うと MOD 演算をビット演算で高速化可能
- MOD 演算は遅い
といったことが書いてある.
参考
実装
/// Hash - RollingHash
use crate::algebra::modint::*;
use crate::mint; // IGNORE
#[derive(Debug, Clone)]
pub struct RollingHash {
data: ModInt,
base: ModInt,
baseinv: ModInt,
length: usize,
pow: ModInt,
}
impl RollingHash {
pub fn new() -> Self {
let data = mint!(0);
let base = mint!(37);
let baseinv = base.inv();
let pow = mint!(1);
Self {
data,
base,
baseinv,
length: 0,
pow,
}
}
pub fn unwrap(&self) -> i128 {
self.data.0
}
pub fn push_back(&mut self, x: i128) {
self.length += 1;
self.pow = self.pow * self.base;
self.data = self.data * self.base + mint!(x);
}
pub fn push_front(&mut self, x: i128) {
self.data = self.data + self.pow * mint!(x);
self.length += 1;
self.pow = self.pow * self.base;
}
pub fn pop_back(&mut self, x: i128) {
self.length -= 1;
self.pow = self.pow * self.baseinv;
self.data = (self.data - mint!(x)) * self.baseinv;
}
pub fn pop_front(&mut self, x: i128) {
self.length -= 1;
self.pow = self.pow * self.baseinv;
self.data = self.data - self.pow * mint!(x);
}
pub fn concat(&self, other: &Self) -> Self {
let mut r = self.clone();
r.length = self.length + other.length;
r.data = self.data * other.pow + other.data;
r.pow = self.pow * other.pow;
r
}
}
impl std::cmp::PartialEq for RollingHash {
fn eq(&self, other: &Self) -> bool {
self.length == other.length && self.data == other.data
}
}
impl std::cmp::Eq for RollingHash {}