#include "string/rolling-hash-on-segment-tree.hpp"
#pragma once #include <vector> using namespace std; #include "../atcoder/segtree.hpp" #include "../internal/internal-hash.hpp" namespace RollingHashonSegmentTreeImpl { constexpr int BASE_NUM = 1; using Hash = internal::Hash<BASE_NUM>; using T = pair<Hash, int>; vector<Hash> Pow{Hash::set(1)}; const Hash Basis = Hash::get_basis(); const Hash Zero = Hash::set(0); T op(T a, T b) { while (b.second >= (int)Pow.size()) { Hash h = Pow.back(); Pow.push_back(h * Basis); } Hash h = pfma(a.first, Pow[b.second], b.first); int len = a.second + b.second; return make_pair(h, len); } T e() { return make_pair(Zero, 0); } template <typename Str> struct RollingHashonSegmentTree { using Value = typename Str::value_type; int n; atcoder::segtree<T, op, e> seg; RollingHashonSegmentTree() : n(0) {} RollingHashonSegmentTree(const Str& S) : n(S.size()) { vector<T> init(n); for (int i = 0; i < n; i++) { init[i] = make_pair(Hash::set(S[i]), 1); } seg = {init}; } void update(int i, const Value& v) { assert(0 <= i and i < n); seg.set(i, make_pair(Hash::set(v), 1)); } // [l1, r1) と [l2, r2) が一致するかを判定 bool same(int l1, int r1, int l2, int r2) { assert(0 <= l1 and l1 <= r1 and r1 <= n); assert(0 <= l2 and l2 <= r2 and r2 <= n); if (r1 - l1 != r2 - l2) return false; return seg.prod(l1, r1) == seg.prod(l2, r2); } }; } // namespace RollingHashonSegmentTreeImpl using RollingHashonSegmentTreeImpl::RollingHashonSegmentTree;
#line 2 "string/rolling-hash-on-segment-tree.hpp" #include <vector> using namespace std; #line 1 "atcoder/segtree.hpp" #include <algorithm> #include <cassert> #line 7 "atcoder/segtree.hpp" #line 1 "atcoder/internal_bit.hpp" #ifdef _MSC_VER #include <intrin.h> #endif namespace atcoder { namespace internal { // @param n `0 <= n` // @return minimum non-negative `x` s.t. `n <= 2**x` int ceil_pow2(int n) { int x = 0; while ((1U << x) < (unsigned int)(n)) x++; return x; } // @param n `1 <= n` // @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0` constexpr int bsf_constexpr(unsigned int n) { int x = 0; while (!(n & (1 << x))) x++; return x; } // @param n `1 <= n` // @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0` int bsf(unsigned int n) { #ifdef _MSC_VER unsigned long index; _BitScanForward(&index, n); return index; #else return __builtin_ctz(n); #endif } } // namespace internal } // namespace atcoder #line 9 "atcoder/segtree.hpp" namespace atcoder { template <class S, S (*op)(S, S), S (*e)()> struct segtree { public: segtree() : segtree(0) {} segtree(int n) : segtree(std::vector<S>(n, e())) {} segtree(const std::vector<S>& v) : _n(int(v.size())) { log = internal::ceil_pow2(_n); size = 1 << log; d = std::vector<S>(2 * size, e()); for (int i = 0; i < _n; i++) d[size + i] = v[i]; for (int i = size - 1; i >= 1; i--) { update(i); } } void set(int p, S x) { assert(0 <= p && p < _n); p += size; d[p] = x; for (int i = 1; i <= log; i++) update(p >> i); } S get(int p) { assert(0 <= p && p < _n); return d[p + size]; } S prod(int l, int r) { assert(0 <= l && l <= r && r <= _n); S sml = e(), smr = e(); l += size; r += size; while (l < r) { if (l & 1) sml = op(sml, d[l++]); if (r & 1) smr = op(d[--r], smr); l >>= 1; r >>= 1; } return op(sml, smr); } S all_prod() { return d[1]; } template <bool (*f)(S)> int max_right(int l) { return max_right(l, [](S x) { return f(x); }); } template <class F> int max_right(int l, F f) { assert(0 <= l && l <= _n); assert(f(e())); if (l == _n) return _n; l += size; S sm = e(); do { while (l % 2 == 0) l >>= 1; if (!f(op(sm, d[l]))) { while (l < size) { l = (2 * l); if (f(op(sm, d[l]))) { sm = op(sm, d[l]); l++; } } return l - size; } sm = op(sm, d[l]); l++; } while ((l & -l) != l); return _n; } template <bool (*f)(S)> int min_left(int r) { return min_left(r, [](S x) { return f(x); }); } template <class F> int min_left(int r, F f) { assert(0 <= r && r <= _n); assert(f(e())); if (r == 0) return 0; r += size; S sm = e(); do { r--; while (r > 1 && (r % 2)) r >>= 1; if (!f(op(d[r], sm))) { while (r < size) { r = (2 * r + 1); if (f(op(d[r], sm))) { sm = op(d[r], sm); r--; } } return r + 1 - size; } sm = op(d[r], sm); } while ((r & -r) != r); return 0; } private: int _n, size, log; std::vector<S> d; void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); } }; } // namespace atcoder #line 2 "internal/internal-hash.hpp" namespace internal { using i64 = long long; using u64 = unsigned long long; using u128 = __uint128_t; template <int BASE_NUM = 2> struct Hash : array<u64, BASE_NUM> { using array<u64, BASE_NUM>::operator[]; static constexpr int n = BASE_NUM; Hash() : array<u64, BASE_NUM>() {} static constexpr u64 md = (1ull << 61) - 1; constexpr static Hash set(const i64 &a) { Hash res; fill(begin(res), end(res), cast(a)); return res; } Hash &operator+=(const Hash &r) { for (int i = 0; i < n; i++) if (((*this)[i] += r[i]) >= md) (*this)[i] -= md; return *this; } Hash &operator+=(const i64 &r) { u64 s = cast(r); for (int i = 0; i < n; i++) if (((*this)[i] += s) >= md) (*this)[i] -= md; return *this; } Hash &operator-=(const Hash &r) { for (int i = 0; i < n; i++) if (((*this)[i] += md - r[i]) >= md) (*this)[i] -= md; return *this; } Hash &operator-=(const i64 &r) { u64 s = cast(r); for (int i = 0; i < n; i++) if (((*this)[i] += md - s) >= md) (*this)[i] -= md; return *this; } Hash &operator*=(const Hash &r) { for (int i = 0; i < n; i++) (*this)[i] = modmul((*this)[i], r[i]); return *this; } Hash &operator*=(const i64 &r) { u64 s = cast(r); for (int i = 0; i < n; i++) (*this)[i] = modmul((*this)[i], s); return *this; } Hash operator+(const Hash &r) { return Hash(*this) += r; } Hash operator+(const i64 &r) { return Hash(*this) += r; } Hash operator-(const Hash &r) { return Hash(*this) -= r; } Hash operator-(const i64 &r) { return Hash(*this) -= r; } Hash operator*(const Hash &r) { return Hash(*this) *= r; } Hash operator*(const i64 &r) { return Hash(*this) *= r; } Hash operator-() const { Hash res; for (int i = 0; i < n; i++) res[i] = (*this)[i] == 0 ? 0 : md - (*this)[i]; return res; } friend Hash pfma(const Hash &a, const Hash &b, const Hash &c) { Hash res; for (int i = 0; i < n; i++) res[i] = modfma(a[i], b[i], c[i]); return res; } friend Hash pfma(const Hash &a, const Hash &b, const i64 &c) { Hash res; u64 s = cast(c); for (int i = 0; i < n; i++) res[i] = modfma(a[i], b[i], s); return res; } Hash pow(long long e) { Hash a{*this}, res{Hash::set(1)}; for (; e; a *= a, e >>= 1) { if (e & 1) res *= a; } return res; } static Hash get_basis() { static auto rand_time = chrono::duration_cast<chrono::nanoseconds>( chrono::high_resolution_clock::now().time_since_epoch()) .count(); static mt19937_64 rng(rand_time); Hash h; for (int i = 0; i < n; i++) { while (isPrimitive(h[i] = rng() % (md - 1) + 1) == false) ; } return h; } private: static u64 modpow(u64 a, u64 b) { u64 r = 1; for (a %= md; b; a = modmul(a, a), b >>= 1) r = modmul(r, a); return r; } static bool isPrimitive(u64 x) { for (auto &d : vector<u64>{2, 3, 5, 7, 11, 13, 31, 41, 61, 151, 331, 1321}) if (modpow(x, (md - 1) / d) <= 1) return false; return true; } static inline constexpr u64 cast(const long long &a) { return a < 0 ? a + md : a; } static inline constexpr u64 modmul(const u64 &a, const u64 &b) { u128 d = u128(a) * b; u64 ret = (u64(d) & md) + u64(d >> 61); return ret >= md ? ret - md : ret; } static inline constexpr u64 modfma(const u64 &a, const u64 &b, const u64 &c) { u128 d = u128(a) * b + c; u64 ret = (d >> 61) + (u64(d) & md); return ret >= md ? ret - md : ret; } }; } // namespace internal /** * @brief ハッシュ構造体 * @docs docs/internal/internal-hash.md */ #line 8 "string/rolling-hash-on-segment-tree.hpp" namespace RollingHashonSegmentTreeImpl { constexpr int BASE_NUM = 1; using Hash = internal::Hash<BASE_NUM>; using T = pair<Hash, int>; vector<Hash> Pow{Hash::set(1)}; const Hash Basis = Hash::get_basis(); const Hash Zero = Hash::set(0); T op(T a, T b) { while (b.second >= (int)Pow.size()) { Hash h = Pow.back(); Pow.push_back(h * Basis); } Hash h = pfma(a.first, Pow[b.second], b.first); int len = a.second + b.second; return make_pair(h, len); } T e() { return make_pair(Zero, 0); } template <typename Str> struct RollingHashonSegmentTree { using Value = typename Str::value_type; int n; atcoder::segtree<T, op, e> seg; RollingHashonSegmentTree() : n(0) {} RollingHashonSegmentTree(const Str& S) : n(S.size()) { vector<T> init(n); for (int i = 0; i < n; i++) { init[i] = make_pair(Hash::set(S[i]), 1); } seg = {init}; } void update(int i, const Value& v) { assert(0 <= i and i < n); seg.set(i, make_pair(Hash::set(v), 1)); } // [l1, r1) と [l2, r2) が一致するかを判定 bool same(int l1, int r1, int l2, int r2) { assert(0 <= l1 and l1 <= r1 and r1 <= n); assert(0 <= l2 and l2 <= r2 and r2 <= n); if (r1 - l1 != r2 - l2) return false; return seg.prod(l1, r1) == seg.prod(l2, r2); } }; } // namespace RollingHashonSegmentTreeImpl using RollingHashonSegmentTreeImpl::RollingHashonSegmentTree;