Rolling Hash
(library/string/rolling-hash.hpp)

• View this file on GitHub
• Last update: 2023-08-13 14:16:40+08:00
• Include: #include "library/string/rolling-hash.hpp"

使用方法

using H = rolling_hash<modint61>;

H s("aaa"), t("aa");
assert(s.get() * 2 == t.get() * 3);

t.add_char('a'); // t = "aaa"
assert(s.get() == t.get());
assert(s.get(0, 2) == t.get(1, 3)); // [l, r)
assert(s.get() + t.get() == H("aaaaaa").get());

範例

1. ABC312 Ex - snukesnuke

References

1. https://hitonanode.github.io/cplib-cpp/string/rolling_hash_1d.hpp
2. tourist

Depends on

• library/modint/modint61.hpp

Verified with

• test/string/rolling-hash/aoj-alds1-String-Search.test.cpp

Code

#pragma once
#include <vector>

#include <cstring>

#include <cassert>

#include <chrono>

#include <random>

#include "../modint/modint61.hpp"


namespace felix {

template<class M = modint61>
struct rolling_hash {
	static std::vector<M> power;
	static M base;

	static void prepare(int _n) {
		if(power.size() > 1 && power[0] != base) {
			power = {M(1)};
		}
		while((int) power.size() <= _n) {
			power.emplace_back(power.back() * base);
		}
	}

	rolling_hash() : n(0) {}
	rolling_hash(const std::string& s, M B = generate_base()) : n(s.size()), pref(s.size() + 1) {
		base = B;
		for(int i = 0; i < n; i++) {
			pref[i + 1] = pref[i] * base + s[i];
		}
		prepare(n);
	}

	constexpr int size() const { return n; }
	constexpr int length() const { return n; }

	void add_char(char c) {
		pref.emplace_back(pref[n] * base + c);
		n++;
		prepare(n);
	}

	struct Hash {
		M val;
		int len;

		constexpr Hash() : len(0) {}
		constexpr Hash(const M& x, int L) : val(x), len(L) {}

		constexpr int size() const { return len; }
		constexpr int length() const { return len; }

		// S + T

		constexpr Hash& operator+=(const Hash& rhs) & {
			val = val * power[rhs.len] + rhs.val;
			len += rhs.len;
			return *this;
		}

		// S + ... + S

		constexpr Hash& operator*=(int n) & {
			if(len > 0) {
				M a1 = val;
				M r = (len < (int) power.size() ? power[len] : base.pow(len));
				val = a1 * (r.pow(n) - 1U) / (r - 1U);
				len *= n;
			}
			return *this;
		}

		friend constexpr Hash operator+(Hash lhs, Hash rhs) { return lhs += rhs; }
		friend constexpr Hash operator*(Hash s, int n) { return s *= n; }

		constexpr bool operator==(const Hash& rhs) const { return val == rhs.val && len == rhs.len; }
		constexpr bool operator<(const Hash& rhs) const { return val.val() < rhs.val.val() || (val.val() == rhs.val.val() && len < rhs.len); }
	};

	// [l, r)

	constexpr Hash get(int l, int r) const {
		assert(0 <= l && l <= r && r <= n);
		return Hash(pref[r] - pref[l] * power[r - l], r - l);
	}

	constexpr Hash get() const {
		return Hash(pref[n], n);
	}

	static inline M generate_base(bool new_base = false) {
		static M B(0);
		if(B.val() == 0 || new_base) {
			std::mt19937_64 mt(std::chrono::steady_clock::now().time_since_epoch().count());
			std::uniform_int_distribution<unsigned long long> rd(1, M::mod() - 1);
			B = M(rd(mt));
		}
		return B;
	}

private:
	int n;
	std::vector<M> pref;
};

template<class M> std::vector<M> rolling_hash<M>::power{M(1)};
template<class M> M rolling_hash<M>::base;

} // namespace felix

#line 2 "library/string/rolling-hash.hpp"
#include <vector>

#include <cstring>

#include <cassert>

#include <chrono>

#include <random>

#line 2 "library/modint/modint61.hpp"
#include <iostream>

#line 4 "library/modint/modint61.hpp"

namespace felix {

// 2^61 - 1

struct modint61 {
private:
	using M = modint61;

	static constexpr long long md = (1LL << 61) - 1;

public:
	static constexpr long long mod() { return md; }

	constexpr modint61() : v(0) {}
	// 0 <= x < md * 2

	constexpr explicit modint61(long long x) : v(x >= md ? x - md : x) {}

	constexpr long long val() const { return v; }
	constexpr M inv() const { return pow(md - 2); }

	constexpr M& operator+=(const M& rhs) & {
		v += rhs.v;
		if(v >= md) {
			v -= md;
		}
		return *this;
	}

	constexpr M& operator-=(const M& rhs) & {
		v -= rhs.v;
		if(v < 0) {
			v += md;
		}
		return *this;
	}

	constexpr M& operator*=(const M& rhs) & {
		using ull = unsigned long long;

		ull uu = (ull) hi() * rhs.hi() * 2;
		ull ll = (ull) lo() * rhs.lo();
		ull lu = (ull) hi() * rhs.lo() + (ull) lo() * rhs.hi();
		ull sum = uu + ll + ((lu & ((1ULL << 30) - 1)) << 31) + (lu >> 30);
		v = (sum >> 61) + (sum & ull(md));
		if(v >= md) {
			v -= md;
		}
		return *this;
	}

	constexpr M& operator/=(const M& rhs) & {
		return *this *= rhs.inv();
	}

	constexpr M& operator+=(const unsigned int& rhs) & { return *this += M(rhs); }
	constexpr M& operator-=(const unsigned int& rhs) & { return *this -= M(rhs); }

	constexpr M pow(long long n) const {
		assert(n >= 0);
		M ans(1), a = *this;
		while(n) {
			if(n & 1) {
				ans *= a;
			}
			a *= a;
			n >>= 1;
		}
		return ans;
	}

	friend constexpr M operator+(M lhs, M rhs) { return lhs += rhs; }
	friend constexpr M operator-(M lhs, M rhs) { return lhs -= rhs; }
	friend constexpr M operator*(M lhs, M rhs) { return lhs *= rhs; }
	friend constexpr M operator/(M lhs, M rhs) { return lhs /= rhs; }

	friend constexpr M operator+(M lhs, unsigned int rhs) { return lhs += rhs; }
	friend constexpr M operator-(M lhs, unsigned int rhs) { return lhs -= rhs; }

	constexpr M operator+() const { return *this; }
	constexpr M operator-() const { return M(md - v); }
	constexpr bool operator==(const M &rhs) const { return v == rhs.v; }
	constexpr bool operator!=(const M &rhs) const { return v != rhs.v; }
	
	friend std::ostream& operator<<(std::ostream& out, const M& num) {
		return out << num.v;
	}

private:
	long long v;

	inline constexpr unsigned int hi() const { return v >> 31; }
	inline constexpr unsigned int lo() const { return v & ((1ULL << 31) - 1); }
};

} // namespace felix

#line 8 "library/string/rolling-hash.hpp"

namespace felix {

template<class M = modint61>
struct rolling_hash {
	static std::vector<M> power;
	static M base;

	static void prepare(int _n) {
		if(power.size() > 1 && power[0] != base) {
			power = {M(1)};
		}
		while((int) power.size() <= _n) {
			power.emplace_back(power.back() * base);
		}
	}

	rolling_hash() : n(0) {}
	rolling_hash(const std::string& s, M B = generate_base()) : n(s.size()), pref(s.size() + 1) {
		base = B;
		for(int i = 0; i < n; i++) {
			pref[i + 1] = pref[i] * base + s[i];
		}
		prepare(n);
	}

	constexpr int size() const { return n; }
	constexpr int length() const { return n; }

	void add_char(char c) {
		pref.emplace_back(pref[n] * base + c);
		n++;
		prepare(n);
	}

	struct Hash {
		M val;
		int len;

		constexpr Hash() : len(0) {}
		constexpr Hash(const M& x, int L) : val(x), len(L) {}

		constexpr int size() const { return len; }
		constexpr int length() const { return len; }

		// S + T

		constexpr Hash& operator+=(const Hash& rhs) & {
			val = val * power[rhs.len] + rhs.val;
			len += rhs.len;
			return *this;
		}

		// S + ... + S

		constexpr Hash& operator*=(int n) & {
			if(len > 0) {
				M a1 = val;
				M r = (len < (int) power.size() ? power[len] : base.pow(len));
				val = a1 * (r.pow(n) - 1U) / (r - 1U);
				len *= n;
			}
			return *this;
		}

		friend constexpr Hash operator+(Hash lhs, Hash rhs) { return lhs += rhs; }
		friend constexpr Hash operator*(Hash s, int n) { return s *= n; }

		constexpr bool operator==(const Hash& rhs) const { return val == rhs.val && len == rhs.len; }
		constexpr bool operator<(const Hash& rhs) const { return val.val() < rhs.val.val() || (val.val() == rhs.val.val() && len < rhs.len); }
	};

	// [l, r)

	constexpr Hash get(int l, int r) const {
		assert(0 <= l && l <= r && r <= n);
		return Hash(pref[r] - pref[l] * power[r - l], r - l);
	}

	constexpr Hash get() const {
		return Hash(pref[n], n);
	}

	static inline M generate_base(bool new_base = false) {
		static M B(0);
		if(B.val() == 0 || new_base) {
			std::mt19937_64 mt(std::chrono::steady_clock::now().time_since_epoch().count());
			std::uniform_int_distribution<unsigned long long> rd(1, M::mod() - 1);
			B = M(rd(mt));
		}
		return B;
	}

private:
	int n;
	std::vector<M> pref;
};

template<class M> std::vector<M> rolling_hash<M>::power{M(1)};
template<class M> M rolling_hash<M>::base;

} // namespace felix

Back to top page