字符串 Rabin-Karp 基本数字符号

Question

我正在阅读 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 (mod 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 belongs to [b]n 等同于写 a == b (mod n)。所有这些等价类的集合是

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

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

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

Answer 1

我会尽力引导您朝着正确的方向前进，即使这与编程无关。

其中带-4的例子是一个等价类的例子，它是所有等价于给定数字的数字的集合。因此，在 [3]7 中，所有数字都等于(模 7)3，其中包括 -4 以及 17 和 710 以及其他无穷大。

您也可以将同一个类命名为 [10]7，因为每个等于(模 7)3 的数字同时等于(模 7)10。

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

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

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