競プロノート

Appearance

Rolling Hash（ローリングハッシュ） ​

文字列の部分文字列をハッシュ値に変換し、高速に比較するアルゴリズム。

前処理 O(N) で、任意の部分文字列のハッシュ値を O(1) で求められる。

イメージ ​

S = "abacaba"

次の部分文字列は同じ文字列である。

  • S[0, 3) = "aba"
  • S[4, 7) = "aba"

Rolling Hashでは、この2つの部分文字列のハッシュ値を O(1) で比較できる。

特徴 ​

項目計算量
前処理O(N)
部分文字列のハッシュ取得O(1)
部分文字列の比較O(1)
LCP（最長共通接頭辞長）O(log N)
空間計算量O(N)

実装 ​

cpp

#pragma once
#include <algorithm>
#include <cassert>
#include <chrono>
#include <random>
#include <string>
#include <vector>

struct RollingHash {
    using ull = unsigned long long;
    static constexpr ull MOD = (1ULL << 61) - 1;

    static ull reduce(__uint128_t x) {
        ull v = (ull)(x >> 61) + (ull)(x & MOD);
        return v >= MOD ? v - MOD : v;
    }

    static ull mul(ull a, ull b) { return reduce((__uint128_t)a * b); }

    static ull base() {
        static const ull b = [] {
            std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
            return std::uniform_int_distribution<ull>(257, MOD - 2)(rng);
        }();
        return b;
    }

    std::vector<ull> h, pw;

    RollingHash() = default;
    explicit RollingHash(const std::string& s) { build(s); }

    void build(const std::string& s) {
        int n = (int)s.size();
        h.assign(n + 1, 0);
        pw.assign(n + 1, 1);
        ull b = base();
        for (int i = 0; i < n; i++) {
            pw[i + 1] = mul(pw[i], b);
            h[i + 1] = mul(h[i], b) + (unsigned char)s[i] + 1;
            if (h[i + 1] >= MOD) h[i + 1] -= MOD;
        }
    }

    // 半開区間 [l, r) のハッシュ O(1)
    ull get(int l, int r) const {
        assert(0 <= l && l <= r && r < (int)h.size());
        ull x = h[r] + MOD - mul(h[l], pw[r - l]);
        return x >= MOD ? x - MOD : x;
    }

    // 2つの部分文字列が一致するか O(1)
    bool same(int l1, int r1, const RollingHash& other, int l2, int r2) const {
        return r1 - l1 == r2 - l2 && get(l1, r1) == other.get(l2, r2);
    }

    // 2つのsuffixの最長共通接頭辞長 O(log N)
    int lcp(int i, const RollingHash& other, int j) const {
        assert(0 <= i && i < (int)h.size());
        assert(0 <= j && j < (int)other.h.size());
        int lo = 0, hi = std::min((int)h.size() - 1 - i, (int)other.h.size() - 1 - j) + 1;
        while (hi - lo > 1) {
            int mid = (lo + hi) / 2;
            if (get(i, i + mid) == other.get(j, j + mid)) lo = mid;
            else hi = mid;
        }
        return lo;
    }
};

使用例 ​

部分文字列の比較 ​

cpp
RollingHash rh("abacaba");

cout << rh.same(0, 3, rh, 4, 7) << '\n'; // 1
cout << rh.same(0, 3, rh, 1, 4) << '\n'; // 0

異なる文字列の比較 ​

cpp
RollingHash a("abacaba");
RollingHash b("aba");

cout << a.same(0, 3, b, 0, 3) << '\n'; // 1
cout << a.lcp(0, b, 0) << '\n';         // 3

文字列検索 ​

文字列 s に t が現れる位置を列挙する。

cpp
string s = "abracadabra", t = "abra";
RollingHash hs(s), ht(t);

int n = s.size(), m = t.size();
for (int i = 0; i + m <= n; i++) {
    if (hs.same(i, i + m, ht, 0, m)) {
        cout << i << '\n'; // 0, 7
    }
}

主な操作 ​

メソッド機能
build(s)文字列を前処理する
get(l, r)半開区間 [l, r) のハッシュ値
same(l1, r1, other, l2, r2)2つの部分文字列が一致するか
lcp(i, other, j)2つのsuffixの最長共通接頭辞長

注意点 ​

  • ハッシュの衝突があるため、比較は確率的であり、完全な一致判定ではない。
  • 区間は半開区間 [l, r)。
  • 異なる長さの文字列は same() で一致しないようにしている。
  • 基数は実行時にランダムに決定する。同一プログラム内では共通。
  • ハッシュ値を異なるプログラムの実行間で比較してはいけない。
  • この実装では mod 2^61-1 と __uint128_t を使用する（g++向け）。
  • UTF-8文字列はバイト単位で処理する。

Z-Algorithmとの使い分け ​

Z-AlgorithmRolling Hash
prefixとの一致長O(N)で全位置を計算LCPクエリごとに O(log N)
任意の部分文字列の比較工夫が必要O(1)
衝突の可能性なしあり
実装の簡潔さ◎○

単純な文字列検索ならZ-Algorithmで十分な場合が多い。

任意の部分文字列を何度も比較する場合はRolling Hashが便利。

関連 ​