rolling_hash.hpp¶
Length-aware rolling hashes modulo 2^61-1 for substring comparison, concatenation, and longest-common-extension queries.
为静态字符串或整数序列提取模 2^61-1 的带长度子串指纹，以 O(1) 比较等长子串、拼接指纹，并用二分求 LCP/LCS；适合周期与重复片段判定。
Implementation¶
#ifndef NOYA_ROLLING_HASH_HPP
#define NOYA_ROLLING_HASH_HPP 1
/// @complexity Time: O(n) build, O(1) substring hash/equality/concatenation,
/// and O(log n) longest-common-prefix/suffix queries. Space: O(n), with powers
/// shared by rolling hashes that use the default base.
#include "noya/rnd.hpp"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <memory>
#include <string>
#include <type_traits>
#include <vector>
namespace noya {
/// @brief Arithmetic modulo the Mersenne prime 2^61-1.
struct modint61 {
static constexpr std::uint64_t modulus = (UINT64_C(1) << 61) - 1;
modint61() = default;
template <class Integer,
std::enable_if_t<std::is_integral_v<Integer>, int> = 0>
explicit modint61(Integer value) {
static_assert(sizeof(Integer) <= sizeof(std::uint64_t));
if constexpr (std::is_signed_v<Integer>) {
if (value < 0) {
std::uint64_t magnitude = static_cast<std::uint64_t>(-(value + 1)) + 1;
std::uint64_t remainder = reduce(magnitude);
value_ = remainder == 0 ? 0 : modulus - remainder;
return;
}
}
value_ = reduce(static_cast<std::uint64_t>(value));
}
std::uint64_t val() const { return value_; }
friend bool operator==(const modint61 &, const modint61 &) = default;
friend modint61 operator+(modint61 left, modint61 right) {
std::uint64_t sum = left.value_ + right.value_;
if (sum >= modulus) {
sum -= modulus;
}
return raw(sum);
}
friend modint61 operator-(modint61 left, modint61 right) {
return raw(left.value_ >= right.value_
? left.value_ - right.value_
: left.value_ + modulus - right.value_);
}
friend modint61 operator*(modint61 left, modint61 right) {
__uint128_t product = static_cast<__uint128_t>(left.value_) * right.value_;
return raw(reduce(product));
}
private:
std::uint64_t value_ = 0;
static modint61 raw(std::uint64_t value) {
modint61 result;
result.value_ = value;
return result;
}
static std::uint64_t reduce(__uint128_t value) {
std::uint64_t folded = static_cast<std::uint64_t>(value & modulus) +
static_cast<std::uint64_t>(value >> 61);
return folded >= modulus ? folded - modulus : folded;
}
};
/// @brief Return the process-wide randomized base used by default hashes.
inline std::uint64_t rolling_hash_base() {
constexpr std::uint64_t minimum = UINT64_C(1) << 30;
constexpr std::uint64_t random_mask = (UINT64_C(1) << 60) - 1;
static const std::uint64_t base =
minimum + (internal::gen_values()() & random_mask);
return base;
}
namespace internal {
template <class Hash> class rolling_hash_context {
public:
explicit rolling_hash_context(std::uint64_t base) : base_(base) {
assert(base_ != Hash(0) && base_ != Hash(1) && base_ != Hash(-1));
powers_.emplace_back(1);
}
const Hash &base() const { return base_; }
const Hash &power(int exponent) {
assert(exponent >= 0);
while (int(powers_.size()) <= exponent) {
powers_.push_back(powers_.back() * base_);
}
return powers_[exponent];
}
private:
Hash base_;
std::vector<Hash> powers_;
};
template <class Hash>
std::shared_ptr<rolling_hash_context<Hash>> default_rolling_hash_context() {
static auto context =
std::make_shared<rolling_hash_context<Hash>>(rolling_hash_base());
return context;
}
template <class T> auto normalize_hash_symbol(const T &value) {
using raw_type = std::remove_cv_t<T>;
if constexpr (std::is_same_v<raw_type, char> ||
std::is_same_v<raw_type, signed char> ||
std::is_same_v<raw_type, unsigned char>) {
return static_cast<unsigned char>(value);
} else {
return value;
}
}
template <class Hash> int hash_size(const Hash &hash) {
if constexpr (requires { hash.size(); }) {
return hash.size();
} else {
return hash.n;
}
}
template <class First, class Second>
void assert_compatible_hashes(const First &first, const Second &second) {
if constexpr (requires { first.compatible_with(second); }) {
assert(first.compatible_with(second));
}
}
} // namespace internal
/// @brief A substring hash token that also records its sequence length.
template <class Hash> struct rolling_hash_value {
Hash hash{};
int length = 0;
friend bool operator==(const rolling_hash_value &,
const rolling_hash_value &) = default;
};
/// @brief Prefix rolling hash with length-aware substring and concatenation
/// tokens. The default modulus is the Mersenne prime 2^61-1.
/// @details Prefixes satisfy H[i + 1] = H[i] * base + value[i], hence
/// hash([l, r)) = H[r] - H[l] * base^(r-l). A token stores its length so hashes
/// concatenate as left * base^(right.length) + right without ambiguity between
/// equal numeric hashes of different lengths.
template <class Symbol, class Hash = modint61> class rolling_hash {
public:
using symbol_type = Symbol;
using hash_type = Hash;
using value_type = rolling_hash_value<Hash>;
rolling_hash() : context_(internal::default_rolling_hash_context<Hash>()) {
prefix_.emplace_back();
}
explicit rolling_hash(std::uint64_t base)
: context_(std::make_shared<context_type>(base)), prefix_(1) {}
explicit rolling_hash(const std::vector<Symbol> &values) : rolling_hash() {
build(values);
}
rolling_hash(const std::vector<Symbol> &values, std::uint64_t base)
: rolling_hash(base) {
build(values);
}
explicit rolling_hash(const std::string &values) : rolling_hash() {
build(values);
}
rolling_hash(const std::string &values, std::uint64_t base)
: rolling_hash(base) {
build(values);
}
void build(const std::vector<Symbol> &values) {
build(values.begin(), values.end());
}
void build(const std::string &values) { build(values.begin(), values.end()); }
int size() const { return int(prefix_.size()) - 1; }
bool empty() const { return size() == 0; }
const Hash &base() const { return context_->base(); }
template <class OtherSymbol>
bool compatible_with(const rolling_hash<OtherSymbol, Hash> &other) const {
return base() == other.base();
}
/// @brief Return a length-aware hash of [left, right).
value_type prod(int left, int right) const {
assert(0 <= left && left <= right && right <= size());
int length = right - left;
return {prefix_[right] - prefix_[left] * context_->power(length), length};
}
value_type slice(int left, int right) const { return prod(left, right); }
/// @brief Return the hash token of left followed by right. Both tokens must
/// have been computed with this object's base.
value_type concat(const value_type &left, const value_type &right) const {
assert(left.length >= 0 && right.length >= 0);
return {left.hash * context_->power(right.length) + right.hash,
left.length + right.length};
}
private:
using context_type = internal::rolling_hash_context<Hash>;
std::shared_ptr<context_type> context_;
std::vector<Hash> prefix_;
template <class Iterator> void build(Iterator first, Iterator last) {
prefix_.assign(1, Hash{});
for (; first != last; ++first) {
Hash symbol(internal::normalize_hash_symbol(Symbol(*first)));
prefix_.push_back(prefix_.back() * base() + symbol);
}
context_->power(size());
}
};
/// @brief Longest common prefix of suffixes beginning at first_index and
/// second_index.
template <class FirstHash, class SecondHash>
int lcp(const FirstHash &first, int first_index, const SecondHash &second,
int second_index) {
int first_size = internal::hash_size(first);
int second_size = internal::hash_size(second);
assert(0 <= first_index && first_index <= first_size);
assert(0 <= second_index && second_index <= second_size);
internal::assert_compatible_hashes(first, second);
int good = 0;
int bad = std::min(first_size - first_index, second_size - second_index) + 1;
while (bad - good > 1) {
int middle = (good + bad) / 2;
if (first.prod(first_index, first_index + middle) ==
second.prod(second_index, second_index + middle)) {
good = middle;
} else {
bad = middle;
}
}
return good;
}
/// @brief Longest common suffix ending at first_index and second_index. Index
/// -1 denotes the empty prefix before a sequence.
template <class FirstHash, class SecondHash>
int lcs(const FirstHash &first, int first_index, const SecondHash &second,
int second_index) {
int first_size = internal::hash_size(first);
int second_size = internal::hash_size(second);
assert(-1 <= first_index && first_index < first_size);
assert(-1 <= second_index && second_index < second_size);
internal::assert_compatible_hashes(first, second);
int good = 0;
int bad = std::min(first_index + 1, second_index + 1) + 1;
while (bad - good > 1) {
int middle = (good + bad) / 2;
if (first.prod(first_index + 1 - middle, first_index + 1) ==
second.prod(second_index + 1 - middle, second_index + 1)) {
good = middle;
} else {
bad = middle;
}
}
return good;
}
/// @brief Check whether [first_left, first_right) equals
/// [second_left, second_right) in O(1).
template <class FirstHash, class SecondHash>
bool same(const FirstHash &first, int first_left, int first_right,
const SecondHash &second, int second_left, int second_right) {
int first_size = internal::hash_size(first);
int second_size = internal::hash_size(second);
assert(0 <= first_left && first_left <= first_right &&
first_right <= first_size);
assert(0 <= second_left && second_left <= second_right &&
second_right <= second_size);
internal::assert_compatible_hashes(first, second);
return first_right - first_left == second_right - second_left &&
first.prod(first_left, first_right) ==
second.prod(second_left, second_right);
}
} // namespace noya
#endif // NOYA_ROLLING_HASH_HPP
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <ctime>
#include <memory>
#include <numeric>
#include <random>
#include <string>
#include <type_traits>
#include <vector>
/// @complexity Time: O(n) build, O(1) substring hash/equality/concatenation,
/// and O(log n) longest-common-prefix/suffix queries. Space: O(n), with powers
/// shared by rolling hashes that use the default base.
/// @complexity Time: O(n) per generated permutation/tree; O(1) scalar draws.
/// Space: O(n) returned data.
/// @brief Random permutation, hash-value, and rooted-tree generators backed by
/// a shared 64-bit Mersenne Twister.
namespace noya {
using ull = unsigned long long;
namespace internal {
inline std::mt19937_64 &gen_values() {
static std::mt19937_64 gen(time(0));
return gen;
}
} // namespace internal
inline std::vector<int> random_permutation(int N) {
std::vector<int> p(N);
std::iota(p.begin(), p.end(), 0);
std::shuffle(p.begin(), p.end(), internal::gen_values());
return p;
}
inline std::vector<ull> random_hash_values(int N) {
std::vector<ull> X(N);
std::generate(X.begin(), X.end(), internal::gen_values());
return X;
}
inline std::vector<std::vector<int>> random_tree(int N) {
std::vector<std::vector<int>> g(N);
for (int i = 1; i < N; i++) {
int p = internal::gen_values()() % i;
g[p].push_back(i);
}
return g;
}
} // namespace noya
namespace noya {
/// @brief Arithmetic modulo the Mersenne prime 2^61-1.
struct modint61 {
static constexpr std::uint64_t modulus = (UINT64_C(1) << 61) - 1;
modint61() = default;
template <class Integer,
std::enable_if_t<std::is_integral_v<Integer>, int> = 0>
explicit modint61(Integer value) {
static_assert(sizeof(Integer) <= sizeof(std::uint64_t));
if constexpr (std::is_signed_v<Integer>) {
if (value < 0) {
std::uint64_t magnitude = static_cast<std::uint64_t>(-(value + 1)) + 1;
std::uint64_t remainder = reduce(magnitude);
value_ = remainder == 0 ? 0 : modulus - remainder;
return;
}
}
value_ = reduce(static_cast<std::uint64_t>(value));
}
std::uint64_t val() const { return value_; }
friend bool operator==(const modint61 &, const modint61 &) = default;
friend modint61 operator+(modint61 left, modint61 right) {
std::uint64_t sum = left.value_ + right.value_;
if (sum >= modulus) {
sum -= modulus;
}
return raw(sum);
}
friend modint61 operator-(modint61 left, modint61 right) {
return raw(left.value_ >= right.value_
? left.value_ - right.value_
: left.value_ + modulus - right.value_);
}
friend modint61 operator*(modint61 left, modint61 right) {
__uint128_t product = static_cast<__uint128_t>(left.value_) * right.value_;
return raw(reduce(product));
}
private:
std::uint64_t value_ = 0;
static modint61 raw(std::uint64_t value) {
modint61 result;
result.value_ = value;
return result;
}
static std::uint64_t reduce(__uint128_t value) {
std::uint64_t folded = static_cast<std::uint64_t>(value & modulus) +
static_cast<std::uint64_t>(value >> 61);
return folded >= modulus ? folded - modulus : folded;
}
};
/// @brief Return the process-wide randomized base used by default hashes.
inline std::uint64_t rolling_hash_base() {
constexpr std::uint64_t minimum = UINT64_C(1) << 30;
constexpr std::uint64_t random_mask = (UINT64_C(1) << 60) - 1;
static const std::uint64_t base =
minimum + (internal::gen_values()() & random_mask);
return base;
}
namespace internal {
template <class Hash> class rolling_hash_context {
public:
explicit rolling_hash_context(std::uint64_t base) : base_(base) {
assert(base_ != Hash(0) && base_ != Hash(1) && base_ != Hash(-1));
powers_.emplace_back(1);
}
const Hash &base() const { return base_; }
const Hash &power(int exponent) {
assert(exponent >= 0);
while (int(powers_.size()) <= exponent) {
powers_.push_back(powers_.back() * base_);
}
return powers_[exponent];
}
private:
Hash base_;
std::vector<Hash> powers_;
};
template <class Hash>
std::shared_ptr<rolling_hash_context<Hash>> default_rolling_hash_context() {
static auto context =
std::make_shared<rolling_hash_context<Hash>>(rolling_hash_base());
return context;
}
template <class T> auto normalize_hash_symbol(const T &value) {
using raw_type = std::remove_cv_t<T>;
if constexpr (std::is_same_v<raw_type, char> ||
std::is_same_v<raw_type, signed char> ||
std::is_same_v<raw_type, unsigned char>) {
return static_cast<unsigned char>(value);
} else {
return value;
}
}
template <class Hash> int hash_size(const Hash &hash) {
if constexpr (requires { hash.size(); }) {
return hash.size();
} else {
return hash.n;
}
}
template <class First, class Second>
void assert_compatible_hashes(const First &first, const Second &second) {
if constexpr (requires { first.compatible_with(second); }) {
assert(first.compatible_with(second));
}
}
} // namespace internal
/// @brief A substring hash token that also records its sequence length.
template <class Hash> struct rolling_hash_value {
Hash hash{};
int length = 0;
friend bool operator==(const rolling_hash_value &,
const rolling_hash_value &) = default;
};
/// @brief Prefix rolling hash with length-aware substring and concatenation
/// tokens. The default modulus is the Mersenne prime 2^61-1.
/// @details Prefixes satisfy H[i + 1] = H[i] * base + value[i], hence
/// hash([l, r)) = H[r] - H[l] * base^(r-l). A token stores its length so hashes
/// concatenate as left * base^(right.length) + right without ambiguity between
/// equal numeric hashes of different lengths.
template <class Symbol, class Hash = modint61> class rolling_hash {
public:
using symbol_type = Symbol;
using hash_type = Hash;
using value_type = rolling_hash_value<Hash>;
rolling_hash() : context_(internal::default_rolling_hash_context<Hash>()) {
prefix_.emplace_back();
}
explicit rolling_hash(std::uint64_t base)
: context_(std::make_shared<context_type>(base)), prefix_(1) {}
explicit rolling_hash(const std::vector<Symbol> &values) : rolling_hash() {
build(values);
}
rolling_hash(const std::vector<Symbol> &values, std::uint64_t base)
: rolling_hash(base) {
build(values);
}
explicit rolling_hash(const std::string &values) : rolling_hash() {
build(values);
}
rolling_hash(const std::string &values, std::uint64_t base)
: rolling_hash(base) {
build(values);
}
void build(const std::vector<Symbol> &values) {
build(values.begin(), values.end());
}
void build(const std::string &values) { build(values.begin(), values.end()); }
int size() const { return int(prefix_.size()) - 1; }
bool empty() const { return size() == 0; }
const Hash &base() const { return context_->base(); }
template <class OtherSymbol>
bool compatible_with(const rolling_hash<OtherSymbol, Hash> &other) const {
return base() == other.base();
}
/// @brief Return a length-aware hash of [left, right).
value_type prod(int left, int right) const {
assert(0 <= left && left <= right && right <= size());
int length = right - left;
return {prefix_[right] - prefix_[left] * context_->power(length), length};
}
value_type slice(int left, int right) const { return prod(left, right); }
/// @brief Return the hash token of left followed by right. Both tokens must
/// have been computed with this object's base.
value_type concat(const value_type &left, const value_type &right) const {
assert(left.length >= 0 && right.length >= 0);
return {left.hash * context_->power(right.length) + right.hash,
left.length + right.length};
}
private:
using context_type = internal::rolling_hash_context<Hash>;
std::shared_ptr<context_type> context_;
std::vector<Hash> prefix_;
template <class Iterator> void build(Iterator first, Iterator last) {
prefix_.assign(1, Hash{});
for (; first != last; ++first) {
Hash symbol(internal::normalize_hash_symbol(Symbol(*first)));
prefix_.push_back(prefix_.back() * base() + symbol);
}
context_->power(size());
}
};
/// @brief Longest common prefix of suffixes beginning at first_index and
/// second_index.
template <class FirstHash, class SecondHash>
int lcp(const FirstHash &first, int first_index, const SecondHash &second,
int second_index) {
int first_size = internal::hash_size(first);
int second_size = internal::hash_size(second);
assert(0 <= first_index && first_index <= first_size);
assert(0 <= second_index && second_index <= second_size);
internal::assert_compatible_hashes(first, second);
int good = 0;
int bad = std::min(first_size - first_index, second_size - second_index) + 1;
while (bad - good > 1) {
int middle = (good + bad) / 2;
if (first.prod(first_index, first_index + middle) ==
second.prod(second_index, second_index + middle)) {
good = middle;
} else {
bad = middle;
}
}
return good;
}
/// @brief Longest common suffix ending at first_index and second_index. Index
/// -1 denotes the empty prefix before a sequence.
template <class FirstHash, class SecondHash>
int lcs(const FirstHash &first, int first_index, const SecondHash &second,
int second_index) {
int first_size = internal::hash_size(first);
int second_size = internal::hash_size(second);
assert(-1 <= first_index && first_index < first_size);
assert(-1 <= second_index && second_index < second_size);
internal::assert_compatible_hashes(first, second);
int good = 0;
int bad = std::min(first_index + 1, second_index + 1) + 1;
while (bad - good > 1) {
int middle = (good + bad) / 2;
if (first.prod(first_index + 1 - middle, first_index + 1) ==
second.prod(second_index + 1 - middle, second_index + 1)) {
good = middle;
} else {
bad = middle;
}
}
return good;
}
/// @brief Check whether [first_left, first_right) equals
/// [second_left, second_right) in O(1).
template <class FirstHash, class SecondHash>
bool same(const FirstHash &first, int first_left, int first_right,
const SecondHash &second, int second_left, int second_right) {
int first_size = internal::hash_size(first);
int second_size = internal::hash_size(second);
assert(0 <= first_left && first_left <= first_right &&
first_right <= first_size);
assert(0 <= second_left && second_left <= second_right &&
second_right <= second_size);
internal::assert_compatible_hashes(first, second);
return first_right - first_left == second_right - second_left &&
first.prod(first_left, first_right) ==
second.prod(second_left, second_right);
}
} // namespace noya