Rolling Hash

string/rolling_hash.hpp · GitHub で見る

共通ページ

#include "lib/string/rolling_hash.hpp"

RollingHash a("abracadabra"), b("abra");
auto hash = a.get(0, 4);
bool same = hash == b.get();
int length = a.lcp(0, b, 0);
auto joined = RollingHash::concat(a.get(0, 4), b.get(), b.size());

操作	内容・返り値	計算量
`RollingHash()` / `RollingHash(s)` / `RollingHash(a)`	空／文字列／整数配列から構築	空: \(O(1)\)、配列: \(O(n)\)
`build(s)` / `build(a)`	文字列／整数配列で再構築	\(O(n)\)
`size()` / `empty()`	要素数／空判定	\(O(1)\)
`get()` / `get(l,r)`	全体／\([l,r)\) のハッシュ	\(O(1)\)
`value()` / `value(l,r)`	全体／\([l,r)\) を長さ付きの `Value` で取得	\(O(1)\)
`lcp(l,other,j)`	接尾辞同士の最長共通接頭辞長	\(O(\log k)\)
`lcp(l,r,other,j,k)`	\([l,r)\) と相手の \([j,k)\) の最長共通接頭辞長	\(O(\log k)\)
`RollingHash::concat(left,right,right_length)`	生のハッシュ同士を連結	準備済み: \(O(1)\)、累乗の拡張: 合計 \(O(N)\)
`RollingHash::reserve(n)`	基数の累乗を長さ `n` まで準備	拡張分に比例
`RollingHash::single(x)` / `RollingHash::e()`	1 要素／空列の `Value`	\(O(1)\)
`RollingHash::op(a,b)`	`Value` をこの順で連結	準備済み: \(O(1)\)、累乗の拡張: 合計 \(O(N)\)
`RollingHash::base()` / `RollingHash::mod`	共通の基数／法	\(O(1)\)
`a == b` / `a != b`	`Value` のハッシュと長さを比較	\(O(1)\)

get(l,r) は \([l,r)\)、get() は全体のハッシュです。lcp(l,b,j) は両接尾辞の LCP、lcp(l,r,b,j,k) は区間 \([l,r)\) と \([j,k)\) の LCP を返します。concat(x,y,len) は x の後ろに長さ len の y を連結します。

std::string_view・整数の std::vector<T> から構築でき、build(a) で再構築できます。整数は法で正規化し、文字列の char は符号なし byte として扱います。size()・empty() も使えます。

法は \(2^{61}-1\)、base() は実行ごとにランダムな共通の基数です。同じ長さの区間同士でハッシュを比較します。ハッシュの衝突が起こる可能性があります。

#include "lib/string/rolling_hash.hpp"
#include <atcoder/segtree>

using RH = RollingHash;
RH::reserve(11);
std::vector<RH::Value> values;
for (char c : std::string_view("abracadabra")) values.push_back(RH::single(c));
atcoder::segtree<RH::Value, RH::op, RH::e> seg(values);
seg.set(0, RH::single('x'));
auto part = seg.prod(7, 11);
bool same = part == RH("abra").value();

Value は hash と length を持つモノイドです。single(x) は 1 要素、op(a,b) はこの順での連結、e() は空列です。value(l,r)・value() は区間・全体を Value として取り出します。Value の比較は長さも含みます。reserve(n) で累乗を長さ n まで準備できます。

長さを \(n\)、LCP の比較区間の短い方の長さを \(k\) として、構築は \(O(n)\)、取得・single・e は \(O(1)\)、LCP は \(O(\log k)\) です。基数の累乗は全インスタンスで共有し、長さ \(N\) まで合計 \(O(N)\) 時間・空間で拡張します。連結・op は必要な累乗があれば \(O(1)\)、各インスタンスの空間は \(O(n)\) です。Segtree で reserve(n) を済ませた場合、構築は \(O(n)\)、点更新・区間取得は \(O(\log n)\)、空間は \(O(n)\) です。

依存ライブラリ

SplitMix64

検証コード

test/rolling_hash.test.cpp

コード

#line 1 "string/rolling_hash.hpp"

#line 1 "components/splitmix64.hpp"

#include <cstdint>

inline std::uint64_t splitmix64(std::uint64_t x) {
	x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
	x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
	return x ^ (x >> 31);
}
class SplitMix64 {
	std::uint64_t state;

public:
	explicit SplitMix64(std::uint64_t seed = 0) : state(seed) {}
	std::uint64_t operator()() { return splitmix64(state += 0x9e3779b97f4a7c15ULL); }
};

#line 5 "string/rolling_hash.hpp"
#include <algorithm>
#include <cassert>
#include <chrono>
#include <cstddef>
#line 10 "string/rolling_hash.hpp"
#include <limits>
#include <string_view>
#include <type_traits>
#include <vector>

class RollingHash {
  public:
	using Hash = std::uint64_t;
	struct Value {
		Hash hash = 0;
		int length = 0;
		bool operator==(const Value &) const = default;
	};
	static constexpr Hash mod = (Hash(1) << 61) - 1;
	static Hash base() {
		static const Hash value = splitmix64(Hash(std::chrono::steady_clock::now().time_since_epoch().count()) ^ Hash(reinterpret_cast<std::uintptr_t>(&powers))) % (mod - 512) + 256;
		return value;
	}

private:
	inline static std::vector<Hash> powers{1};
	std::vector<Hash> prefix;
	static Hash reduce(__uint128_t value) {
		Hash result = (Hash(value) & mod) + Hash(value >> 61);
		return result >= mod ? result - mod : result;
	}
	static Hash mul(Hash a, Hash b) { return reduce(__uint128_t(a) * b); }
	static void ensure_powers(int n) {
		std::size_t old = powers.size();
		if (std::size_t(n) < old) return;
		powers.resize(std::size_t(n) + 1);
		Hash b = base();
		std::size_t i = old;
		for (; i < powers.size() && i < old + 4; ++i) powers[i] = mul(powers[i - 1], b);
		if (i == powers.size()) return;
		Hash step = powers[4];
		for (; i + 4 <= powers.size(); i += 4) {
			powers[i] = mul(powers[i - 4], step);
			powers[i + 1] = mul(powers[i - 3], step);
			powers[i + 2] = mul(powers[i - 2], step);
			powers[i + 3] = mul(powers[i - 1], step);
		}
		for (; i < powers.size(); ++i) powers[i] = mul(powers[i - 4], step);
	}
	template <class T>
	static Hash encode(T value) {
		static_assert(std::is_integral_v<T> && sizeof(T) <= 8);
		if constexpr (std::is_same_v<T, char>) return static_cast<unsigned char>(value) + 1;
		else if constexpr (sizeof(T) <= 4) {
			if constexpr (std::is_signed_v<T>) return value >= -1 ? Hash(std::int64_t(value) + 1) : Hash(std::int64_t(value) + std::int64_t(mod) + 1);
			else return Hash(value) + 1;
		} else {
			Hash result;
			if constexpr (std::is_signed_v<T>) {
				std::int64_t x = std::int64_t(value) % std::int64_t(mod);
				result = x < 0 ? Hash(x + std::int64_t(mod)) : Hash(x);
			} else result = Hash(value) % mod;
			return result == mod - 1 ? 0 : result + 1;
		}
	}
	template <class Range>
	void build_range(const Range &values) {
		assert(values.size() <= std::size_t(std::numeric_limits<int>::max()));
		int n = int(values.size());
		ensure_powers(n);
		prefix.resize(std::size_t(n) + 1);
		Hash value = 0, b = base();
		prefix[0] = 0;
		int i = 0;
		for (typename Range::value_type x : values) prefix[++i] = value = reduce(__uint128_t(value) * b + encode(x));
	}

public:
	RollingHash() = default;
	explicit RollingHash(std::string_view s) { build(s); }
	template <class T>
	explicit RollingHash(const std::vector<T> &values) { build(values); }
	void build(std::string_view s) { build_range(s); }
	template <class T>
	void build(const std::vector<T> &values) { build_range(values); }
	int size() const { return prefix.empty() ? 0 : int(prefix.size() - 1); }
	bool empty() const { return !size(); }
	static void reserve(int n) {
		assert(n >= 0);
		ensure_powers(n);
	}
	template <class T>
	static Value single(T x) { return {encode(x), 1}; }
	static Value e() { return {}; }
	static Value op(Value left, Value right) {
		assert(left.length >= 0 && right.length >= 0 && left.length <= std::numeric_limits<int>::max() - right.length);
		if (!left.length) return right;
		if (!right.length) return left;
		return {concat(left.hash, right.hash, right.length), left.length + right.length};
	}
	Hash get() const { return prefix.empty() ? 0 : prefix.back(); }
	Hash get(int l, int r) const {
		assert(0 <= l && l <= r && r <= size());
		if (!l) return r ? prefix[r] : 0;
		Hash value = prefix[r] + mod - mul(prefix[l], powers[r - l]);
		return value >= mod ? value - mod : value;
	}
	Value value() const { return {get(), size()}; }
	Value value(int l, int r) const { return {get(l, r), r - l}; }
	static Hash concat(Hash left, Hash right, int right_length) {
		assert(left < mod && right < mod && right_length >= 0);
		ensure_powers(right_length);
		return reduce(__uint128_t(left) * powers[right_length] + right);
	}
	int lcp(int l, int r, const RollingHash &other, int other_l, int other_r) const {
		assert(0 <= l && l <= r && r <= size() && 0 <= other_l && other_l <= other_r && other_r <= other.size());
		int low = 0, high = std::min(r - l, other_r - other_l);
		while (low < high) {
			int mid = high - (high - low) / 2;
			if (get(l, l + mid) == other.get(other_l, other_l + mid)) low = mid;
			else high = mid - 1;
		}
		return low;
	}
	int lcp(int l, const RollingHash &other, int other_l) const { return lcp(l, size(), other, other_l, other.size()); }
};

#ifndef ROLLING_HASH_HPP
#define ROLLING_HASH_HPP

#include "../components/splitmix64.hpp"
#include <algorithm>
#include <cassert>
#include <chrono>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <string_view>
#include <type_traits>
#include <vector>

class RollingHash {
  public:
	using Hash = std::uint64_t;
	struct Value {
		Hash hash = 0;
		int length = 0;
		bool operator==(const Value &) const = default;
	};
	static constexpr Hash mod = (Hash(1) << 61) - 1;
	static Hash base() {
		static const Hash value = splitmix64(Hash(std::chrono::steady_clock::now().time_since_epoch().count()) ^ Hash(reinterpret_cast<std::uintptr_t>(&powers))) % (mod - 512) + 256;
		return value;
	}

  private:
	inline static std::vector<Hash> powers{1};
	std::vector<Hash> prefix;
	static Hash reduce(__uint128_t value) {
		Hash result = (Hash(value) & mod) + Hash(value >> 61);
		return result >= mod ? result - mod : result;
	}
	static Hash mul(Hash a, Hash b) { return reduce(__uint128_t(a) * b); }
	static void ensure_powers(int n) {
		std::size_t old = powers.size();
		if (std::size_t(n) < old) return;
		powers.resize(std::size_t(n) + 1);
		Hash b = base();
		std::size_t i = old;
		for (; i < powers.size() && i < old + 4; ++i) powers[i] = mul(powers[i - 1], b);
		if (i == powers.size()) return;
		Hash step = powers[4];
		for (; i + 4 <= powers.size(); i += 4) {
			powers[i] = mul(powers[i - 4], step);
			powers[i + 1] = mul(powers[i - 3], step);
			powers[i + 2] = mul(powers[i - 2], step);
			powers[i + 3] = mul(powers[i - 1], step);
		}
		for (; i < powers.size(); ++i) powers[i] = mul(powers[i - 4], step);
	}
	template <class T>
	static Hash encode(T value) {
		static_assert(std::is_integral_v<T> && sizeof(T) <= 8);
		if constexpr (std::is_same_v<T, char>) return static_cast<unsigned char>(value) + 1;
		else if constexpr (sizeof(T) <= 4) {
			if constexpr (std::is_signed_v<T>) return value >= -1 ? Hash(std::int64_t(value) + 1) : Hash(std::int64_t(value) + std::int64_t(mod) + 1);
			else return Hash(value) + 1;
		} else {
			Hash result;
			if constexpr (std::is_signed_v<T>) {
				std::int64_t x = std::int64_t(value) % std::int64_t(mod);
				result = x < 0 ? Hash(x + std::int64_t(mod)) : Hash(x);
			} else result = Hash(value) % mod;
			return result == mod - 1 ? 0 : result + 1;
		}
	}
	template <class Range>
	void build_range(const Range &values) {
		assert(values.size() <= std::size_t(std::numeric_limits<int>::max()));
		int n = int(values.size());
		ensure_powers(n);
		prefix.resize(std::size_t(n) + 1);
		Hash value = 0, b = base();
		prefix[0] = 0;
		int i = 0;
		for (typename Range::value_type x : values) prefix[++i] = value = reduce(__uint128_t(value) * b + encode(x));
	}

  public:
	RollingHash() = default;
	explicit RollingHash(std::string_view s) { build(s); }
	template <class T>
	explicit RollingHash(const std::vector<T> &values) { build(values); }
	void build(std::string_view s) { build_range(s); }
	template <class T>
	void build(const std::vector<T> &values) { build_range(values); }
	int size() const { return prefix.empty() ? 0 : int(prefix.size() - 1); }
	bool empty() const { return !size(); }
	static void reserve(int n) {
		assert(n >= 0);
		ensure_powers(n);
	}
	template <class T>
	static Value single(T x) { return {encode(x), 1}; }
	static Value e() { return {}; }
	static Value op(Value left, Value right) {
		assert(left.length >= 0 && right.length >= 0 && left.length <= std::numeric_limits<int>::max() - right.length);
		if (!left.length) return right;
		if (!right.length) return left;
		return {concat(left.hash, right.hash, right.length), left.length + right.length};
	}
	Hash get() const { return prefix.empty() ? 0 : prefix.back(); }
	Hash get(int l, int r) const {
		assert(0 <= l && l <= r && r <= size());
		if (!l) return r ? prefix[r] : 0;
		Hash value = prefix[r] + mod - mul(prefix[l], powers[r - l]);
		return value >= mod ? value - mod : value;
	}
	Value value() const { return {get(), size()}; }
	Value value(int l, int r) const { return {get(l, r), r - l}; }
	static Hash concat(Hash left, Hash right, int right_length) {
		assert(left < mod && right < mod && right_length >= 0);
		ensure_powers(right_length);
		return reduce(__uint128_t(left) * powers[right_length] + right);
	}
	int lcp(int l, int r, const RollingHash &other, int other_l, int other_r) const {
		assert(0 <= l && l <= r && r <= size() && 0 <= other_l && other_l <= other_r && other_r <= other.size());
		int low = 0, high = std::min(r - l, other_r - other_l);
		while (low < high) {
			int mid = high - (high - low) / 2;
			if (get(l, l + mid) == other.get(other_l, other_l + mid)) low = mid;
			else high = mid - 1;
		}
		return low;
	}
	int lcp(int l, const RollingHash &other, int other_l) const { return lcp(l, size(), other, other_l, other.size()); }
};

#endif

#line 1 "string/rolling_hash.hpp"



#line 1 "components/splitmix64.hpp"



#include <cstdint>

inline std::uint64_t splitmix64(std::uint64_t x) {
	x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
	x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
	return x ^ (x >> 31);
}
class SplitMix64 {
	std::uint64_t state;

  public:
	explicit SplitMix64(std::uint64_t seed = 0) : state(seed) {}
	std::uint64_t operator()() { return splitmix64(state += 0x9e3779b97f4a7c15ULL); }
};


#line 5 "string/rolling_hash.hpp"
#include <algorithm>
#include <cassert>
#include <chrono>
#include <cstddef>
#line 10 "string/rolling_hash.hpp"
#include <limits>
#include <string_view>
#include <type_traits>
#include <vector>

class RollingHash {
  public:
	using Hash = std::uint64_t;
	struct Value {
		Hash hash = 0;
		int length = 0;
		bool operator==(const Value &) const = default;
	};
	static constexpr Hash mod = (Hash(1) << 61) - 1;
	static Hash base() {
		static const Hash value = splitmix64(Hash(std::chrono::steady_clock::now().time_since_epoch().count()) ^ Hash(reinterpret_cast<std::uintptr_t>(&powers))) % (mod - 512) + 256;
		return value;
	}

  private:
	inline static std::vector<Hash> powers{1};
	std::vector<Hash> prefix;
	static Hash reduce(__uint128_t value) {
		Hash result = (Hash(value) & mod) + Hash(value >> 61);
		return result >= mod ? result - mod : result;
	}
	static Hash mul(Hash a, Hash b) { return reduce(__uint128_t(a) * b); }
	static void ensure_powers(int n) {
		std::size_t old = powers.size();
		if (std::size_t(n) < old) return;
		powers.resize(std::size_t(n) + 1);
		Hash b = base();
		std::size_t i = old;
		for (; i < powers.size() && i < old + 4; ++i) powers[i] = mul(powers[i - 1], b);
		if (i == powers.size()) return;
		Hash step = powers[4];
		for (; i + 4 <= powers.size(); i += 4) {
			powers[i] = mul(powers[i - 4], step);
			powers[i + 1] = mul(powers[i - 3], step);
			powers[i + 2] = mul(powers[i - 2], step);
			powers[i + 3] = mul(powers[i - 1], step);
		}
		for (; i < powers.size(); ++i) powers[i] = mul(powers[i - 4], step);
	}
	template <class T>
	static Hash encode(T value) {
		static_assert(std::is_integral_v<T> && sizeof(T) <= 8);
		if constexpr (std::is_same_v<T, char>) return static_cast<unsigned char>(value) + 1;
		else if constexpr (sizeof(T) <= 4) {
			if constexpr (std::is_signed_v<T>) return value >= -1 ? Hash(std::int64_t(value) + 1) : Hash(std::int64_t(value) + std::int64_t(mod) + 1);
			else return Hash(value) + 1;
		} else {
			Hash result;
			if constexpr (std::is_signed_v<T>) {
				std::int64_t x = std::int64_t(value) % std::int64_t(mod);
				result = x < 0 ? Hash(x + std::int64_t(mod)) : Hash(x);
			} else result = Hash(value) % mod;
			return result == mod - 1 ? 0 : result + 1;
		}
	}
	template <class Range>
	void build_range(const Range &values) {
		assert(values.size() <= std::size_t(std::numeric_limits<int>::max()));
		int n = int(values.size());
		ensure_powers(n);
		prefix.resize(std::size_t(n) + 1);
		Hash value = 0, b = base();
		prefix[0] = 0;
		int i = 0;
		for (typename Range::value_type x : values) prefix[++i] = value = reduce(__uint128_t(value) * b + encode(x));
	}

  public:
	RollingHash() = default;
	explicit RollingHash(std::string_view s) { build(s); }
	template <class T>
	explicit RollingHash(const std::vector<T> &values) { build(values); }
	void build(std::string_view s) { build_range(s); }
	template <class T>
	void build(const std::vector<T> &values) { build_range(values); }
	int size() const { return prefix.empty() ? 0 : int(prefix.size() - 1); }
	bool empty() const { return !size(); }
	static void reserve(int n) {
		assert(n >= 0);
		ensure_powers(n);
	}
	template <class T>
	static Value single(T x) { return {encode(x), 1}; }
	static Value e() { return {}; }
	static Value op(Value left, Value right) {
		assert(left.length >= 0 && right.length >= 0 && left.length <= std::numeric_limits<int>::max() - right.length);
		if (!left.length) return right;
		if (!right.length) return left;
		return {concat(left.hash, right.hash, right.length), left.length + right.length};
	}
	Hash get() const { return prefix.empty() ? 0 : prefix.back(); }
	Hash get(int l, int r) const {
		assert(0 <= l && l <= r && r <= size());
		if (!l) return r ? prefix[r] : 0;
		Hash value = prefix[r] + mod - mul(prefix[l], powers[r - l]);
		return value >= mod ? value - mod : value;
	}
	Value value() const { return {get(), size()}; }
	Value value(int l, int r) const { return {get(l, r), r - l}; }
	static Hash concat(Hash left, Hash right, int right_length) {
		assert(left < mod && right < mod && right_length >= 0);
		ensure_powers(right_length);
		return reduce(__uint128_t(left) * powers[right_length] + right);
	}
	int lcp(int l, int r, const RollingHash &other, int other_l, int other_r) const {
		assert(0 <= l && l <= r && r <= size() && 0 <= other_l && other_l <= other_r && other_r <= other.size());
		int low = 0, high = std::min(r - l, other_r - other_l);
		while (low < high) {
			int mid = high - (high - low) / 2;
			if (get(l, l + mid) == other.get(other_l, other_l + mid)) low = mid;
			else high = mid - 1;
		}
		return low;
	}
	int lcp(int l, const RollingHash &other, int other_l) const { return lcp(l, size(), other, other_l, other.size()); }
};