Rolling Hash
(src/string/RollingHash.hpp)

• View this file on GitHub
• Last update: 2024-05-31 19:00:40+09:00
• Include: #include "src/string/RollingHash.hpp"

• 参考実装：tatyam

使い方

• RH rh(string s)：文字列 $s$ に対する Rolling Hash を準備する
  • $O(n)$ 時間
• u64 rh.get(ll l, ll r)：$s[l:r]$ の hash を求める
  • mod を $P := 2^{61}-1$ とし，基数 $r$ を $[0, P)$ からランダムに選ぶ
  • このとき，長さ $n$ の文字列 $s$ の hash は $(s[0] r^{n-1} + s[1] r^{n-2} + \dots + s[n-1] r^0) \bmod P$ で計算される
  • $O(1)$ 時間

使い方 (応用編)

• LCP (Longest Common Prefix) を求めたいとき：LCP の長さを二分探索すれば，$O(\log n)$ 時間 / query
• 文字列を辞書順で比較したいとき：LCP の長さを二分探索すれば，$O(\log n)$ 時間 / query

衝突確率

• $2$ つの異なる長さ $n$ 以下の文字列が衝突する確率は $\frac{n}{P}$ 以下
  • 参考資料：Schwartz–Zippel lemma による hash の解析 – noshi91
• 相異なる $n$ 文字の文字列 $m$ 個がどこかで衝突する確率は，$\frac{n \cdot \binom{m}{2}}{P}$ 以下
  • $(n, m) = (1, 10^6)$ を $100$ ケースやっても $0.002\%$ なので，衝突は基本的に無視できる

Verified with

• test/string/RollingHash.test.cpp

Code

// using u64 = uint64_t;
const u64 mod = INF;
u64 add(u64 a, u64 b) {
   a += b;
   if(a >= mod) a -= mod;
   return a;
}
u64 mul(u64 a, u64 b) {
   auto c = (__uint128_t)a * b;
   return add(c >> 61, c & mod);
}
random_device rnd;
const u64 r = ((u64)rnd() << 32 | rnd()) % mod;
struct RH {
   ll n;
   vector<u64> hs, pw;
   RH(string s) : n(sz(s)), hs(n + 1), pw(n + 1, 1) {
      rep(i, 0, n) {
         pw[i + 1] = mul(pw[i], r);
         hs[i + 1] = add(mul(hs[i], r), s[i]);
      }
   }
   u64 get(ll l, ll r) const { return add(hs[r], mod - mul(hs[l], pw[r - l])); }
};

#line 1 "src/string/RollingHash.hpp"
// using u64 = uint64_t;
const u64 mod = INF;
u64 add(u64 a, u64 b) {
   a += b;
   if(a >= mod) a -= mod;
   return a;
}
u64 mul(u64 a, u64 b) {
   auto c = (__uint128_t)a * b;
   return add(c >> 61, c & mod);
}
random_device rnd;
const u64 r = ((u64)rnd() << 32 | rnd()) % mod;
struct RH {
   ll n;
   vector<u64> hs, pw;
   RH(string s) : n(sz(s)), hs(n + 1), pw(n + 1, 1) {
      rep(i, 0, n) {
         pw[i + 1] = mul(pw[i], r);
         hs[i + 1] = add(mul(hs[i], r), s[i]);
      }
   }
   u64 get(ll l, ll r) const { return add(hs[r], mod - mul(hs[l], pw[r - l])); }
};

Back to top page