algo — C++23 日本語リファレンス
GitHub

RollingHash

クラス · ローリングハッシュ

struct RollingHash;

概要

ローリングハッシュ

法 $2^{61}-1$ の Horner 法で prefix hash を持つ。 base はプログラム実行のたびに乱数で決まる（意図的な衝突を避けるため）。

計算量

構築・破棄

名前 説明 計算量
(constructor) (1) 空文字列用のhashを構築する
(2) 文字列sのprefix hashを構築する		 (1) $O(1)$
(2) $O(n)$

メンバ関数

名前 説明 計算量
derive 同じ基数で別の文字列をhash化する $O(n)$
get_base 使用中の基数を返す $O(1)$
get (1) 文字列全体のhashを返す
(2) prefix s[0,r)のhashを返す
(3) 部分文字列s[l,r)のhashを返す		 $O(1)$
substr s.substr(pos,len)のhashを返す $O(1)$
search pattern sとhashが一致する開始位置を列挙する 元文字列長を $n$、pattern長を $m$ として $O(n+m)$

メンバの詳細

(constructor)

// (1)
RollingHash();

// (2)
explicit RollingHash(const std::string &s, HashInt base = random_hash_base());

(1) 空文字列用のhashを構築する

(2) 文字列sのprefix hashを構築する

get

// (1)
HashInt get() const;

// (2)
HashInt get(int r) const;

// (3)
HashInt get(int l, int r) const;

(1) 文字列全体のhashを返す

(2) prefix s[0,r)のhashを返す

(3) 部分文字列s[l,r)のhashを返す

参照