2025 Summer Day20

课堂内容

字符串哈希

定义哈希函数 $H(s)$:

其中 $base$ 大于字符集大小。这个哈希函数的冲突概率为 $\frac{1}{P}$。

通过这个定义，我们可以通过前缀和处理，得到这个字符串上每个区间的哈希值。

树哈希 （重点）

定义哈希函数 $H(u)$，表示以 $u$ 为根节点的子树的哈希值。

其中 $son(u, i)$ 表示 $u$ 的第 $i$ 个儿子，$size(u)$ 表示以 $u$ 为根节点的子树的大小。

字典树

字典树就没什么好讲的了，注意一下 0/1 字典树就行。