哈希

Error

我们可以将值存储在其每个前缀处，而不是仅仅计算序列的哈希值。请注意，这些将是等于相应前缀的序列的哈希值。

有了这样的结构，就可以快速计算出这个序列的任意子段的哈希值（类似于前缀和）。

如果我们要计算子段 [l;r] 的哈希值，那么我们需要将前缀 r 上的哈希值减去前缀 l-1 上的哈希值乘以 p 的 r-l+1 次方。如果您将值写在前缀上并看看会发生什么，那么为什么会这样就很清楚了。我希望你能成功看到这张照片。



作为这些操作的结果，我们得到了原始序列的一个子段的散列。此外，如果将此散列视为来自等于此子段的序列的散列，则该散列等于该散列（不需要额外的度数转换等与其他值进行比较）。

这里有两点需要说明：
1）要快速乘以p的r-l+1次方，需要预先计算p的所有可能的次方模模。
2) 必须记住，我们执行所有计算模模，因此可能会在减去前缀哈希后得到一个负数。为避免这种情况，您始终可以在减去之前添加 mod。另外，不要忘记在乘法和所有加法之后取模值。

在代码中它看起来像这样：
  #include ; 使用命名空间标准； typedef long longll； 常数 MAXN = 1000003； // 基础和哈希模块 ll p, mod; // 前缀散列和指数 p h[MAXN], pows[MAXN]; // 计算子段 [l;r] 的散列 ll get_segment_hash(int l, int r) { return (h[r] + mod - h[l - 1] * pows[r - l + 1] % mod) % mod; } 主函数() { // 以某种方式得到 p 和 mod // 预先计算幂 p 战俘[0] = 1; for (int i = 0; i < MAXN; i++) pows[i] = (pows[i - 1] * p) % mod; // // 主要问题解决 // 返回 0； }

如果我们有字符串 A 的哈希值等于 h_A 字符串 B 的哈希值等于 h_B，那么我们可以快速计算出字符串 AB 的哈希值：
h_AB = h_A * p^|B| + h_B   <- 对所有事物进行模数计算
|B|在哪里- 字符串 B 的长度。

除了序列之外，您还可以散列集。也就是说，没有顺序的对象集。根据以下公式计算：
hash(A) = \(\sum_{a \in A} p^{ord(a)}\)   <- 对所有事物进行模数计算
其中 ord 是一个函数，它将所有可能对象中的绝对序数分配给集合中的一个对象（例如，如果对象是自然数，则 ord(x) = x，如果是小写拉丁字母，则 ord(& #39;a' ;) = 1, ord('b') = 2 等）

也就是说，对于每个对象，我们将一个等于基数的值与该对象的数量次方相关联，并将所有这些值相加，以获得整个集合的哈希值。从公式中可以清楚地看出，如果将元素添加到集合或从集合中删除（只需添加或减去所需的值），则很容易重新计算哈希。同样的道理， 如果不是添加或删除单个元素，而是添加或删除其他集合（只需添加/减去它们的散列）。

正如您已经了解的那样，单个元素被视为大小为 1 的集合，我们可以为其计算哈希。更大的集合只是这些单个集合的并集，通过组合集合，我们添加它们的哈希值。

事实上，这仍然是相同的多项式哈希，但在 p^m  处的系数之前，我们有值数 n - m - 1 下的序列元素（其中 n 是序列的长度），现在这是集合中绝对序数等于 m 的元素数。

在这种散列中，必须采用足够大的基数（大于最大集合大小），或者使用双重散列来避免出现绝对序数为 m 的一组 p 个对象与具有一个绝对序数的对象的集合具有相同散列的情况序数 m+1.
 

还有几种方法可以有效地散列有根树。 
其中一种方法安排如下：
我们按照深度遍历的顺序递归地处理顶点。我们假设单个顶点的哈希值等于 p。对于有孩子的顶点，我们首先为他们运行算法，然后通过孩子我们将计算当前子树的散列。为此，将子树的哈希值视为一个数字序列，并根据该序列计算哈希值。这将是当前子树的散列。
如果孩子的顺序对我们不重要，那么在计算哈希之前，我们从孩子子树中排序哈希序列，然后从排序后的序列计算哈希。

通过这种方式，您可以检查树的同构性 - 只需计算哈希而不对孩子排序（即，每次对孩子的哈希进行排序）。如果根的哈希匹配，则树是同构的，否则不是。

对于无根树，一切都以类似的方式发生，但质心必须作为根。或者，如果有两个质心，则考虑一对哈希。