library
This documentation is automatically generated by online-judge-tools/verification-helper
Rolling Hash
(String/rollinghash.hpp)
- View this file on GitHub
- Last update: 2024-04-26 03:18:17+09:00
- Include:
#include "String/rollinghash.hpp"
Depends on
Random
(Utility/random.hpp)
Code
#pragma once
#include "Utility/random.hpp"
struct RollingHash {
using ull = unsigned long long;
const ull MOD = 0x1fffffffffffffff;
const ull base;
vector<ull> hashed, power;
static constexpr ull mask(ll a) { return (1ULL << a) - 1; }
inline ull mul(ull a, ull b) const {
__uint128_t ans = __uint128_t(a) * b;
ans = (ans >> 61) + (ans & MOD);
if (ans >= MOD)
ans -= MOD;
return ans;
}
static inline ull genbase() { return Random::get(ull(0x1fffffffffffffff)); }
RollingHash() = default;
RollingHash(const string &s, ull base) : base(base) {
ll n = s.size();
hashed.assign(n + 1, 0);
power.assign(n + 1, 0);
power[0] = 1;
for (ll i = 0; i < n; i++) {
power[i + 1] = mul(power[i], base);
hashed[i + 1] = mul(hashed[i], base) + s[i];
if (hashed[i + 1] >= MOD)
hashed[i + 1] -= MOD;
}
}
ull get(ll l, ll r) const {
ull ret = hashed[r] + MOD - mul(hashed[l], power[r - l]);
if (ret >= MOD)
ret -= MOD;
return ret;
}
ull connect(ull h1, ull h2, ll h2len) const {
ull ret = mul(h1, power[h2len]) + h2;
if (ret >= MOD)
ret -= MOD;
return ret;
}
void connect(const string &s) {
ll n = hashed.size() - 1, m = s.size();
hashed.resize(n + m + 1);
power.resize(n + m + 1);
for (ll i = n; i < n + m; i++) {
power[i + 1] = mul(power[i], base);
hashed[i + 1] = mul(hashed[i], base) + s[i - n];
if (hashed[i + 1] >= MOD)
hashed[i + 1] -= MOD;
}
}
ll LCP(const RollingHash &b, ll l1, ll r1, ll l2, ll r2) {
ll len = min(r1 - l1, r2 - l2);
ll low = -1, high = len + 1;
while (high - low > 1) {
ll mid = (low + high) / 2;
if (get(l1, l1 + mid) == b.get(l2, l2 + mid))
low = mid;
else
high = mid;
}
return low;
}
};
/**
* @brief Rolling Hash
*/#line 2 "Utility/random.hpp"
namespace Random {
mt19937_64 randgen(chrono::steady_clock::now().time_since_epoch().count());
using u64 = unsigned long long;
u64 get() {
return randgen();
}
template <typename T> T get(T L) { // [0,L]
return get() % (L + 1);
}
template <typename T> T get(T L, T R) { // [L,R]
return get(R - L) + L;
}
double uniform() {
return double(get(1000000000)) / 1000000000;
}
string str(int n) {
string ret;
rep(i, 0, n) ret += get('a', 'z');
return ret;
}
template <typename Iter> void shuffle(Iter first, Iter last) {
if (first == last)
return;
int len = 1;
for (auto it = first + 1; it != last; it++) {
len++;
int j = get(0, len - 1);
if (j != len - 1)
iter_swap(it, first + j);
}
}
template <typename T> vector<T> select(int n, T L, T R) { // [L,R]
if (n * 2 >= R - L + 1) {
vector<T> ret(R - L + 1);
iota(ALL(ret), L);
shuffle(ALL(ret));
ret.resize(n);
return ret;
} else {
unordered_set<T> used;
vector<T> ret;
while (SZ(used) < n) {
T x = get(L, R);
if (!used.count(x)) {
used.insert(x);
ret.push_back(x);
}
}
return ret;
}
}
void relabel(int n, vector<pair<int, int>> &es) {
shuffle(ALL(es));
vector<int> ord(n);
iota(ALL(ord), 0);
shuffle(ALL(ord));
for (auto &[u, v] : es)
u = ord[u], v = ord[v];
}
template <bool directed, bool simple> vector<pair<int, int>> genGraph(int n) {
vector<pair<int, int>> cand, es;
rep(u, 0, n) rep(v, 0, n) {
if (simple and u == v)
continue;
if (!directed and u > v)
continue;
cand.push_back({u, v});
}
int m = get(SZ(cand));
vector<int> ord;
if (simple)
ord = select(m, 0, SZ(cand) - 1);
else {
rep(_, 0, m) ord.push_back(get(SZ(cand) - 1));
}
for (auto &i : ord)
es.push_back(cand[i]);
relabel(n, es);
return es;
}
vector<pair<int, int>> genTree(int n) {
vector<pair<int, int>> es;
rep(i, 1, n) es.push_back({get(i - 1), i});
relabel(n, es);
return es;
}
}; // namespace Random
/**
* @brief Random
*/
#line 3 "String/rollinghash.hpp"
struct RollingHash {
using ull = unsigned long long;
const ull MOD = 0x1fffffffffffffff;
const ull base;
vector<ull> hashed, power;
static constexpr ull mask(ll a) { return (1ULL << a) - 1; }
inline ull mul(ull a, ull b) const {
__uint128_t ans = __uint128_t(a) * b;
ans = (ans >> 61) + (ans & MOD);
if (ans >= MOD)
ans -= MOD;
return ans;
}
static inline ull genbase() { return Random::get(ull(0x1fffffffffffffff)); }
RollingHash() = default;
RollingHash(const string &s, ull base) : base(base) {
ll n = s.size();
hashed.assign(n + 1, 0);
power.assign(n + 1, 0);
power[0] = 1;
for (ll i = 0; i < n; i++) {
power[i + 1] = mul(power[i], base);
hashed[i + 1] = mul(hashed[i], base) + s[i];
if (hashed[i + 1] >= MOD)
hashed[i + 1] -= MOD;
}
}
ull get(ll l, ll r) const {
ull ret = hashed[r] + MOD - mul(hashed[l], power[r - l]);
if (ret >= MOD)
ret -= MOD;
return ret;
}
ull connect(ull h1, ull h2, ll h2len) const {
ull ret = mul(h1, power[h2len]) + h2;
if (ret >= MOD)
ret -= MOD;
return ret;
}
void connect(const string &s) {
ll n = hashed.size() - 1, m = s.size();
hashed.resize(n + m + 1);
power.resize(n + m + 1);
for (ll i = n; i < n + m; i++) {
power[i + 1] = mul(power[i], base);
hashed[i + 1] = mul(hashed[i], base) + s[i - n];
if (hashed[i + 1] >= MOD)
hashed[i + 1] -= MOD;
}
}
ll LCP(const RollingHash &b, ll l1, ll r1, ll l2, ll r2) {
ll len = min(r1 - l1, r2 - l2);
ll low = -1, high = len + 1;
while (high - low > 1) {
ll mid = (low + high) / 2;
if (get(l1, l1 + mid) == b.get(l2, l2 + mid))
low = mid;
else
high = mid;
}
return low;
}
};
/**
* @brief Rolling Hash
*/