連続する部分文字列のハッシュ
使い方
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 にすると精度を犠牲にしてかなり速くなる．
実装
using rh_type = unsigned long long;
template <rh_type MOD = 0>
struct rolling_hash {
int n;
rh_type base;
std::vector<rh_type> pow, hash;
rolling_hash() {}
template <typename Array>
rolling_hash(const Array &s, rh_type b_ = 10007) {
set(s, b_);
}
template <typename Array>
void set(const Array &s, rh_type b_ = 10007) {
n = s.size();
base = b_;
pow.resize(n + 1);
pow[0] = 1;
hash.resize(n + 1);
hash[0] = 0;
for (int i = 0; i < n; ++i) {
if (MOD == 0) {
pow[i + 1] = pow[i] * base;
hash[i + 1] = s[i] + hash[i] * base;
} else {
pow[i + 1] = pow[i] * base % MOD;
hash[i + 1] = (s[i] + hash[i] * base) % MOD;
}
}
}
rh_type get(int r) const { return hash[r]; }
rh_type get(int l, int r) const {
if (MOD == 0) {
return get(r) - get(l) * pow[r - l];
} else {
return (get(r) - get(l) * pow[r - l] % MOD + MOD) % MOD;
}
}
};
// 1000000007, 1000000009, 1000000021, ...
using RH = rolling_hash<1000000007>;
検証
AOJ2763 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2024422