哈希
stripe_python
·
·
算法·理论
多项式哈希
用于快速判断两个序列是否相同。
对于长为 n 的序列 a_i,选定底数 B 和模数 M 后,定义 a_i 的哈希值为
\text{HASH}(a_i)=\left(\sum_{i=1}^n a_i \times B^{i-1}\right) \bmod M
多项式哈希是滚动的过程,因此可以对 a_i 的每个前缀预处理一个前缀哈希 h_i=\text{HASH}(a_{[1,i]})。此时有
\text{HASH}(a_{[l,r]})=h_r-h_{l-1} \times B^{r-l+1}
另外,多项式哈希是一种半群信息,可以配合线段树等数据结构。
树哈希
用于快速判断两棵树是否同构。
对 u 所在子树,定义其哈希值为
\text{HASH}(u)=1+\sum_{v \in \text{son}(u)} f\left(\text{HASH}(v) \right)
其中 f 为 \mathbb{N} \to \mathbb{N} 的一个映射。
这种哈希容易换根,因此无根树同构问题可以转化为集合哈希。
集合哈希
用于快速判断两个集合是否相同。
Sum Hash
对于集合 S,选定模数 M,定义其哈希值为
\text{HASH}(S)=\sum_{x \in S} f(x)
其中 f 是一个 S \to \mathbb{N} 的映射。
Xor Hash
对于集合 S,定义其哈希值为
\text{HASH}(S)=\bigoplus_{x \in S} f(x)
其中 f 是一个 S \to \mathbb{N} 的映射。
多用于一些特殊情形,如与奇偶性相关的问题。
f
上文提及的 f 可以如下设计:对于每个整数,将其随机映射到 [0,2^{64}) 内的一个整数。哈希表维护。
其他
P6688。
将区间减去最小值。定义集合 S 的哈希值为 \text{HASH}(S)=\left(\sum \limits_{x \in S} g^x\right) \bmod M。
线段树维护之,复杂度 O(q \log n)。submission。
P10992。
定义 p_i 为 i 之前该位置字符最后一次出现的位置,对序列 i-p_i 做多项式哈希,可以滚动。
二分答案,滑动窗口扫两遍判定,复杂度 O(n \log n)。submission。
CF1479D。
单次询问考虑二分答案,用 Xor Hash 来判定。
对值域建可持久化线段树,每个节点存一棵树,查询先差分开,然后线段树上二分。复杂度 O(q \log n)。
CF452F。
枚举等差中项,在值域上等差数列转化成一个回文串。
线段树维护正反哈希判定。O(n \log n)。