noya2_Library
This documentation is automatically generated by online-judge-tools/verification-helper
string/rolling_hash.hpp
- View this file on GitHub
- Last update: 2026-04-22 14:52:50+09:00
- Include:
#include "string/rolling_hash.hpp"
Code
#pragma once
#include<vector>
#include<string>
#include<cassert>
#include<ranges>
#include<random>
namespace noya2 {
struct rolling_hash {
using ull = unsigned long long;
rolling_hash(){}
rolling_hash(const std::string &s){
build(s | std::ranges::to<std::vector<char>>());
}
template<typename T>
rolling_hash(const std::vector<T> &s){
build(s);
}
static ull get_hash(const std::string &s){
int len = s.size();
set_hash();
extend_pow_base(len);
ull res = 0;
for (int i = 0; i < len; i++){
res = cal_mod(mul_mod(res, BASE) + s[i]);
}
return res;
}
template<typename T>
static ull get_hash(const std::vector<T> &s){
int len = s.size();
set_hash();
extend_pow_base(len);
ull res = 0;
for (int i = 0; i < len; i++){
res = cal_mod(mul_mod(res, BASE) + s[i]);
}
return res;
}
ull prod(int l, int r){
return cal_mod(inner_hash[r] + POSITIVISER - mul_mod(inner_hash[l], pow_base[r - l]));
}
size_t size() const { return inner_hash.size() - 1u; }
template<class... Hash_Lengths>
static ull concat(const Hash_Lengths&... hash_length){
return inner_concat(0ULL, hash_length...);
}
private:
static ull inner_concat(const ull& temp){
return temp;
}
template<class... Tail> static ull inner_concat(const ull& temp, const ull& hash, const int& len, const Tail&... tail){
return inner_concat(cal_mod(cal_mod(mul_mod(temp, pow_base[len])) + hash), tail...);
}
static constexpr ull MASK30 = (1ULL << 30) - 1;
static constexpr ull MASK31 = (1ULL << 31) - 1;
static constexpr ull MASK61 = (1ULL << 61) - 1;
static constexpr ull MOD = (1ULL << 61) - 1;
static constexpr ull POSITIVISER = MOD * 4;
static ull BASE;
static std::vector<ull> pow_base;
static ull mul_mod(ull a, ull b){
ull au = a >> 31, ad = a & MASK31;
ull bu = b >> 31, bd = b & MASK31;
ull mid = ad * bu + au * bd;
ull midu = mid >> 30, midd = mid & MASK30;
return (au * bu * 2 + midu + (midd << 31) + ad * bd);
}
static ull cal_mod(ull x){
ull xu = x >> 61;
ull xd = x & MASK61;
ull res = xu + xd;
if (res >= MOD) res -= MOD;
return res;
}
static void set_hash(){
if (BASE == 0) BASE = (1UL << 31) + (std::random_device()() & MASK31);
}
static void extend_pow_base(int len){
int nlen = pow_base.size();
if (nlen > len) return ;
pow_base.resize(len + 1);
for (int i = nlen; i <= len; i++){
pow_base[i] = cal_mod(mul_mod(pow_base[i - 1],BASE));
}
}
std::vector<ull> inner_hash;
template<typename T>
void build(const std::vector<T> &s){
set_hash();
int n = s.size();
extend_pow_base(n);
inner_hash.resize(n + 1);
inner_hash[0] = 0;
for (int i = 0; i < n; i++){
inner_hash[i + 1] = cal_mod(mul_mod(inner_hash[i], BASE) + s[i]);
}
}
};
unsigned long long rolling_hash::BASE = 0;
std::vector<unsigned long long> rolling_hash::pow_base = {1};
using roriha = rolling_hash;
} // namespace noya2#line 2 "string/rolling_hash.hpp"
#include<vector>
#include<string>
#include<cassert>
#include<ranges>
#include<random>
namespace noya2 {
struct rolling_hash {
using ull = unsigned long long;
rolling_hash(){}
rolling_hash(const std::string &s){
build(s | std::ranges::to<std::vector<char>>());
}
template<typename T>
rolling_hash(const std::vector<T> &s){
build(s);
}
static ull get_hash(const std::string &s){
int len = s.size();
set_hash();
extend_pow_base(len);
ull res = 0;
for (int i = 0; i < len; i++){
res = cal_mod(mul_mod(res, BASE) + s[i]);
}
return res;
}
template<typename T>
static ull get_hash(const std::vector<T> &s){
int len = s.size();
set_hash();
extend_pow_base(len);
ull res = 0;
for (int i = 0; i < len; i++){
res = cal_mod(mul_mod(res, BASE) + s[i]);
}
return res;
}
ull prod(int l, int r){
return cal_mod(inner_hash[r] + POSITIVISER - mul_mod(inner_hash[l], pow_base[r - l]));
}
size_t size() const { return inner_hash.size() - 1u; }
template<class... Hash_Lengths>
static ull concat(const Hash_Lengths&... hash_length){
return inner_concat(0ULL, hash_length...);
}
private:
static ull inner_concat(const ull& temp){
return temp;
}
template<class... Tail> static ull inner_concat(const ull& temp, const ull& hash, const int& len, const Tail&... tail){
return inner_concat(cal_mod(cal_mod(mul_mod(temp, pow_base[len])) + hash), tail...);
}
static constexpr ull MASK30 = (1ULL << 30) - 1;
static constexpr ull MASK31 = (1ULL << 31) - 1;
static constexpr ull MASK61 = (1ULL << 61) - 1;
static constexpr ull MOD = (1ULL << 61) - 1;
static constexpr ull POSITIVISER = MOD * 4;
static ull BASE;
static std::vector<ull> pow_base;
static ull mul_mod(ull a, ull b){
ull au = a >> 31, ad = a & MASK31;
ull bu = b >> 31, bd = b & MASK31;
ull mid = ad * bu + au * bd;
ull midu = mid >> 30, midd = mid & MASK30;
return (au * bu * 2 + midu + (midd << 31) + ad * bd);
}
static ull cal_mod(ull x){
ull xu = x >> 61;
ull xd = x & MASK61;
ull res = xu + xd;
if (res >= MOD) res -= MOD;
return res;
}
static void set_hash(){
if (BASE == 0) BASE = (1UL << 31) + (std::random_device()() & MASK31);
}
static void extend_pow_base(int len){
int nlen = pow_base.size();
if (nlen > len) return ;
pow_base.resize(len + 1);
for (int i = nlen; i <= len; i++){
pow_base[i] = cal_mod(mul_mod(pow_base[i - 1],BASE));
}
}
std::vector<ull> inner_hash;
template<typename T>
void build(const std::vector<T> &s){
set_hash();
int n = s.size();
extend_pow_base(n);
inner_hash.resize(n + 1);
inner_hash[0] = 0;
for (int i = 0; i < n; i++){
inner_hash[i + 1] = cal_mod(mul_mod(inner_hash[i], BASE) + s[i]);
}
}
};
unsigned long long rolling_hash::BASE = 0;
std::vector<unsigned long long> rolling_hash::pow_base = {1};
using roriha = rolling_hash;
} // namespace noya2