This documentation is automatically generated by online-judge-tools/verification-helper
#include "String/rollinghash.hpp"
#pragma once
#include "Utility/random.hpp"
#include "Math/hash.hpp"
struct RollingHash {
using ull = unsigned long long;
const Hash base;
vector<Hash> hashed, power;
static inline ull genbase() {
return Random::get(ull(0x1fffffffffffffff));
}
RollingHash(Hash base) : base(base) {}
template <typename STR> void build(const STR &s) {
int 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] = power[i] * base;
hashed[i + 1] = hashed[i] * base + s[i];
}
}
Hash get(ll l, ll r) const {
return hashed[r] - hashed[l] * power[r - l];
}
Hash connect(Hash h1, Hash h2, ll h2len) const {
return h1 * power[h2len] + h2;
}
template <typename STR> void connect(const STR &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] = power[i] * base;
hashed[i + 1] = hashed[i] * base + s[i - n];
}
}
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 multi, bool self>
vector<pair<int, int>> genGraph(int n, int m) {
vector<pair<int, int>> cand, es;
rep(u, 0, n) rep(v, 0, n) {
if (!self and u == v)
continue;
if (!directed and u > v)
continue;
cand.push_back({u, v});
}
if (m == -1)
m = get(SZ(cand));
// chmin(m, SZ(cand));
vector<int> ord;
if (multi)
rep(_, 0, m) ord.push_back(get(SZ(cand) - 1));
else {
ord = select(m, 0, 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 2 "Math/hash.hpp"
struct Hash {
static constexpr ull mod = 0x1fffffffffffffff;
ull v;
static constexpr ull get_mod() {
return mod;
}
constexpr ull inv() const {
assert(v != 0);
ull x = v, y = mod, p = 1, q = 0, t = 0, tmp = 0;
while (y > 0) {
t = x / y;
x -= t * y, p -= t * q;
tmp = x, x = y, y = tmp;
tmp = p, p = q, q = tmp;
}
if (p < 0)
p += mod;
return p;
}
constexpr Hash(ll x = 0) : v(x >= 0 ? x % mod : (mod - (-x) % mod) % mod) {}
Hash operator-() const {
return Hash() - *this;
}
Hash pow(ull t) {
Hash res = 1, b = *this;
while (t) {
if (t & 1)
res *= b;
b *= b;
t >>= 1;
}
return res;
}
Hash &operator+=(const Hash &x) {
if ((v += x.v) >= mod)
v -= mod;
return *this;
}
Hash &operator-=(const Hash &x) {
if ((v += mod - x.v) >= mod)
v -= mod;
return *this;
}
Hash &operator*=(const Hash &x) {
u128 ans = u128(v) * x.v;
ans = (ans >> 61) + (ans & mod);
if (ans >= mod)
ans -= mod;
v = ans;
return *this;
}
Hash &operator/=(const Hash &x) {
v = ull(v) * x.inv() % mod;
return *this;
}
Hash operator+(const Hash &x) const {
return Hash(*this) += x;
}
Hash operator-(const Hash &x) const {
return Hash(*this) -= x;
}
Hash operator*(const Hash &x) const {
return Hash(*this) *= x;
}
Hash operator/(const Hash &x) const {
return Hash(*this) /= x;
}
bool operator==(const Hash &x) const {
return v == x.v;
}
bool operator!=(const Hash &x) const {
return v != x.v;
}
// mapに載せる時用
bool operator<(const Hash &x) const {
return v < x.v;
}
bool operator<=(const Hash &x) const {
return v <= x.v;
}
bool operator>(const Hash &x) const {
return v > x.v;
}
bool operator>=(const Hash &x) const {
return v >= x.v;
}
friend istream &operator>>(istream &is, Hash &x) {
return is >> x.v;
}
friend ostream &operator<<(ostream &os, const Hash &x) {
return os << x.v;
}
};
void rd(Hash &x) {
fastio::rd(x.v);
}
/**
* @brief Hash
*/
#line 4 "String/rollinghash.hpp"
struct RollingHash {
using ull = unsigned long long;
const Hash base;
vector<Hash> hashed, power;
static inline ull genbase() {
return Random::get(ull(0x1fffffffffffffff));
}
RollingHash(Hash base) : base(base) {}
template <typename STR> void build(const STR &s) {
int 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] = power[i] * base;
hashed[i + 1] = hashed[i] * base + s[i];
}
}
Hash get(ll l, ll r) const {
return hashed[r] - hashed[l] * power[r - l];
}
Hash connect(Hash h1, Hash h2, ll h2len) const {
return h1 * power[h2len] + h2;
}
template <typename STR> void connect(const STR &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] = power[i] * base;
hashed[i + 1] = hashed[i] * base + s[i - n];
}
}
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
*/