rolling_hash.hpp¶
为静态字符串或整数序列提取模 \(2^{61}-1\) 的带长度子串指纹，以 \(O(1)\) 比较等长子串、拼接指纹，并用二分求 LCP/LCS；适合周期与重复片段判定。
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.
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @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 mod = (UINT64_C(1) << 61) - 1;
modint61() = default;
template <class Integer,
std::enable_if_t<std::is_integral_v<Integer>, int> = 0>
explicit modint61(Integer va1) {
static_assert(sizeof(Integer) <= sizeof(std::uint64_t));
if constexpr (std::is_signed_v<Integer>) {
if (va1 < 0) {
std::uint64_t mag = static_cast<std::uint64_t>(-(va1 + 1)) + 1;
std::uint64_t rem = reduce(mag);
v_ = rem == 0 ? 0 : mod - rem;
return;
}
}
v_ = reduce(static_cast<std::uint64_t>(va1));
}
std::uint64_t val() const { return v_; }
friend bool operator==(const modint61 &, const modint61 &) = default;
friend modint61 operator+(modint61 l, modint61 r) {
std::uint64_t sum = l.v_ + r.v_;
if (sum >= mod) {
sum -= mod;
}
return raw(sum);
}
friend modint61 operator-(modint61 l, modint61 r) {
return raw(l.v_ >= r.v_ ? l.v_ - r.v_ : l.v_ + mod - r.v_);
}
friend modint61 operator*(modint61 l, modint61 r) {
__uint128_t prd = static_cast<__uint128_t>(l.v_) * r.v_;
return raw(reduce(prd));
}
private:
std::uint64_t v_ = 0;
static modint61 raw(std::uint64_t va1) {
modint61 res;
res.v_ = va1;
return res;
}
static std::uint64_t reduce(__uint128_t va1) {
std::uint64_t fld = static_cast<std::uint64_t>(va1 & mod) +
static_cast<std::uint64_t>(va1 >> 61);
return fld >= mod ? fld - mod : fld;
}
};
/// @brief Return the process-wide randomized base used by default hashes.
inline std::uint64_t rolling_hash_base() {
constexpr std::uint64_t mn = UINT64_C(1) << 30;
constexpr std::uint64_t rm = (UINT64_C(1) << 60) - 1;
static const std::uint64_t bas = mn + (internal::gen_values()() & rm);
return bas;
}
namespace internal {
template <class Hash> class rolling_hash_context {
public:
explicit rolling_hash_context(std::uint64_t bas) : b_(bas) {
assert(b_ != Hash(0) && b_ != Hash(1) && b_ != Hash(-1));
pw_.emplace_back(1);
}
const Hash &base() const { return b_; }
const Hash &power(int k) {
assert(k >= 0);
while (int(pw_.size()) <= k) {
pw_.push_back(pw_.back() * b_);
}
return pw_[k];
}
private:
Hash b_;
std::vector<Hash> pw_;
};
template <class Hash>
std::shared_ptr<rolling_hash_context<Hash>> default_rolling_hash_context() {
static auto ctx =
std::make_shared<rolling_hash_context<Hash>>(rolling_hash_base());
return ctx;
}
template <class T> auto normalize_hash_symbol(const T &va1) {
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>(va1);
} else {
return va1;
}
}
template <class Hash> int hash_size(const Hash &h) {
if constexpr (requires { h.size(); }) {
return h.size();
} else {
return h.n;
}
}
template <class First, class Second>
void assert_compatible_hashes(const First &a, const Second &b) {
if constexpr (requires { a.compatible_with(b); }) {
assert(a.compatible_with(b));
}
}
} // namespace internal
/// @brief A substring hash token that also records its sequence length.
template <class Hash> struct rolling_hash_value {
Hash h{};
int len = 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] * B + s[i] for symbols s and base B, hence
/// hash([l, r)) = H[r] - H[l] * B^(r-l). A token stores its length so hashes
/// concatenate as l.h * B^(r.len) + r.h 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() : ct_(internal::default_rolling_hash_context<Hash>()) {
pr_.emplace_back();
}
explicit rolling_hash(std::uint64_t bas)
: ct_(std::make_shared<context_type>(bas)), pr_(1) {}
explicit rolling_hash(const std::vector<Symbol> &va2) : rolling_hash() {
build(va2);
}
rolling_hash(const std::vector<Symbol> &va2, std::uint64_t bas)
: rolling_hash(bas) {
build(va2);
}
explicit rolling_hash(const std::string &va2) : rolling_hash() { build(va2); }
rolling_hash(const std::string &va2, std::uint64_t bas) : rolling_hash(bas) {
build(va2);
}
void build(const std::vector<Symbol> &va2) { build(va2.begin(), va2.end()); }
void build(const std::string &va2) { build(va2.begin(), va2.end()); }
int size() const { return int(pr_.size()) - 1; }
bool empty() const { return size() == 0; }
const Hash &base() const { return ct_->base(); }
template <class OtherSymbol>
bool compatible_with(const rolling_hash<OtherSymbol, Hash> &rhs) const {
return base() == rhs.base();
}
/// @brief Return a length-aware hash of [l, r).
value_type prod(int l, int r) const {
assert(0 <= l && l <= r && r <= size());
int len = r - l;
return {pr_[r] - pr_[l] * ct_->power(len), len};
}
value_type slice(int l, int r) const { return prod(l, r); }
/// @brief Return the hash token of l followed by r. Both tokens must
/// have been computed with this object's base.
value_type concat(const value_type &l, const value_type &r) const {
assert(l.len >= 0 && r.len >= 0);
return {l.h * ct_->power(r.len) + r.h, l.len + r.len};
}
private:
using context_type = internal::rolling_hash_context<Hash>;
std::shared_ptr<context_type> ct_;
std::vector<Hash> pr_;
template <class Iterator> void build(Iterator a, Iterator lst) {
pr_.assign(1, Hash{});
for (; a != lst; ++a) {
Hash c(internal::normalize_hash_symbol(Symbol(*a)));
pr_.push_back(pr_.back() * base() + c);
}
ct_->power(size());
}
};
/// @brief Longest common prefix of suffixes beginning at i1 and
/// i2.
template <class FirstHash, class SecondHash>
int lcp(const FirstHash &a, int i1, const SecondHash &b, int i2) {
int n1 = internal::hash_size(a);
int n2 = internal::hash_size(b);
assert(0 <= i1 && i1 <= n1);
assert(0 <= i2 && i2 <= n2);
internal::assert_compatible_hashes(a, b);
int ok = 0;
int bad = std::min(n1 - i1, n2 - i2) + 1;
while (bad - ok > 1) {
int mid = (ok + bad) / 2;
if (a.prod(i1, i1 + mid) == b.prod(i2, i2 + mid)) {
ok = mid;
} else {
bad = mid;
}
}
return ok;
}
/// @brief Longest common suffix ending at i1 and i2. Index
/// -1 denotes the empty prefix before a sequence.
template <class FirstHash, class SecondHash>
int lcs(const FirstHash &a, int i1, const SecondHash &b, int i2) {
int n1 = internal::hash_size(a);
int n2 = internal::hash_size(b);
assert(-1 <= i1 && i1 < n1);
assert(-1 <= i2 && i2 < n2);
internal::assert_compatible_hashes(a, b);
int ok = 0;
int bad = std::min(i1 + 1, i2 + 1) + 1;
while (bad - ok > 1) {
int mid = (ok + bad) / 2;
if (a.prod(i1 + 1 - mid, i1 + 1) == b.prod(i2 + 1 - mid, i2 + 1)) {
ok = mid;
} else {
bad = mid;
}
}
return ok;
}
/// @brief Check whether [l1, r1) equals
/// [l2, r2) in O(1).
template <class FirstHash, class SecondHash>
bool same(const FirstHash &a, int l1, int r1, const SecondHash &b, int l2,
int r2) {
int n1 = internal::hash_size(a);
int n2 = internal::hash_size(b);
assert(0 <= l1 && l1 <= r1 && r1 <= n1);
assert(0 <= l2 && l2 <= r2 && r2 <= n2);
internal::assert_compatible_hashes(a, b);
return r1 - l1 == r2 - l2 && a.prod(l1, r1) == b.prod(l2, r2);
}
} // namespace noya
#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 mod = (UINT64_C(1) << 61) - 1;
modint61() = default;
template <class Integer,
std::enable_if_t<std::is_integral_v<Integer>, int> = 0>
explicit modint61(Integer va1) {
static_assert(sizeof(Integer) <= sizeof(std::uint64_t));
if constexpr (std::is_signed_v<Integer>) {
if (va1 < 0) {
std::uint64_t mag = static_cast<std::uint64_t>(-(va1 + 1)) + 1;
std::uint64_t rem = reduce(mag);
v_ = rem == 0 ? 0 : mod - rem;
return;
}
}
v_ = reduce(static_cast<std::uint64_t>(va1));
}
std::uint64_t val() const { return v_; }
friend bool operator==(const modint61 &, const modint61 &) = default;
friend modint61 operator+(modint61 l, modint61 r) {
std::uint64_t sum = l.v_ + r.v_;
if (sum >= mod) {
sum -= mod;
}
return raw(sum);
}
friend modint61 operator-(modint61 l, modint61 r) {
return raw(l.v_ >= r.v_ ? l.v_ - r.v_ : l.v_ + mod - r.v_);
}
friend modint61 operator*(modint61 l, modint61 r) {
__uint128_t prd = static_cast<__uint128_t>(l.v_) * r.v_;
return raw(reduce(prd));
}
private:
std::uint64_t v_ = 0;
static modint61 raw(std::uint64_t va1) {
modint61 res;
res.v_ = va1;
return res;
}
static std::uint64_t reduce(__uint128_t va1) {
std::uint64_t fld = static_cast<std::uint64_t>(va1 & mod) +
static_cast<std::uint64_t>(va1 >> 61);
return fld >= mod ? fld - mod : fld;
}
};
/// @brief Return the process-wide randomized base used by default hashes.
inline std::uint64_t rolling_hash_base() {
constexpr std::uint64_t mn = UINT64_C(1) << 30;
constexpr std::uint64_t rm = (UINT64_C(1) << 60) - 1;
static const std::uint64_t bas = mn + (internal::gen_values()() & rm);
return bas;
}
namespace internal {
template <class Hash> class rolling_hash_context {
public:
explicit rolling_hash_context(std::uint64_t bas) : b_(bas) {
assert(b_ != Hash(0) && b_ != Hash(1) && b_ != Hash(-1));
pw_.emplace_back(1);
}
const Hash &base() const { return b_; }
const Hash &power(int k) {
assert(k >= 0);
while (int(pw_.size()) <= k) {
pw_.push_back(pw_.back() * b_);
}
return pw_[k];
}
private:
Hash b_;
std::vector<Hash> pw_;
};
template <class Hash>
std::shared_ptr<rolling_hash_context<Hash>> default_rolling_hash_context() {
static auto ctx =
std::make_shared<rolling_hash_context<Hash>>(rolling_hash_base());
return ctx;
}
template <class T> auto normalize_hash_symbol(const T &va1) {
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>(va1);
} else {
return va1;
}
}
template <class Hash> int hash_size(const Hash &h) {
if constexpr (requires { h.size(); }) {
return h.size();
} else {
return h.n;
}
}
template <class First, class Second>
void assert_compatible_hashes(const First &a, const Second &b) {
if constexpr (requires { a.compatible_with(b); }) {
assert(a.compatible_with(b));
}
}
} // namespace internal
/// @brief A substring hash token that also records its sequence length.
template <class Hash> struct rolling_hash_value {
Hash h{};
int len = 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] * B + s[i] for symbols s and base B, hence
/// hash([l, r)) = H[r] - H[l] * B^(r-l). A token stores its length so hashes
/// concatenate as l.h * B^(r.len) + r.h 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() : ct_(internal::default_rolling_hash_context<Hash>()) {
pr_.emplace_back();
}
explicit rolling_hash(std::uint64_t bas)
: ct_(std::make_shared<context_type>(bas)), pr_(1) {}
explicit rolling_hash(const std::vector<Symbol> &va2) : rolling_hash() {
build(va2);
}
rolling_hash(const std::vector<Symbol> &va2, std::uint64_t bas)
: rolling_hash(bas) {
build(va2);
}
explicit rolling_hash(const std::string &va2) : rolling_hash() { build(va2); }
rolling_hash(const std::string &va2, std::uint64_t bas) : rolling_hash(bas) {
build(va2);
}
void build(const std::vector<Symbol> &va2) { build(va2.begin(), va2.end()); }
void build(const std::string &va2) { build(va2.begin(), va2.end()); }
int size() const { return int(pr_.size()) - 1; }
bool empty() const { return size() == 0; }
const Hash &base() const { return ct_->base(); }
template <class OtherSymbol>
bool compatible_with(const rolling_hash<OtherSymbol, Hash> &rhs) const {
return base() == rhs.base();
}
/// @brief Return a length-aware hash of [l, r).
value_type prod(int l, int r) const {
assert(0 <= l && l <= r && r <= size());
int len = r - l;
return {pr_[r] - pr_[l] * ct_->power(len), len};
}
value_type slice(int l, int r) const { return prod(l, r); }
/// @brief Return the hash token of l followed by r. Both tokens must
/// have been computed with this object's base.
value_type concat(const value_type &l, const value_type &r) const {
assert(l.len >= 0 && r.len >= 0);
return {l.h * ct_->power(r.len) + r.h, l.len + r.len};
}
private:
using context_type = internal::rolling_hash_context<Hash>;
std::shared_ptr<context_type> ct_;
std::vector<Hash> pr_;
template <class Iterator> void build(Iterator a, Iterator lst) {
pr_.assign(1, Hash{});
for (; a != lst; ++a) {
Hash c(internal::normalize_hash_symbol(Symbol(*a)));
pr_.push_back(pr_.back() * base() + c);
}
ct_->power(size());
}
};
/// @brief Longest common prefix of suffixes beginning at i1 and
/// i2.
template <class FirstHash, class SecondHash>
int lcp(const FirstHash &a, int i1, const SecondHash &b, int i2) {
int n1 = internal::hash_size(a);
int n2 = internal::hash_size(b);
assert(0 <= i1 && i1 <= n1);
assert(0 <= i2 && i2 <= n2);
internal::assert_compatible_hashes(a, b);
int ok = 0;
int bad = std::min(n1 - i1, n2 - i2) + 1;
while (bad - ok > 1) {
int mid = (ok + bad) / 2;
if (a.prod(i1, i1 + mid) == b.prod(i2, i2 + mid)) {
ok = mid;
} else {
bad = mid;
}
}
return ok;
}
/// @brief Longest common suffix ending at i1 and i2. Index
/// -1 denotes the empty prefix before a sequence.
template <class FirstHash, class SecondHash>
int lcs(const FirstHash &a, int i1, const SecondHash &b, int i2) {
int n1 = internal::hash_size(a);
int n2 = internal::hash_size(b);
assert(-1 <= i1 && i1 < n1);
assert(-1 <= i2 && i2 < n2);
internal::assert_compatible_hashes(a, b);
int ok = 0;
int bad = std::min(i1 + 1, i2 + 1) + 1;
while (bad - ok > 1) {
int mid = (ok + bad) / 2;
if (a.prod(i1 + 1 - mid, i1 + 1) == b.prod(i2 + 1 - mid, i2 + 1)) {
ok = mid;
} else {
bad = mid;
}
}
return ok;
}
/// @brief Check whether [l1, r1) equals
/// [l2, r2) in O(1).
template <class FirstHash, class SecondHash>
bool same(const FirstHash &a, int l1, int r1, const SecondHash &b, int l2,
int r2) {
int n1 = internal::hash_size(a);
int n2 = internal::hash_size(b);
assert(0 <= l1 && l1 <= r1 && r1 <= n1);
assert(0 <= l2 && l2 <= r2 && r2 <= n2);
internal::assert_compatible_hashes(a, b);
return r1 - l1 == r2 - l2 && a.prod(l1, r1) == b.prod(l2, r2);
}
} // 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 mod = (UINT64_C(1) << 61) - 1;
modint61() = default;
template <class Integer,
std::enable_if_t<std::is_integral_v<Integer>, int> = 0>
explicit modint61(Integer va1) {
static_assert(sizeof(Integer) <= sizeof(std::uint64_t));
if constexpr (std::is_signed_v<Integer>) {
if (va1 < 0) {
std::uint64_t mag = static_cast<std::uint64_t>(-(va1 + 1)) + 1;
std::uint64_t rem = reduce(mag);
v_ = rem == 0 ? 0 : mod - rem;
return;
}
}
v_ = reduce(static_cast<std::uint64_t>(va1));
}
std::uint64_t val() const { return v_; }
friend bool operator==(const modint61 &, const modint61 &) = default;
friend modint61 operator+(modint61 l, modint61 r) {
std::uint64_t sum = l.v_ + r.v_;
if (sum >= mod) {
sum -= mod;
}
return raw(sum);
}
friend modint61 operator-(modint61 l, modint61 r) {
return raw(l.v_ >= r.v_ ? l.v_ - r.v_ : l.v_ + mod - r.v_);
}
friend modint61 operator*(modint61 l, modint61 r) {
__uint128_t prd = static_cast<__uint128_t>(l.v_) * r.v_;
return raw(reduce(prd));
}
private:
std::uint64_t v_ = 0;
static modint61 raw(std::uint64_t va1) {
modint61 res;
res.v_ = va1;
return res;
}
static std::uint64_t reduce(__uint128_t va1) {
std::uint64_t fld = static_cast<std::uint64_t>(va1 & mod) +
static_cast<std::uint64_t>(va1 >> 61);
return fld >= mod ? fld - mod : fld;
}
};
/// @brief Return the process-wide randomized base used by default hashes.
inline std::uint64_t rolling_hash_base() {
constexpr std::uint64_t mn = UINT64_C(1) << 30;
constexpr std::uint64_t rm = (UINT64_C(1) << 60) - 1;
static const std::uint64_t bas = mn + (internal::gen_values()() & rm);
return bas;
}
namespace internal {
template <class Hash> class rolling_hash_context {
public:
explicit rolling_hash_context(std::uint64_t bas) : b_(bas) {
assert(b_ != Hash(0) && b_ != Hash(1) && b_ != Hash(-1));
pw_.emplace_back(1);
}
const Hash &base() const { return b_; }
const Hash &power(int k) {
assert(k >= 0);
while (int(pw_.size()) <= k) {
pw_.push_back(pw_.back() * b_);
}
return pw_[k];
}
private:
Hash b_;
std::vector<Hash> pw_;
};
template <class Hash>
std::shared_ptr<rolling_hash_context<Hash>> default_rolling_hash_context() {
static auto ctx =
std::make_shared<rolling_hash_context<Hash>>(rolling_hash_base());
return ctx;
}
template <class T> auto normalize_hash_symbol(const T &va1) {
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>(va1);
} else {
return va1;
}
}
template <class Hash> int hash_size(const Hash &h) {
if constexpr (requires { h.size(); }) {
return h.size();
} else {
return h.n;
}
}
template <class First, class Second>
void assert_compatible_hashes(const First &a, const Second &b) {
if constexpr (requires { a.compatible_with(b); }) {
assert(a.compatible_with(b));
}
}
} // namespace internal
/// @brief A substring hash token that also records its sequence length.
template <class Hash> struct rolling_hash_value {
Hash h{};
int len = 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] * B + s[i] for symbols s and base B, hence
/// hash([l, r)) = H[r] - H[l] * B^(r-l). A token stores its length so hashes
/// concatenate as l.h * B^(r.len) + r.h 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() : ct_(internal::default_rolling_hash_context<Hash>()) {
pr_.emplace_back();
}
explicit rolling_hash(std::uint64_t bas)
: ct_(std::make_shared<context_type>(bas)), pr_(1) {}
explicit rolling_hash(const std::vector<Symbol> &va2) : rolling_hash() {
build(va2);
}
rolling_hash(const std::vector<Symbol> &va2, std::uint64_t bas)
: rolling_hash(bas) {
build(va2);
}
explicit rolling_hash(const std::string &va2) : rolling_hash() { build(va2); }
rolling_hash(const std::string &va2, std::uint64_t bas) : rolling_hash(bas) {
build(va2);
}
void build(const std::vector<Symbol> &va2) { build(va2.begin(), va2.end()); }
void build(const std::string &va2) { build(va2.begin(), va2.end()); }
int size() const { return int(pr_.size()) - 1; }
bool empty() const { return size() == 0; }
const Hash &base() const { return ct_->base(); }
template <class OtherSymbol>
bool compatible_with(const rolling_hash<OtherSymbol, Hash> &rhs) const {
return base() == rhs.base();
}
/// @brief Return a length-aware hash of [l, r).
value_type prod(int l, int r) const {
assert(0 <= l && l <= r && r <= size());
int len = r - l;
return {pr_[r] - pr_[l] * ct_->power(len), len};
}
value_type slice(int l, int r) const { return prod(l, r); }
/// @brief Return the hash token of l followed by r. Both tokens must
/// have been computed with this object's base.
value_type concat(const value_type &l, const value_type &r) const {
assert(l.len >= 0 && r.len >= 0);
return {l.h * ct_->power(r.len) + r.h, l.len + r.len};
}
private:
using context_type = internal::rolling_hash_context<Hash>;
std::shared_ptr<context_type> ct_;
std::vector<Hash> pr_;
template <class Iterator> void build(Iterator a, Iterator lst) {
pr_.assign(1, Hash{});
for (; a != lst; ++a) {
Hash c(internal::normalize_hash_symbol(Symbol(*a)));
pr_.push_back(pr_.back() * base() + c);
}
ct_->power(size());
}
};
/// @brief Longest common prefix of suffixes beginning at i1 and
/// i2.
template <class FirstHash, class SecondHash>
int lcp(const FirstHash &a, int i1, const SecondHash &b, int i2) {
int n1 = internal::hash_size(a);
int n2 = internal::hash_size(b);
assert(0 <= i1 && i1 <= n1);
assert(0 <= i2 && i2 <= n2);
internal::assert_compatible_hashes(a, b);
int ok = 0;
int bad = std::min(n1 - i1, n2 - i2) + 1;
while (bad - ok > 1) {
int mid = (ok + bad) / 2;
if (a.prod(i1, i1 + mid) == b.prod(i2, i2 + mid)) {
ok = mid;
} else {
bad = mid;
}
}
return ok;
}
/// @brief Longest common suffix ending at i1 and i2. Index
/// -1 denotes the empty prefix before a sequence.
template <class FirstHash, class SecondHash>
int lcs(const FirstHash &a, int i1, const SecondHash &b, int i2) {
int n1 = internal::hash_size(a);
int n2 = internal::hash_size(b);
assert(-1 <= i1 && i1 < n1);
assert(-1 <= i2 && i2 < n2);
internal::assert_compatible_hashes(a, b);
int ok = 0;
int bad = std::min(i1 + 1, i2 + 1) + 1;
while (bad - ok > 1) {
int mid = (ok + bad) / 2;
if (a.prod(i1 + 1 - mid, i1 + 1) == b.prod(i2 + 1 - mid, i2 + 1)) {
ok = mid;
} else {
bad = mid;
}
}
return ok;
}
/// @brief Check whether [l1, r1) equals
/// [l2, r2) in O(1).
template <class FirstHash, class SecondHash>
bool same(const FirstHash &a, int l1, int r1, const SecondHash &b, int l2,
int r2) {
int n1 = internal::hash_size(a);
int n2 = internal::hash_size(b);
assert(0 <= l1 && l1 <= r1 && r1 <= n1);
assert(0 <= l2 && l2 <= r2 && r2 <= n2);
internal::assert_compatible_hashes(a, b);
return r1 - l1 == r2 - l2 && a.prod(l1, r1) == b.prod(l2, r2);
}
} // namespace noya