ホーム > libalgo

連続する部分文字列のハッシュ

使い方

RH hs(s,b)
s のハッシュを求めるクラスを構築.b には [2,m-1] の乱数を渡す (省略可).
hs.set(s,b)
s のハッシュを再構築.vector の再構築は重いので,コンストラクタよりこっちを呼んで使いまわした方がいい.
hs.get(l,r)
[l,r) のハッシュを取得.

衝突が怖いときは複数の b で計算して全て一致するか確かめる. MOD を素数にせずに unsiguned long long で MOD 2^64 にすると精度を犠牲にしてかなり速くなる.

実装

template <unsigned long long MOD>
class rolling_hash {
public:
    using ull = unsigned long long;
    int n;
    ull b;
    std::vector<ull> pow, hash;

    rolling_hash() {}

    rolling_hash(const std::string &s, ull b_ = 10007) { set(s, b_); }

    void set(const std::string &s, ull b_ = 10007) {
        n = s.size();
        b = b_;
        calc(s.c_str());
    }

    ull get(int i) const { return hash[i]; }

    ull get(int i, int j) const { return (get(j) - get(i) * pow[j - i] % MOD + MOD) % MOD; }

private:
    void calc(const char *s) {
        pow.resize(n + 1);
        pow[0] = 1;
        hash.resize(n + 1);
        hash[0] = 0;
        for (int i = 0; i < n; ++i) {
            pow[i + 1] = pow[i] * b % MOD;
            hash[i + 1] = (s[i] + hash[i] * b) % MOD;
        }
    }
};

// 1000000007, 1000000009, 1000000021, ...
using RH = rolling_hash<1000000007>;

検証

AOJ2763 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2024422

参考文献