RollingHash2D

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

struct RollingHash2D;

概要

二次元ローリングハッシュ

行方向・列方向にそれぞれ別の基数を持つ二次元 Horner 法で構築する。 base_x/base_y はプログラム実行のたびに乱数で決まる（意図的な衝突を避けるため）。

計算量

構築は $O(hw)$、矩形hashは $O(1)$

構築・破棄

名前	説明	計算量
`(constructor)`	(1) 空盤面用のhashを構築する (2) 二次元列gridのhashを構築する (3) 文字列行列gridのhashを構築する	(1) $O(1)$ (2) $O(hw)$ (3) $O(hw)$

メンバ関数

名前	説明	計算量
`derive`	(1) 同じ基数で別の二次元列をhash化する (2) 同じ基数で別の文字列行列をhash化する	$O(hw)$
`get_base_x`	行方向の基数を返す	$O(1)$
`get_base_y`	列方向の基数を返す	$O(1)$
`get`	(1) 盤面全体のhashを返す (2) 矩形grid[x1,x2)[y1,y2)のhashを返す	$O(1)$

メンバの詳細

(constructor)

// (1)
RollingHash2D();

// (2)
template <class T>
explicit RollingHash2D(const std::vector<std::vector<T>> &grid, HashInt base_x = random_hash_base(), HashInt base_y = random_hash_base());

// (3)
explicit RollingHash2D(const std::vector<std::string> &grid, HashInt base_x = random_hash_base(), HashInt base_y = random_hash_base());

(1) 空盤面用のhashを構築する

計算量: $O(1)$

(2) 二次元列gridのhashを構築する

計算量: $O(hw)$

(3) 文字列行列gridのhashを構築する

計算量: $O(hw)$

derive

// (1)
template <class T>
RollingHash2D derive(const std::vector<std::vector<T>> &grid) const;

// (2)
RollingHash2D derive(const std::vector<std::string> &grid) const;

(1) 同じ基数で別の二次元列をhash化する

計算量: $O(hw)$

(2) 同じ基数で別の文字列行列をhash化する

計算量: $O(hw)$

get

// (1)
HashInt get() const;

// (2)
HashInt get(int x1, int x2, int y1, int y2) const;

(1) 盤面全体のhashを返す

計算量: $O(1)$

(2) 矩形grid[x1,x2)[y1,y2)のhashを返す

計算量: $O(1)$