ハッシュを計算する構造体
タイトルの通りです。
衝突しにくい構造体が作りたかった（衝突すると悲しいので）
コード
struct Hash { static constexpr ll M1 = (1LL << 61) - 1; static constexpr ll M2 = (1LL << 31) - 1; ll val1, val2; constexpr Hash(ll val = 0) noexcept : val1(val), val2(val) {} constexpr Hash(ll val1, ll val2) noexcept : val1(val1), val2(val2 % M2) { if (val1 >= M1) val1 -= M1; } constexpr Hash operator-() const noexcept { return Hash(val1 ? M1 - val1 : 0, val2 ? M2 - val2 : 0); } constexpr Hash operator+=(const Hash &h) noexcept { val1 += h.val1; if (val1 > M1) val1 -= M1; val2 += h.val2; if (val2 > M2) val2 -= M2; return *this; } constexpr Hash operator-=(const Hash &h) noexcept { val1 -= h.val1; if (val1 < 0) val1 += M1; val2 -= h.val2; if (val2 < 0) val2 += M2; return *this; } Hash operator*=(const Hash &h) noexcept { __int128 t; t = val1; t *= h.val1; t = (t >> 61) + (t & M1); if (t >= M1) t -= M1; val1 = ll(t); val2 *= h.val2; val2 = (val2 >> 31) + (val2 & M2); if (val2 >= M2) val2 -= M2; return *this; } constexpr Hash operator+(const Hash &h) const noexcept { return Hash(*this) += h; } constexpr Hash operator-(const Hash &h) const noexcept { return Hash(*this) -= h; } Hash operator*(const Hash &h) const noexcept { return Hash(*this) *= h; } constexpr bool operator==(const Hash &h) const noexcept { return val1 == h.val1 and val2 == h.val2; } constexpr bool operator!=(const Hash &h) const noexcept { return !(*this == h); } constexpr bool operator<(const Hash &h) const noexcept { return val1 == h.val1 ? val2 < h.val2 : val1 < h.val1; } friend ostream &operator<<(ostream &os, const Hash &h) noexcept { return os << "(" << h.val1 << ", " << h.val2 << ")"; } };
mod2^61-1とmod2^31-1をペアで持ってます。比較演算子<はsetとかに入れる用です。
定数倍は速いはず。
あとローリングハッシュのライブラリも作ったので置いておきます。
class RollingHash { Hash B; pair<Hash, Hash> _calc(string &s, int l, int r) { assert(l <= r); Hash res, p = 1; for (int i = r - 1; i >= l; i--) { res += p * ll(s[i]); if (i != l) p *= B; } return {res, p}; } public: RollingHash() { random_device seed; mt19937 engine(seed()); B = Hash(ll(engine()) + 1000, ll((engine()) + 1000)); } // [l, r) のハッシュを計算 Hash calc(string &s, int l = -1, int r = -1) { if (l == -1) l = 0, r = s.length(); return _calc(s, l, r).first; } // s の長さ m の部分文字列のハッシュ vector<Hash> Roll(string &s, int m) { vector<Hash> hash; int n = s.length(); assert(n >= m); hash.resize(n - m + 1); auto [h, p] = _calc(s, 0, m); hash[0] = h; for (int i = m; i < n; i++) { h -= p * ll(s[i - m]); h *= B; h += ll(s[i]); hash[i - m + 1] = h; } return hash; } };
機能が少ないのでもう少し整備したい
