ローリングハッシュ LIB::RollingHash

LIB::RollingHash

長さNとMの文字列に対して文字列検索をすると計算量
https://qiita.com/keymoon/items/11fac5627672a6d6a9f6
https://zenn.dev/hellorusk/articles/c2de32c2295093f8721c

メンバ関数

RollingHash(string& sin, u64 base)

ハッシュ値を計算したい文字列sinと基数を入力
基数は乱数を使うと良い

hash(l,r)

コンストラクタで入力した文字列について半開区間[l,r)のハッシュ値を返す

使い方

srand((unsigned int)time(NULL));
ll base=rand()%987;
RollingHash rh(S,base);

注意点

128bit整数を使うのでboostのインクルードが必要

#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using namespace boost;

namespace LIB {
	class RollingHash {
	private:
		using u64=unsigned long long;
		using u32=unsigned int;
		using i128=multiprecision::int128_t;
		static constexpr u64 mod=(1uLL<<61)-1;
		u64 base;
		std::string s;
		std::vector<u64> htable, pow;
		u64 mul(i128 a, i128 b) const {
			i128 t=a*b;
			t=(t>>61)+(t&mod);
			if(t>=mod) return (u64)(t-mod);
			return (u64)t;
		}
		u32 xorshift(u32 x) const {
			x^=x<<13,x^=x>>17,x^=x<<5;
			return x;
		}
	public:
		RollingHash(const RollingHash&)=default;
		RollingHash(RollingHash&&)=default;
		RollingHash():base(0),s() {};
		RollingHash(string& sin, u64 base):base(base),s(sin) {
			htable.resize(s.size()+1,0);
			pow.resize(s.size()+1,1);
			for(u64 i=0; i<s.size(); i++) {
				htable[i+1]=mul(htable[i],base)+xorshift((u32)(s[i]+1));
				pow[i+1]=mul(pow[i],base);
				if(htable[i+1]>=mod) htable[i+1]-=mod;
			}
		}
		u64 hash() const { return htable.back(); }
		u64 hash(u64 l, u64 r) const {
			u64 ret=mod+htable[r]-mul(htable[l],pow[r-l]);
			return ret<mod?ret:ret-mod;
		}
		u64 size() const { return s.size(); }
	};
}

実装例

https://atcoder.jp/contests/abc141/submissions/44445437