string/rolling_hash.cpp
Code
#pragma once
#include <bits/stdc++.h>
using namespace std;
using u64 = unsigned long long;
constexpr u64 M = 2305843009213693951; // 2^61 - 1
constexpr u64 MASK31 = 2147483647; // 2^31 - 1
constexpr u64 MASK30 = 1073741823; // 2^30 - 1
constexpr u64 POSITIVIZER = 4 * M;
u64 CalcMod(u64 x) {
u64 res = (x >> 61) + (x & M);
if (res >= M) res -= M;
return res;
}
u64 mul(u64 x, u64 y) {
u64 au = (x >> 31), ad = (x & MASK31), bu = (y >> 31), bd = (y & MASK31);
u64 m = au * bd + ad * bu;
u64 mu = (m >> 30), md = (m & MASK30);
u64 ans = ((au * bu) << 1) + mu + (md << 31) + ad * bd;
return CalcMod(ans);
}
struct RollingHash {
static u64 B;
int N;
vector<u64> hash, power;
RollingHash(const string &s) {
N = (int)s.size();
hash.resize(N + 1, 0);
power.resize(N + 1, 0);
hash[0] = 0;
power[0] = 1;
for (int i = 0; i < (int)s.size(); ++i) {
hash[i + 1] = CalcMod(mul(hash[i], B) + s[i]);
power[i + 1] = mul(power[i], B);
}
}
u64 get() { return hash[N]; }
u64 get(int k) { return hash[k]; }
u64 get(int l, int r) { return CalcMod(hash[r] + POSITIVIZER - mul(hash[l], power[r - l])); }
};
mt19937_64 mt;
uniform_int_distribution<unsigned long long> rng(2, M - 2);
unsigned long long RollingHash::B = rng(mt);
/*
// two 32bit MOD version
struct RollingHash {
using u64 = unsigned long long;
static const u64 M1 = 2147483647,M2 = 1000000007;
static u64 B1,B2;
int N;
vector<u64> hash1,hash2,power1,power2;
RollingHash(string &s) {
N = s.size();
power1.resize(N + 1); power2.resize(N + 1); hash1.resize(N + 1); hash2.resize(N + 1);
power1[0] = 1; power2[0] = 1; hash1[0] = 0; hash2[0] = 0;
for (int i = 0;i < N; ++i) {
power1[i + 1] = power1[i] * B1 % M1;
power2[i + 1] = power2[i] * B2 % M2;
hash1[i + 1] = (hash1[i] * B1 + s[i]) % M1;
hash2[i + 1] = (hash2[i] * B2 + s[i]) % M2;
}
}
// return hash of S
pair<u64,u64> get() {
return make_pair(hash1[N],hash2[N]);
}
// return hash of S[0,k)
pair<u64,u64> get(int k) {
return make_pair(hash1[k],hash2[k]);
}
// return hash of S[l,r)
pair<u64,u64> get(int l,int r) {
u64 x = (hash1[r] - (hash1[l] * power1[r - l]) % M1 + M1) % M1;
u64 y = (hash2[r] - (hash2[l] * power2[r - l]) % M2 + M2) % M2;
return make_pair(x,y);
}
//return if S[l1,r1) == S[l2,r2)
bool equal(int l1,int r1,int l2,int r2) {
return get(l1,r1) == get(l2,r2);
}
};
mt19937_64 mt;
uniform_int_distribution<unsigned long long> rand1(2,RollingHash::M1 - 2);
uniform_int_distribution<unsigned long long> rand2(2,RollingHash::M2 - 2);
unsigned long long RollingHash::B1 = rand1(mt);
unsigned long long RollingHash::B2 = rand2(mt);
using u64 = unsigned long long;
using Pu = pair<u64,u64>;
*/
#line 2 "string/rolling_hash.cpp"
#include <bits/stdc++.h>
using namespace std;
using u64 = unsigned long long;
constexpr u64 M = 2305843009213693951; // 2^61 - 1
constexpr u64 MASK31 = 2147483647; // 2^31 - 1
constexpr u64 MASK30 = 1073741823; // 2^30 - 1
constexpr u64 POSITIVIZER = 4 * M;
u64 CalcMod(u64 x) {
u64 res = (x >> 61) + (x & M);
if (res >= M) res -= M;
return res;
}
u64 mul(u64 x, u64 y) {
u64 au = (x >> 31), ad = (x & MASK31), bu = (y >> 31), bd = (y & MASK31);
u64 m = au * bd + ad * bu;
u64 mu = (m >> 30), md = (m & MASK30);
u64 ans = ((au * bu) << 1) + mu + (md << 31) + ad * bd;
return CalcMod(ans);
}
struct RollingHash {
static u64 B;
int N;
vector<u64> hash, power;
RollingHash(const string &s) {
N = (int)s.size();
hash.resize(N + 1, 0);
power.resize(N + 1, 0);
hash[0] = 0;
power[0] = 1;
for (int i = 0; i < (int)s.size(); ++i) {
hash[i + 1] = CalcMod(mul(hash[i], B) + s[i]);
power[i + 1] = mul(power[i], B);
}
}
u64 get() { return hash[N]; }
u64 get(int k) { return hash[k]; }
u64 get(int l, int r) { return CalcMod(hash[r] + POSITIVIZER - mul(hash[l], power[r - l])); }
};
mt19937_64 mt;
uniform_int_distribution<unsigned long long> rng(2, M - 2);
unsigned long long RollingHash::B = rng(mt);
/*
// two 32bit MOD version
struct RollingHash {
using u64 = unsigned long long;
static const u64 M1 = 2147483647,M2 = 1000000007;
static u64 B1,B2;
int N;
vector<u64> hash1,hash2,power1,power2;
RollingHash(string &s) {
N = s.size();
power1.resize(N + 1); power2.resize(N + 1); hash1.resize(N + 1); hash2.resize(N + 1);
power1[0] = 1; power2[0] = 1; hash1[0] = 0; hash2[0] = 0;
for (int i = 0;i < N; ++i) {
power1[i + 1] = power1[i] * B1 % M1;
power2[i + 1] = power2[i] * B2 % M2;
hash1[i + 1] = (hash1[i] * B1 + s[i]) % M1;
hash2[i + 1] = (hash2[i] * B2 + s[i]) % M2;
}
}
// return hash of S
pair<u64,u64> get() {
return make_pair(hash1[N],hash2[N]);
}
// return hash of S[0,k)
pair<u64,u64> get(int k) {
return make_pair(hash1[k],hash2[k]);
}
// return hash of S[l,r)
pair<u64,u64> get(int l,int r) {
u64 x = (hash1[r] - (hash1[l] * power1[r - l]) % M1 + M1) % M1;
u64 y = (hash2[r] - (hash2[l] * power2[r - l]) % M2 + M2) % M2;
return make_pair(x,y);
}
//return if S[l1,r1) == S[l2,r2)
bool equal(int l1,int r1,int l2,int r2) {
return get(l1,r1) == get(l2,r2);
}
};
mt19937_64 mt;
uniform_int_distribution<unsigned long long> rand1(2,RollingHash::M1 - 2);
uniform_int_distribution<unsigned long long> rand2(2,RollingHash::M2 - 2);
unsigned long long RollingHash::B1 = rand1(mt);
unsigned long long RollingHash::B2 = rand2(mt);
using u64 = unsigned long long;
using Pu = pair<u64,u64>;
*/
Back to top page