0

我正在阅读 Cormen 等人的算法简介中的字符串算法

以下是关于一些基本数论符号的文本。

注意：在下面的文本中，将 == 引用为模等价。

给定一个整数除以另一个整数的余数的定义明确的概念，提供特殊符号来表示余数相等是很方便的。如果 (a mod n) = (b mod n)，我们写 a == b (mod n) 并说 a 等价于 b，模 n。换句话说，如果 a 和 b 除以 n 时具有相同的余数，则 a == b (mod n)。等效地，a == b (mod n) 当且仅当 n | (b-a)。例如，61 == 6（模 11）。此外，-13 == 22 == 2 == (mod 5)。

整数可以根据余数模n分为n个等价类。包含整数 a 的等价类模 n 是

[a]n = {a + kn : k Z} 。

例如，[3]7 = {。. . , -11, -4, 3, 10, 17, . . .}; 该集合的其他表示是 [-4]7 和 [10]7。

写 a 属于 [b]n 与写 a == b (mod n) 相同。所有这些等价类的集合是

Zn = {[a]n : 0 <= a <= n - 1}.---------> 等式 1

我在上面的文字中的问题是在等式1中提到“a”应该在0和n-1之间，但在示例中它被给出为-4，它不在0和6之间，为什么？

除了上面提到的，对于 Rabin-Karp 算法，我们使用两个数模第三个数的等价性？这是什么意思？

4

2 回答 2

1

我会尝试将您推向正确的方向，即使这与编程无关。

其中带有-4的示例是等价类的示例，它是与给定数字等价的所有数字的集合。因此，在 [3]7 中，所有数字都与 3 等价（模 7），其中包括 -4 以及 17 和 710 以及无穷多个其他数字。

您也可以将同一个类命名为 [10]7，因为每个等价于（模 7）到 3 的数同时等价于（模 7）到 10。

最后一个定义给出了一组所有不同的等价类，并指出对于模 7，它们中正好有 7 个，并且可以由 0 到 6 的数字产生。你也可以说

Zn = {[a]n : n <= a < 2 * n}

并且含义将保持不变，因为 [0]7 与 [7]7 相同，而 [6]7 与 [13]7 相同。

于 2011-12-29T09:01:46.323 回答
0

这不是一个编程问题，但没关系......

提到“a”应该在 0 和 n-1 之间，但在示例中它被给出为 -4，它不在 0 和 6 之间，为什么？

因为对于某些 x 使得 [-4]n 与 [x]n 的等价类相同，因此 0 <= x < n。因此等式 1 利用这一事实来“整理”定义并使所有可能性变得不同。

除了上面提到的，对于 Rabin-Karp 算法，我们使用两个数模第三个数的等价性？这是什么意思？

Rabin-Karp 算法要求您计算要搜索的子字符串的哈希值。散列时，重要的是使用一个使用整个可用域的散列函数，即使对于非常小的字符串也是如此。如果您的散列是一个 32 位整数，并且您只是将连续的 unicode 值相加，那么您的散列通常会非常小，从而导致大量冲突。

因此，您需要一个可以为您提供大量答案的函数。不幸的是，这也使您面临整数溢出的可能性。因此，您使用模算术来防止比较被溢出弄乱。

于 2011-12-29T09:15:44.247 回答