Rolling Hash
(library/string/rolling_hash.hpp)

• View this file on GitHub
• Last update: 2026-01-20 20:11:22+09:00
• Include: #include "library/string/rolling_hash.hpp"

Rolling Hash

詳しい説明

できること

• 文字列Sをハッシュに変換する
• get(0, 5): 0~5文字目の部分文字列のハッシュを取得
• ハッシュが同じであれば、文字列が同じである
• ハッシュ衝突の危険性について
  • 法にメルセンヌ素数 $2^{61}-1$ を、基数に実行時疑似乱数を使用していますが、比較するハッシュ値の数が増えると衝突確率が急上昇します
    • 原因: 「誕生日パラドックス」
    • 衝突の目安: およそ $\sqrt M$ 個(約 $1.5 \cdot 10^{9}$ )個の異なるハッシュを生成して比較すると50%の確率で衝突する

計算量

• 構築: $O(\vert S \vert)$
• get: $O(1)$

使い方

string S = "xxx";
RollingHash rh(S);
// ハッシュで比較
if (rh.get(0, 4) == rh.get(7, 11)) {}

string S = "xxxaaa";
RollingHash rh(S);
long long h_1 = rh.get(0, 2);
long long h_2 = rh.get(2, 5); // bの長さ3
// ハッシュをマージ
if (RollingHash::merge(h_1, h_2, 3) == rh.get(0, 5)) {}

Depends on

• 擬似乱数生成 (library/various/random.hpp)

Required by

• 文字列複数 統合検索エンジン (library/string/finds.hpp)

Verified with

• 文字列複数 統合検索エンジンのテスト (tests/string.finds.test.cpp)
• ロリハのテスト (tests/string.rolling_hash.test.cpp)

Code

#pragma once
#include "library/various/random.hpp"
struct RollingHash {
    static const long long MOD = (1LL << 61) - 1;
    static inline long long base = 0;
    vector<long long> hash_sum;
    // 基数をメルセンヌツイスタの乱数で初期化する
    static void init_base() {
        if (base != 0) return;
        base = random(2, MOD - 1);
    }
    // 文字列からハッシュの累積和を構築する
    RollingHash(const string &s) {
        init_base();
        int n = s.size();
        hash_sum.assign(n + 1, 0);
        for (int i = 0; i < n; i++) {
            hash_sum[i + 1] = mul(hash_sum[i], base) + s[i];
            if (hash_sum[i + 1] >= MOD) hash_sum[i + 1] -= MOD;
        }
    }
    // 2^61-1 用の高速な掛け算
    static long long mul(long long a, long long b) {
        __int128_t res = (__int128_t)a * b;
        long long ans = (long long)(res >> 61) + (long long)(res & MOD);
        if (ans >= MOD) ans -= MOD;
        return ans;
    }
    // 累乗テーブルの管理
    static const vector<long long> &get_pow(int n) {
        static vector<long long> pow_memo = {1};
        while ((int)pow_memo.size() <= n) {
            pow_memo.push_back(mul(pow_memo.back(), base));
        }
        return pow_memo;
    }
    // s[l, r) のハッシュを取得
    long long get(int l, int r) const {
        long long res = hash_sum[r] - mul(hash_sum[l], get_pow(r - l)[r - l]);
        if (res < 0) res += MOD;
        return res;
    }
    // 2つのハッシュ(a, b)を結合する。bの長さが b_len
    static long long merge(long long a_hash, long long b_hash, int b_len) {
        long long res = mul(a_hash, get_pow(b_len)[b_len]) + b_hash;
        if (res >= MOD) res -= MOD;
        return res;
    }
};

#line 2 "library/various/random.hpp"
#include <chrono>
#include <random>
inline long long random(long long a, long long b) {
    if (a >= b) return a;
    static mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
    uniform_int_distribution<long long> dist(a, b - 1);
    return dist(mt);
}
#line 3 "library/string/rolling_hash.hpp"
struct RollingHash {
    static const long long MOD = (1LL << 61) - 1;
    static inline long long base = 0;
    vector<long long> hash_sum;
    // 基数をメルセンヌツイスタの乱数で初期化する
    static void init_base() {
        if (base != 0) return;
        base = random(2, MOD - 1);
    }
    // 文字列からハッシュの累積和を構築する
    RollingHash(const string &s) {
        init_base();
        int n = s.size();
        hash_sum.assign(n + 1, 0);
        for (int i = 0; i < n; i++) {
            hash_sum[i + 1] = mul(hash_sum[i], base) + s[i];
            if (hash_sum[i + 1] >= MOD) hash_sum[i + 1] -= MOD;
        }
    }
    // 2^61-1 用の高速な掛け算
    static long long mul(long long a, long long b) {
        __int128_t res = (__int128_t)a * b;
        long long ans = (long long)(res >> 61) + (long long)(res & MOD);
        if (ans >= MOD) ans -= MOD;
        return ans;
    }
    // 累乗テーブルの管理
    static const vector<long long> &get_pow(int n) {
        static vector<long long> pow_memo = {1};
        while ((int)pow_memo.size() <= n) {
            pow_memo.push_back(mul(pow_memo.back(), base));
        }
        return pow_memo;
    }
    // s[l, r) のハッシュを取得
    long long get(int l, int r) const {
        long long res = hash_sum[r] - mul(hash_sum[l], get_pow(r - l)[r - l]);
        if (res < 0) res += MOD;
        return res;
    }
    // 2つのハッシュ(a, b)を結合する。bの長さが b_len
    static long long merge(long long a_hash, long long b_hash, int b_len) {
        long long res = mul(a_hash, get_pow(b_len)[b_len]) + b_hash;
        if (res >= MOD) res -= MOD;
        return res;
    }
};

Back to top page