From 9874851b92a86d65e0d26fc423f5982233ec9ef0 Mon Sep 17 00:00:00 2001 From: Tianyi Qiu Date: Wed, 2 Dec 2020 13:00:24 +0800 Subject: [PATCH] minor fix --- docs/misc/rand-technique.md | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/docs/misc/rand-technique.md b/docs/misc/rand-technique.md index 54dcc8ad..3293e310 100644 --- a/docs/misc/rand-technique.md +++ b/docs/misc/rand-technique.md @@ -286,7 +286,7 @@ $$ 要判断是否存在长度 $=L$ 的坏串，只需把 $\{f_{0,*,L}\}$ 和 $\{f_{1,*,L}\}$ 各自“整合”起来再比较即可（通配符 `*` 这里表示每一个结点，例如 $\{f_{0,*,L}\}$ 表示全体 $f_{0,i,L}$ 构成的集合，其中 $i$ 取遍所有结点）。官方题解[^ref2]中证明了最短坏串（如果存在的话）长度一定不超过 $n_1+n_2$ ，所以这个解法的复杂度是可靠的。 -接下来考虑具体的哈希方式。注意到常规的哈希方法——即把串 $a_1a_2\cdots a_k$ 映射到 $\big(a_1+Pa_2+P^2a_3+\cdots+P^{k-1}a_k\big)\bmod Q$ 上、再把多重集的哈希值定为其中元素的哈希值之和模 $Q$ ——在这里是行不通的。一个反例是，集合 `{ab,cd}` 与集合 `{"cb","ad"}` 的哈希值是一样的，不论 $P,Q$ 如何取值。 +接下来考虑具体的哈希方式。注意到常规的哈希方法——即把串 $a_1a_2\cdots a_k$ 映射到 $\big(a_1+Pa_2+P^2a_3+\cdots+P^{k-1}a_k\big)\bmod Q$ 上、再把多重集的哈希值定为其中元素的哈希值之和模 $Q$ ——在这里是行不通的。一个反例是，集合 `{"ab","cd"}` 与集合 `{"cb","ad"}` 的哈希值是一样的，不论 $P,Q$ 如何取值。 上述做法的问题在于，一个串的哈希值是一个和式，从而其中的每一项可以拆出来并重组。为避免这一问题，我们考虑把哈希值改为一个连乘式。此外，乘法交换律会使得不同的位不可区分，为避免这一点我们要为不同的位赋予不同的权值。 -- 2.11.0