cp-includes
This documentation is automatically generated by online-judge-tools/verification-helper
RollingHash.cpp
- View this file on GitHub
- Last update: 2023-02-27 10:03:35-03:00
Depends on
ModularInteger.cpp
Code
#ifndef _LIB_ROLLING_HASH
#define _LIB_ROLLING_HASH
#include "ModularInteger.cpp"
#include "Random.cpp"
#include "Traits.cpp"
#include <bits/stdc++.h>
namespace lib {
using namespace std;
namespace hashing {
namespace {
using traits::HasBidirectionalIterator;
using traits::HasInputIterator;
using traits::IsBidirectionalIterator;
using traits::IsInputIterator;
using traits::IsRandomIterator;
} // namespace
const static int DEFAULT_MAX_POWERS = 1e6 + 5;
const static int GOOD_MOD1 = (int)1e9 + 7;
const static int GOOD_MOD2 = (int)1e9 + 9;
template <typename T, T... Mods> struct BaseProvider {
typedef BaseProvider<T, Mods...> type;
typedef ModularInteger<T, Mods...> mint_type;
mint_type b;
vector<mint_type> powers;
int max_powers = 0;
BaseProvider(T bases[sizeof...(Mods)]) : powers(1, 1) {
b = mint_type::with_remainders(bases);
}
BaseProvider() : powers(1, 1) {
T bases[sizeof...(Mods)];
for (size_t i = 0; i < sizeof...(Mods); i++)
bases[i] = rng::gen.uniform_int(mint_type::mods[i]);
b = mint_type::with_remainders(bases);
}
void set_max_powers(int x) { max_powers = x; }
inline operator mint_type() const { return b; }
inline T operator()(int i) { return b[i]; }
void ensure(int p) const {
type *self = const_cast<type *>(this);
int cur = powers.size();
if (p > cur)
self->powers.resize(max(2 * cur, p));
else
return;
int nsz = powers.size();
for (int i = cur; i < nsz; i++)
self->powers[i] = powers[i - 1] * b;
}
mint_type power(int p) const {
if (p >= max_powers)
return b ^ p;
ensure(p + 1);
return powers[p];
}
T power(int p, int i) const { return power(p)[i]; }
};
template <typename T, T... Mods> struct RollingHash {
typedef RollingHash<T, Mods...> type;
typedef ModularInteger<T, Mods...> mint_type;
typedef BaseProvider<T, Mods...> base_type;
vector<mint_type> hs;
struct Hash {
mint_type x;
int n;
struct Less {
typename mint_type::less mint_less;
bool operator()(const Hash &lhs, const Hash &rhs) const {
if (lhs.n == rhs.n)
return mint_less(lhs.x, rhs.x);
return lhs.n < rhs.n;
}
};
typedef Less less;
Hash() : n(0) {}
explicit Hash(mint_type y) : x(y), n(1) {}
Hash(mint_type y, int n) : x(y), n(n) { assert(n >= 0); }
explicit operator mint_type() const { return x; }
friend bool operator==(const Hash &lhs, const Hash &rhs) {
return tie(lhs.n, lhs.x) == tie(rhs.n, rhs.x);
}
friend bool operator!=(const Hash &lhs, const Hash &rhs) {
return !(lhs == rhs);
}
friend ostream &operator<<(ostream &output, const Hash &var) {
return output << var.x << "{" << var.n << "}";
}
};
struct Cat {
shared_ptr<base_type> base;
Cat(const shared_ptr<base_type> &base) : base(base) {}
template <
typename Iterator,
typename enable_if<IsInputIterator<Iterator>::value>::type * = nullptr>
Hash operator()(Iterator begin, Iterator end) {
Hash res;
for (auto it = begin; it != end; ++it) {
res.n += it->n;
res.x *= base->power(it->n);
res.x += it->x;
}
return res;
}
Hash operator()(const initializer_list<Hash> &hashes) {
return (*this)(hashes.begin(), hashes.end());
}
template <class... Args> Hash operator()(Args... args) {
return (*this)({args...});
}
template <class... Args>
pair<Hash, Hash> cat(const pair<Args, Args> &... args) {
initializer_list<Hash> fwd_list = {args.first...};
initializer_list<Hash> bwd_list = {args.second...};
return {cat(fwd_list.begin(), fwd_list.end()),
cat(bwd_list.rbegin(), bwd_list.rend())};
}
};
Cat cat;
RollingHash(const shared_ptr<base_type> &base) : hs(1), cat(base) {}
template <
typename Container,
typename enable_if<HasInputIterator<Container>::value>::type * = nullptr>
RollingHash(const Container &container, const shared_ptr<base_type> &base)
: hs(1), cat(base) {
(*this) += container;
}
template <
typename Iterator,
typename enable_if<IsInputIterator<Iterator>::value>::type * = nullptr>
RollingHash(Iterator begin, Iterator end, const shared_ptr<base_type> &base)
: hs(1), cat(base) {
append(begin, end);
}
inline int size() const { return (int)hs.size() - 1; }
template <
typename Iterator,
typename enable_if<IsRandomIterator<Iterator>::value>::type * = nullptr>
void append(Iterator begin, Iterator end) {
int i = hs.size();
hs.resize(hs.size() + distance(begin, end));
for (auto it = begin; it != end; ++it, ++i)
hs[i] = hs[i - 1] * (*cat.base) + mint_type(*it);
}
template <
typename Iterator,
typename enable_if<!IsRandomIterator<Iterator>::value>::type * = nullptr>
void append(Iterator begin, Iterator end) {
for (auto it = begin; it != end; ++it)
(*this) += *it;
}
template <typename U> void append(U rhs) { (*this) += rhs; }
template <typename U,
typename enable_if<is_integral<U>::value>::type * = nullptr>
RollingHash &operator+=(U rhs) {
hs.push_back(mint_type(rhs) + hs.back() * (*cat.base));
return *this;
}
template <
typename Container,
typename enable_if<HasInputIterator<Container>::value>::type * = nullptr>
RollingHash &operator+=(const Container &rhs) {
append(rhs.begin(), rhs.end());
return *this;
}
inline void pop() {
assert(size() > 0);
hs.pop_back();
}
Hash prefix(int n) const {
n = min(n, size());
return Hash(hs[n], n);
}
Hash operator()(int i, int j) const {
return Hash(hs[j + 1] - hs[i] * (cat.base->power(j - i + 1)), j - i + 1);
}
Hash suffix(int n) const {
int sz = size();
n = min(n, sz);
return (*this)(sz - n, sz - 1);
}
pair<Hash, Hash> border(int n) const { return {prefix(n), suffix(n)}; }
Hash substr(int i) const {
i = min(i, size());
return (*this)(i, size() - 1);
}
Hash substr(int i, int j) const { return (*this)(i, j); }
Hash all() const { return Hash(hs.back(), size()); }
friend int lcp(const type &lhs, const type &rhs) {
int l = 0, r = min(lhs.size(), rhs.size());
while (l < r) {
int mid = (l + r) / 2;
if (lhs.hs[mid + 1] != rhs.hs[mid + 1])
r = mid;
else
l = mid + 1;
}
return l;
}
friend bool operator<(const type &lhs, const type &rhs) {
int l = lcp(lhs, rhs);
if (l == min(lhs.size(), rhs.size()))
return lhs.size() < rhs.size();
return lhs(l, l) < rhs(l, l);
}
};
template <typename T, T... Mods> struct BidirectionalRollingHash {
typedef RollingHash<T, Mods...> type;
using Hash = typename type::Hash;
using base_type = typename type::base_type;
using Cat = typename type::Cat;
type fwd, bwd;
typename type::Cat cat;
template <typename Container,
typename enable_if<HasBidirectionalIterator<Container>::value>::type
* = nullptr>
BidirectionalRollingHash(const Container &container,
const shared_ptr<base_type> &base)
: BidirectionalRollingHash<T, Mods...>(container.begin(), container.end(),
base) {}
template <typename Iterator,
typename enable_if<IsBidirectionalIterator<Iterator>::value>::type
* = nullptr>
BidirectionalRollingHash(Iterator begin, Iterator end,
const shared_ptr<base_type> &base)
: fwd(begin, end, base),
bwd(make_reverse_iterator(end), make_reverse_iterator(begin), base),
cat(base) {}
inline Hash forward(int i, int j) const { return fwd(i, j); }
inline Hash backward(int i, int j) const {
int n = fwd.size();
return bwd(n - j - 1, n - i - 1);
}
inline pair<Hash, Hash> operator()(int i, int j) const {
return {forward(i, j), backward(i, j)};
}
};
template <typename R> struct HashProvider {
typedef R Roll;
typedef typename R::base_type base_type;
typedef typename R::Hash Hash;
typename R::Cat cat;
HashProvider() : cat(make_shared<base_type>()) {}
explicit HashProvider(base_type base) : cat(make_shared<base_type>(base)) {}
template <class... Args> R operator()(Args... args) {
return R(args..., cat.base);
}
};
template <typename R> struct PowerHashProvider : HashProvider<R> {
using typename HashProvider<R>::base_type;
using HashProvider<R>::cat;
PowerHashProvider() : PowerHashProvider<R>(base_type()) {}
PowerHashProvider(base_type base) : HashProvider<R>(base) {
cat.base->set_max_powers(DEFAULT_MAX_POWERS);
}
};
template <int32_t... Mods> using Roll32 = RollingHash<int32_t, Mods...>;
template <int64_t... Mods> using Roll64 = RollingHash<int64_t, Mods...>;
template <int32_t... Mods>
using Biroll32 = BidirectionalRollingHash<int32_t, Mods...>;
template <int64_t... Mods>
using Biroll64 = BidirectionalRollingHash<int64_t, Mods...>;
using DefaultProvider = PowerHashProvider<Roll32<GOOD_MOD1, GOOD_MOD2>>;
using BiDefaultProvider = PowerHashProvider<Biroll32<GOOD_MOD1, GOOD_MOD2>>;
} // namespace hashing
} // namespace lib
#endif#line 1 "RollingHash.cpp"
#line 1 "ModularInteger.cpp"
#line 1 "NumberTheory.cpp"
#include <bits/stdc++.h>
namespace lib {
using namespace std;
namespace nt {
int64_t inverse(int64_t a, int64_t b) {
long long b0 = b, t, q;
long long x0 = 0, x1 = 1;
if (b == 1)
return 1;
while (a > 1) {
q = a / b;
t = b, b = a % b, a = t;
t = x0, x0 = x1 - q * x0, x1 = t;
}
if (x1 < 0)
x1 += b0;
return x1;
}
template<typename T, typename U>
T powmod (T a, U b, U p) {
int res = 1;
while (b)
if (b & 1)
res = (int) (res * 1ll * a % p), --b;
else
a = (int) (a * 1ll * a % p), b >>= 1;
return res;
}
template<typename T>
vector<T> factors(T n) {
vector<T> f;
for(T i = 2; i*i <= n; i++) {
if(n % i == 0) f.push_back(i);
while(n % i == 0) n /= i;
}
if(n > 1) f.push_back(n);
return f;
}
} // namespace nt
} // namespace lib
#line 5 "ModularInteger.cpp"
#if __cplusplus < 201300
#error required(c++14)
#endif
namespace lib {
using namespace std;
namespace {
template <typename T, T... Mods> struct ModularIntegerBase {
typedef ModularIntegerBase<T, Mods...> type;
T x[sizeof...(Mods)];
friend ostream &operator<<(ostream &output, const type &var) {
output << "(";
for (int i = 0; i < sizeof...(Mods); i++) {
if (i)
output << ", ";
output << var.x[i];
}
return output << ")";
}
};
template <typename T, T Mod> struct ModularIntegerBase<T, Mod> {
typedef ModularIntegerBase<T, Mod> type;
constexpr static T mod = Mod;
T x[1];
T& data() { return this->x[0]; }
T data() const { return this->x[0]; }
explicit operator int() const { return this->x[0]; }
explicit operator int64_t() const { return this->x[0]; }
explicit operator double() const { return this->x[0]; }
explicit operator long double() const { return this->x[0]; }
friend ostream &operator<<(ostream &output, const type &var) {
return output << var.x[0];
}
};
template<typename T, typename U, T... Mods>
struct InversesTable {
constexpr static size_t n_mods = sizeof...(Mods);
constexpr static T mods[sizeof...(Mods)] = {Mods...};
constexpr static int n_inverses = 1e6 + 10;
T v[n_inverses][n_mods];
T max_x;
InversesTable() : v(), max_x(n_inverses) {
for(int j = 0; j < sizeof...(Mods); j++)
v[1][j] = 1, max_x = min(max_x, mods[j]);
for(int i = 2; i < max_x; i++) {
for(int j = 0; j < sizeof...(Mods); j++) {
v[i][j] = mods[j] - (T)((U)(mods[j] / i) * v[mods[j] % i][j] % mods[j]);
}
}
}
};
// Make available for linkage.
template <typename T, class U, T... Mods>
constexpr T InversesTable<T, U, Mods...>::mods[];
template <typename T, class Enable, T... Mods>
struct ModularIntegerImpl : ModularIntegerBase<T, Mods...> {
typedef ModularIntegerImpl<T, Enable, Mods...> type;
typedef T type_int;
typedef uint64_t large_int;
constexpr static size_t n_mods = sizeof...(Mods);
constexpr static T mods[sizeof...(Mods)] = {Mods...};
using ModularIntegerBase<T, Mods...>::x;
using Inverses = InversesTable<T, large_int, Mods...>;
struct Less {
bool operator()(const type &lhs, const type &rhs) const {
for (size_t i = 0; i < sizeof...(Mods); i++)
if (lhs.x[i] != rhs.x[i])
return lhs.x[i] < rhs.x[i];
return false;
};
};
typedef Less less;
constexpr ModularIntegerImpl() {
for (size_t i = 0; i < sizeof...(Mods); i++)
x[i] = T();
}
constexpr ModularIntegerImpl(large_int y) {
for (size_t i = 0; i < sizeof...(Mods); i++) {
x[i] = y % mods[i];
if (x[i] < 0)
x[i] += mods[i];
}
}
static type with_remainders(T y[sizeof...(Mods)]) {
type res;
for (size_t i = 0; i < sizeof...(Mods); i++)
res.x[i] = y[i];
res.normalize();
return res;
}
inline void normalize() {
for (size_t i = 0; i < sizeof...(Mods); i++)
if ((x[i] %= mods[i]) < 0)
x[i] += mods[i];
}
inline T operator[](int i) const { return x[i]; }
inline T multiply(T a, T b, T mod) const { return (large_int)a * b % mod; }
inline T inv(T a, T mod) const { return static_cast<T>(nt::inverse(a, mod)); }
inline T invi(T a, int i) const {
const static Inverses inverses = Inverses();
if(a < inverses.max_x)
return inverses.v[a][i];
return inv(a, mods[i]);
}
type inverse() const {
T res[sizeof...(Mods)];
for (size_t i = 0; i < sizeof...(Mods); i++)
res[i] = invi(x[i], i);
return type::with_remainders(res);
}
template <typename U> T power_(T a, U p, T mod) {
if (mod == 1)
return T();
if (p < 0) {
if (a == 0)
throw domain_error("0^p with negative p is invalid");
p = -p;
a = inv(a, mod);
}
if (p == 0)
return T(1);
if (p == 1)
return a;
T res = 1;
while (p > 0) {
if (p & 1)
res = multiply(res, a, mod);
p >>= 1;
a = multiply(a, a, mod);
}
return res;
}
inline type &operator+=(const type &rhs) {
for (size_t i = 0; i < sizeof...(Mods); i++)
if ((x[i] += rhs.x[i]) >= mods[i])
x[i] -= mods[i];
return *this;
}
inline type &operator-=(const type &rhs) {
for (size_t i = 0; i < sizeof...(Mods); i++)
if ((x[i] -= rhs.x[i]) < 0)
x[i] += mods[i];
return *this;
}
inline type &operator*=(const type &rhs) {
for (size_t i = 0; i < sizeof...(Mods); i++)
x[i] = multiply(x[i], rhs.x[i], mods[i]);
return *this;
}
inline type &operator/=(const type &rhs) {
for (size_t i = 0; i < sizeof...(Mods); i++)
x[i] = multiply(x[i], invi(rhs.x[i], i), mods[i]);
return *this;
}
inline type &operator+=(T rhs) {
for (size_t i = 0; i < sizeof...(Mods); i++)
if ((x[i] += rhs) >= mods[i])
x[i] -= mods[i];
return *this;
}
type &operator-=(T rhs) {
for (size_t i = 0; i < sizeof...(Mods); i++)
if ((x[i] -= rhs) < 0)
x[i] += mods[i];
return *this;
}
type &operator*=(T rhs) {
for (size_t i = 0; i < sizeof...(Mods); i++)
x[i] = multiply(x[i], rhs, mods[i]);
return *this;
}
type &operator/=(T rhs) {
for (size_t i = 0; i < sizeof...(Mods); i++)
x[i] = multiply(invi(rhs, i), x[i], mods[i]);
return *this;
}
type &operator^=(large_int p) {
for (size_t i = 0; i < sizeof...(Mods); i++)
x[i] = power_(x[i], p, mods[i]);
return *this;
}
type &operator++() {
for (size_t i = 0; i < sizeof...(Mods); i++)
if ((++x[i]) >= mods[i])
x[i] -= mods[i];
return *this;
}
type &operator--() {
for (size_t i = 0; i < sizeof...(Mods); i++)
if ((--x[i]) < 0)
x[i] += mods[i];
return *this;
}
type operator++(int unused) {
type res = *this;
++(*this);
return res;
}
type operator--(int unused) {
type res = *this;
--(*this);
return res;
}
friend type operator+(const type &lhs, const type &rhs) {
type res = lhs;
return res += rhs;
}
friend type operator-(const type &lhs, const type &rhs) {
type res = lhs;
return res -= rhs;
}
friend type operator*(const type &lhs, const type &rhs) {
type res = lhs;
return res *= rhs;
}
friend type operator/(const type &lhs, const type &rhs) {
type res = lhs;
return res /= rhs;
}
friend type operator+(const type &lhs, T rhs) {
type res = lhs;
return res += rhs;
}
friend type operator-(const type &lhs, T rhs) {
type res = lhs;
return res -= rhs;
}
friend type operator*(const type &lhs, T rhs) {
type res = lhs;
return res *= rhs;
}
friend type operator/(const type &lhs, T rhs) {
type res = lhs;
return res /= rhs;
}
friend type operator^(const type &lhs, large_int rhs) {
type res = lhs;
return res ^= rhs;
}
friend type power(const type &lhs, large_int rhs) { return lhs ^ rhs; }
type operator-() const {
type res = *this;
for (size_t i = 0; i < sizeof...(Mods); i++)
if (res.x[i])
res.x[i] = mods[i] - res.x[i];
return res;
}
friend bool operator==(const type &lhs, const type &rhs) {
for (size_t i = 0; i < sizeof...(Mods); i++)
if (lhs.x[i] != rhs.x[i])
return false;
return true;
}
friend bool operator!=(const type &lhs, const type &rhs) {
return !(lhs == rhs);
}
friend istream &operator>>(istream &input, type &var) {
T y;
cin >> y;
var = y;
return input;
}
};
} // namespace
// Explicitly make constexpr available for linkage.
template <typename T, class Enable, T... Mods>
constexpr T ModularIntegerImpl<T, Enable, Mods...>::mods[];
template <typename T, T... Mods>
using ModularInteger =
ModularIntegerImpl<T, typename enable_if<is_integral<T>::value>::type,
Mods...>;
template <int32_t... Mods> using Mint32 = ModularInteger<int32_t, Mods...>;
template <int64_t... Mods> using Mint64 = ModularInteger<int64_t, Mods...>;
using MintP = Mint32<(int32_t)1e9+7>;
using MintNTT = Mint32<998244353>;
} // namespace lib
#line 1 "Random.cpp"
#line 4 "Random.cpp"
namespace lib {
using namespace std;
namespace rng {
struct Generator {
mt19937 rng;
Generator() {
seed_seq seq {
(uint64_t) chrono::duration_cast<chrono::nanoseconds>(
chrono::high_resolution_clock::now().time_since_epoch())
.count(),
#if __cplusplus > 201300
(uint64_t)make_unique<char>().get(),
#else
(uint64_t)unique_ptr<char>(new char).get(),
#endif
(uint64_t)__builtin_ia32_rdtsc()
};
rng = mt19937(seq);
}
Generator(seed_seq &seq) : rng(seq) {}
template <typename T,
typename enable_if<is_integral<T>::value>::type * = nullptr>
inline T uniform_int(T L, T R) {
return uniform_int_distribution<T>(L, R)(rng);
}
template <typename T> inline T uniform_int(T N) {
return uniform_int(T(), N - 1);
}
template <typename T> inline T uniform_real(T N) {
return uniform_real(0.0, static_cast<double>(N));
}
template <typename T> inline T uniform_real(T L, T R) {
return uniform_real_distribution<double>(static_cast<double>(L),
static_cast<double>(R))(rng);
}
inline double uniform_real() { return uniform_real(0.0, 1.0); }
};
static Generator gen = Generator();
} // namespace rng
static rng::Generator &rng_gen = rng::gen;
} // namespace lib
#line 1 "Traits.cpp"
#line 4 "Traits.cpp"
namespace lib {
using namespace std;
namespace traits {
template <typename...> struct make_void { using type = void; };
template <typename... T> using void_t = typename make_void<T...>::type;
/// keep caide
template <typename Iterator>
using IteratorCategory = typename iterator_traits<Iterator>::iterator_category;
/// keep caide
template <typename Container>
using IteratorCategoryOf = IteratorCategory<typename Container::iterator>;
/// keep caide
template <typename Iterator>
using IteratorValue = typename iterator_traits<Iterator>::value_type;
/// keep caide
template <typename Container>
using IteratorValueOf = IteratorValue<typename Container::iterator>;
/// keep caide
template <typename Iterator>
using IsRandomIterator =
is_base_of<random_access_iterator_tag, IteratorCategory<Iterator>>;
/// keep caide
template <typename Iterator>
using IsInputIterator =
is_base_of<input_iterator_tag, IteratorCategory<Iterator>>;
/// keep caide
template <typename Iterator>
using IsBidirectionalIterator =
is_base_of<bidirectional_iterator_tag, IteratorCategory<Iterator>>;
/// keep caide
template <typename Container>
using HasRandomIterator =
is_base_of<random_access_iterator_tag, IteratorCategoryOf<Container>>;
/// keep caide
template <typename Container>
using HasInputIterator =
is_base_of<input_iterator_tag, IteratorCategoryOf<Container>>;
/// keep caide
template <typename Container>
using HasBidirectionalIterator =
is_base_of<bidirectional_iterator_tag, IteratorCategoryOf<Container>>;
} // namespace traits
} // namespace lib
#line 7 "RollingHash.cpp"
namespace lib {
using namespace std;
namespace hashing {
namespace {
using traits::HasBidirectionalIterator;
using traits::HasInputIterator;
using traits::IsBidirectionalIterator;
using traits::IsInputIterator;
using traits::IsRandomIterator;
} // namespace
const static int DEFAULT_MAX_POWERS = 1e6 + 5;
const static int GOOD_MOD1 = (int)1e9 + 7;
const static int GOOD_MOD2 = (int)1e9 + 9;
template <typename T, T... Mods> struct BaseProvider {
typedef BaseProvider<T, Mods...> type;
typedef ModularInteger<T, Mods...> mint_type;
mint_type b;
vector<mint_type> powers;
int max_powers = 0;
BaseProvider(T bases[sizeof...(Mods)]) : powers(1, 1) {
b = mint_type::with_remainders(bases);
}
BaseProvider() : powers(1, 1) {
T bases[sizeof...(Mods)];
for (size_t i = 0; i < sizeof...(Mods); i++)
bases[i] = rng::gen.uniform_int(mint_type::mods[i]);
b = mint_type::with_remainders(bases);
}
void set_max_powers(int x) { max_powers = x; }
inline operator mint_type() const { return b; }
inline T operator()(int i) { return b[i]; }
void ensure(int p) const {
type *self = const_cast<type *>(this);
int cur = powers.size();
if (p > cur)
self->powers.resize(max(2 * cur, p));
else
return;
int nsz = powers.size();
for (int i = cur; i < nsz; i++)
self->powers[i] = powers[i - 1] * b;
}
mint_type power(int p) const {
if (p >= max_powers)
return b ^ p;
ensure(p + 1);
return powers[p];
}
T power(int p, int i) const { return power(p)[i]; }
};
template <typename T, T... Mods> struct RollingHash {
typedef RollingHash<T, Mods...> type;
typedef ModularInteger<T, Mods...> mint_type;
typedef BaseProvider<T, Mods...> base_type;
vector<mint_type> hs;
struct Hash {
mint_type x;
int n;
struct Less {
typename mint_type::less mint_less;
bool operator()(const Hash &lhs, const Hash &rhs) const {
if (lhs.n == rhs.n)
return mint_less(lhs.x, rhs.x);
return lhs.n < rhs.n;
}
};
typedef Less less;
Hash() : n(0) {}
explicit Hash(mint_type y) : x(y), n(1) {}
Hash(mint_type y, int n) : x(y), n(n) { assert(n >= 0); }
explicit operator mint_type() const { return x; }
friend bool operator==(const Hash &lhs, const Hash &rhs) {
return tie(lhs.n, lhs.x) == tie(rhs.n, rhs.x);
}
friend bool operator!=(const Hash &lhs, const Hash &rhs) {
return !(lhs == rhs);
}
friend ostream &operator<<(ostream &output, const Hash &var) {
return output << var.x << "{" << var.n << "}";
}
};
struct Cat {
shared_ptr<base_type> base;
Cat(const shared_ptr<base_type> &base) : base(base) {}
template <
typename Iterator,
typename enable_if<IsInputIterator<Iterator>::value>::type * = nullptr>
Hash operator()(Iterator begin, Iterator end) {
Hash res;
for (auto it = begin; it != end; ++it) {
res.n += it->n;
res.x *= base->power(it->n);
res.x += it->x;
}
return res;
}
Hash operator()(const initializer_list<Hash> &hashes) {
return (*this)(hashes.begin(), hashes.end());
}
template <class... Args> Hash operator()(Args... args) {
return (*this)({args...});
}
template <class... Args>
pair<Hash, Hash> cat(const pair<Args, Args> &... args) {
initializer_list<Hash> fwd_list = {args.first...};
initializer_list<Hash> bwd_list = {args.second...};
return {cat(fwd_list.begin(), fwd_list.end()),
cat(bwd_list.rbegin(), bwd_list.rend())};
}
};
Cat cat;
RollingHash(const shared_ptr<base_type> &base) : hs(1), cat(base) {}
template <
typename Container,
typename enable_if<HasInputIterator<Container>::value>::type * = nullptr>
RollingHash(const Container &container, const shared_ptr<base_type> &base)
: hs(1), cat(base) {
(*this) += container;
}
template <
typename Iterator,
typename enable_if<IsInputIterator<Iterator>::value>::type * = nullptr>
RollingHash(Iterator begin, Iterator end, const shared_ptr<base_type> &base)
: hs(1), cat(base) {
append(begin, end);
}
inline int size() const { return (int)hs.size() - 1; }
template <
typename Iterator,
typename enable_if<IsRandomIterator<Iterator>::value>::type * = nullptr>
void append(Iterator begin, Iterator end) {
int i = hs.size();
hs.resize(hs.size() + distance(begin, end));
for (auto it = begin; it != end; ++it, ++i)
hs[i] = hs[i - 1] * (*cat.base) + mint_type(*it);
}
template <
typename Iterator,
typename enable_if<!IsRandomIterator<Iterator>::value>::type * = nullptr>
void append(Iterator begin, Iterator end) {
for (auto it = begin; it != end; ++it)
(*this) += *it;
}
template <typename U> void append(U rhs) { (*this) += rhs; }
template <typename U,
typename enable_if<is_integral<U>::value>::type * = nullptr>
RollingHash &operator+=(U rhs) {
hs.push_back(mint_type(rhs) + hs.back() * (*cat.base));
return *this;
}
template <
typename Container,
typename enable_if<HasInputIterator<Container>::value>::type * = nullptr>
RollingHash &operator+=(const Container &rhs) {
append(rhs.begin(), rhs.end());
return *this;
}
inline void pop() {
assert(size() > 0);
hs.pop_back();
}
Hash prefix(int n) const {
n = min(n, size());
return Hash(hs[n], n);
}
Hash operator()(int i, int j) const {
return Hash(hs[j + 1] - hs[i] * (cat.base->power(j - i + 1)), j - i + 1);
}
Hash suffix(int n) const {
int sz = size();
n = min(n, sz);
return (*this)(sz - n, sz - 1);
}
pair<Hash, Hash> border(int n) const { return {prefix(n), suffix(n)}; }
Hash substr(int i) const {
i = min(i, size());
return (*this)(i, size() - 1);
}
Hash substr(int i, int j) const { return (*this)(i, j); }
Hash all() const { return Hash(hs.back(), size()); }
friend int lcp(const type &lhs, const type &rhs) {
int l = 0, r = min(lhs.size(), rhs.size());
while (l < r) {
int mid = (l + r) / 2;
if (lhs.hs[mid + 1] != rhs.hs[mid + 1])
r = mid;
else
l = mid + 1;
}
return l;
}
friend bool operator<(const type &lhs, const type &rhs) {
int l = lcp(lhs, rhs);
if (l == min(lhs.size(), rhs.size()))
return lhs.size() < rhs.size();
return lhs(l, l) < rhs(l, l);
}
};
template <typename T, T... Mods> struct BidirectionalRollingHash {
typedef RollingHash<T, Mods...> type;
using Hash = typename type::Hash;
using base_type = typename type::base_type;
using Cat = typename type::Cat;
type fwd, bwd;
typename type::Cat cat;
template <typename Container,
typename enable_if<HasBidirectionalIterator<Container>::value>::type
* = nullptr>
BidirectionalRollingHash(const Container &container,
const shared_ptr<base_type> &base)
: BidirectionalRollingHash<T, Mods...>(container.begin(), container.end(),
base) {}
template <typename Iterator,
typename enable_if<IsBidirectionalIterator<Iterator>::value>::type
* = nullptr>
BidirectionalRollingHash(Iterator begin, Iterator end,
const shared_ptr<base_type> &base)
: fwd(begin, end, base),
bwd(make_reverse_iterator(end), make_reverse_iterator(begin), base),
cat(base) {}
inline Hash forward(int i, int j) const { return fwd(i, j); }
inline Hash backward(int i, int j) const {
int n = fwd.size();
return bwd(n - j - 1, n - i - 1);
}
inline pair<Hash, Hash> operator()(int i, int j) const {
return {forward(i, j), backward(i, j)};
}
};
template <typename R> struct HashProvider {
typedef R Roll;
typedef typename R::base_type base_type;
typedef typename R::Hash Hash;
typename R::Cat cat;
HashProvider() : cat(make_shared<base_type>()) {}
explicit HashProvider(base_type base) : cat(make_shared<base_type>(base)) {}
template <class... Args> R operator()(Args... args) {
return R(args..., cat.base);
}
};
template <typename R> struct PowerHashProvider : HashProvider<R> {
using typename HashProvider<R>::base_type;
using HashProvider<R>::cat;
PowerHashProvider() : PowerHashProvider<R>(base_type()) {}
PowerHashProvider(base_type base) : HashProvider<R>(base) {
cat.base->set_max_powers(DEFAULT_MAX_POWERS);
}
};
template <int32_t... Mods> using Roll32 = RollingHash<int32_t, Mods...>;
template <int64_t... Mods> using Roll64 = RollingHash<int64_t, Mods...>;
template <int32_t... Mods>
using Biroll32 = BidirectionalRollingHash<int32_t, Mods...>;
template <int64_t... Mods>
using Biroll64 = BidirectionalRollingHash<int64_t, Mods...>;
using DefaultProvider = PowerHashProvider<Roll32<GOOD_MOD1, GOOD_MOD2>>;
using BiDefaultProvider = PowerHashProvider<Biroll32<GOOD_MOD1, GOOD_MOD2>>;
} // namespace hashing
} // namespace lib