mmrz's library

This documentation is automatically generated by online-judge-tools/verification-helper

---

Project maintained by mm-rz Hosted on GitHub Pages — Theme by mattgraham

ローリングハッシュ
(string/rolling_hash.hpp)

• View this file on GitHub
• Last update: 2025-07-01 03:22:56+09:00
• Include: #include "string/rolling_hash.hpp"

ローリングハッシュ

使い方

添え字は 0-indexed であることに注意。

• rolling_hash(string s) : $s$ のハッシュ値の前計算を行う $O(\lvert s \rvert)$
• ull slice(int begin, int length) : $s$ の $begin$ 文字目から $length$ 文字のハッシュを返す。

概要

参考

MOD $2^{61}-1$ を採用している。MOD をランダムにしていないため、文字列の統合等をしなくとも、文字長が同じであれば一致判定を行うことができる。

Verified with

• verify/aoj/alds1/14_B.test.cpp

Code

#pragma once

#include<string>
#include<vector>

struct rolling_hash {
	using ull = unsigned long long;

	const ull MASK30 = (1UL << 30) - 1;
	const ull MASK31 = (1UL << 31) - 1;
	const ull MOD = (1UL << 61) - 1;
	const ull MASK61 = MOD;
	const ull POSITIVIZER = MOD * ((1UL << 3) - 1);

	std::string s;
	int n;
	const ull bs = 23948798;

	std::vector<ull> base_pow;
	std::vector<ull> prefix_hash;

	rolling_hash(std::string _s){
		s = _s;
		n = int(s.size());
		base_pow.resize(n + 1);
		base_pow[0] = 1;
		for(int i = 0;i < n;i++){
			base_pow[i + 1] = calcmod(mul(base_pow[i], bs));
		}	

		prefix_hash.resize(n + 1, 0LL);
		for(int i = 0;i < n;i++){
			prefix_hash[i + 1] = calcmod(mul(prefix_hash[i], bs) + s[i]);	
		}
	}

	ull slice(int begin, int length){
		return calcmod(prefix_hash[begin + length] + POSITIVIZER - mul(prefix_hash[begin], base_pow[length]));
	}

	//a * b % mod (2^{61} - 1)
	ull mul(ull a, ull b){
		ull au = a >> 31;
		ull ad = a & MASK31;
		ull bu = b >> 31;
		ull bd = b & MASK31;
		ull mid = ad * bu + au * bd;
		ull midu = mid >> 30;
		ull midd = mid & MASK30;
		return calcmod(au * bu * 2 + midu + (midd << 31) + ad * bd);
	}

	// mod(2^{61} - 1)
	ull calcmod(ull x){
		ull xu = x >> 61;
		ull xd = x & MASK61;
		ull res = xu + xd;
		if (res >= MOD) res -= MOD;
		return res;
	}
};

#line 2 "string/rolling_hash.hpp"

#include<string>
#include<vector>

struct rolling_hash {
	using ull = unsigned long long;

	const ull MASK30 = (1UL << 30) - 1;
	const ull MASK31 = (1UL << 31) - 1;
	const ull MOD = (1UL << 61) - 1;
	const ull MASK61 = MOD;
	const ull POSITIVIZER = MOD * ((1UL << 3) - 1);

	std::string s;
	int n;
	const ull bs = 23948798;

	std::vector<ull> base_pow;
	std::vector<ull> prefix_hash;

	rolling_hash(std::string _s){
		s = _s;
		n = int(s.size());
		base_pow.resize(n + 1);
		base_pow[0] = 1;
		for(int i = 0;i < n;i++){
			base_pow[i + 1] = calcmod(mul(base_pow[i], bs));
		}	

		prefix_hash.resize(n + 1, 0LL);
		for(int i = 0;i < n;i++){
			prefix_hash[i + 1] = calcmod(mul(prefix_hash[i], bs) + s[i]);	
		}
	}

	ull slice(int begin, int length){
		return calcmod(prefix_hash[begin + length] + POSITIVIZER - mul(prefix_hash[begin], base_pow[length]));
	}

	//a * b % mod (2^{61} - 1)
	ull mul(ull a, ull b){
		ull au = a >> 31;
		ull ad = a & MASK31;
		ull bu = b >> 31;
		ull bd = b & MASK31;
		ull mid = ad * bu + au * bd;
		ull midu = mid >> 30;
		ull midd = mid & MASK30;
		return calcmod(au * bu * 2 + midu + (midd << 31) + ad * bd);
	}

	// mod(2^{61} - 1)
	ull calcmod(ull x){
		ull xu = x >> 61;
		ull xd = x & MASK61;
		ull res = xu + xd;
		if (res >= MOD) res -= MOD;
		return res;
	}
};

Back to top page