ローリングハッシュライブラリの使い方についての自分用のメモです
ローリングハッシュ
ローリングハッシュには，2つのパラメタ base と mod がある． 文字列を base 進の数値とみなして，その mod を法とした値をハッシュ値とする．
たとえば，base = 200, mod = 10007 の場合，文字列 “abc” のハッシュ値は， $(97 * 200^2 + 98 * 200 + 99) \mod 10007 = 6976$ である． (文字 ‘a’ の ASCII コードは 97 であった)
このライブラリでは，上の計算例が示すように， 末尾文字が1の位で，先頭文字が base の s.size() - 1 乗の位としている．
安全な運用のためには，以下を守る必要がある:
- mod は，大きな素数とする．(固定しても問題無い)
- base は，ランダムに取る．
- 可能な場合，base は，1文字のハッシュ値より大きく取る． 上の例のように，1文字のハッシュ値を ASCII コードにとるならば， base は 128 以上に取る．
このライブラリでは， keymoon 氏の記事 にしたがって，mod = $2^{61} - 1$ にとっている． この mod を使うと，積が高速に計算できる．
使用法
以下，u64 は unsigned long long のこととする．
ハッシュ値の計算は，次の段取りによる:
- まず，RollingHash オブジェクト
rhを作成する． - 文字列
sおよびその部分文字列についてハッシュ値を計算したいとして，hs = rh.hashes(s);によって，ハッシュテーブルhsを作成する．hsは，長さがs.size() + 1のvector<u64>オブジェクトである． - ハッシュ値は次の通り:
sの位置iから始まる長さkの部分文字列のハッシュ値:rh.get(hs, i, k)- ただし，
sの先頭 k 文字からなる部分文字列のハッシュ値は，hs[k]でも求められる． - したがって，
sのハッシュ値は，hs.back()でも求められる．
オブジェクトの生成
通常は，次のようにする．
RollingHash rh;
これは，string を対象としたものになり，mod は $2^{61} - 1$ である． base は，1000 以上 $2^{59}$ 未満の範囲でランダムに選択される．
base を指定する場合には，次のようにする．
RollingHash rh(base);
次のコードは，base をランダム選択にするが， 選択範囲が min_base 以上 $2^{60}$ 未満になる．
RollingHash rh(0, min_base);
ハッシュテーブルの生成
ハッシュを計算する前に，ハッシュテーブルを生成する必要がある． 文字列 s に対するハッシュテーブルは，次のように生成できる:
string s = "Hello, world.";
vector<u64> hs = rh.hashes(s);
hs には，vector<u64> 型で，サイズ s.size() + 1 のベクトルが設定される．
hs の i 番目の要素 hs[i] は，sの先頭から i 文字の部分文字列
s.substr(0, i) のハッシュ値である．
特に，s のハッシュ値は hs.back() である．
ハッシュ値の計算
s の部分文字列のハッシュ値は，get メソッドで取得できる． 位置 start から始まる長さ len の部分文字列を取得するコードは，次の通り．
u64 h = rh.get(hs, start, len);
連結文字列のハッシュ値
文字列 s1 のハッシュ値が h1 で，文字列 s2 のハッシュ値が h2 のとき， s1 と s2 を連結した文字列 s1 + s2 のハッシュ値 h は，次のように計算できる:
u64 h = rh.hash_concat(h1, h2, s2.size());
一般のベクトルに対するハッシュ
文字列に限らず，ベクトル vector<T> に対してもハッシュを計算できる
(正確にはベクトルでなくても，operator [] が定義されていれば良い)．
この場合，T の各要素に対するハッシュ値が計算できる必要があるので，
それを実行する関数 conv を渡して RollingHashGen オブジェクトを作成する:
conv(t) の値は 0 以上 $2^{61} - 1$ 未満でなければならない．
auto rh = make_rolling_hash_gen<T>(0, min_base, conv);
T の要素に対するハッシュ値が， T から u64 へのキャストで良い場合には，次のように定義することもできる．
RollingHashGen<T, nullptr_t> rh(0, min_base);
なお，上で述べた，文字列を対象とした RollingHash 型は，
RollingHashGen<char, nullptr_t> の別名として定義されている．
mod $2^{61} - 1$ 演算
0 以上 $2^{61} - 1$ 未満の u64 型の a, b に対し， $a + b \mod (2^{61} - 1)$， $a - b \mod (2^{61} - 1)$， $a \times b \mod (2^{61} - 1)$ の値を計算することができる: ハッシュ値をセグメント木で計算する場合など， 自前で計算が必要になったときには，これらの関数が有効であろう．
RollingHash rh;
u64 a, b;
rh_add(a, b); // a + b
rh_subt(a, b); // a - b
rh_mul(a, b); // a * b
rh_prime - a; // -a
コード
keywords
keywords: rolling hash