串拉賓，卡普初等數符號

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 ==（模5）。

整數可以根據它們的餘數模n分成n個等價類。含有整數a的等價類模n是

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

例如，[3] 7 = {。 。 。 ，-11，-4，3，10，17，...。 。 };其他指標是[-4,7和10]。

寫a屬於[b] n與寫a == b（mod n）相同。該組的所有這樣的等價類是

鋅= {[α] N：0 < =一個< = N - 1} .---------->公式1個

我的問題在上面的文本中，在等式1中提到了「a」應當在0和n-1之間，但是在實例中它被給出爲-4而不在0和6之間，爲什麼？

除了上面提到的是，對於Rabin-Karp算法，我們使用兩個數的等價模以第三個數？這是什麼意思？

Answer 1

這不是一個編程的問題，但從來沒有介意

中提到，「一」應該是0和n-1之間，但例如，在它被賦予爲-4這是不在0到6之間，爲什麼？

因爲[-4] n與[x] n是相同的等價類，因此對於某些x使得0 < = x < n。所以方程式1利用了這個事實來「定義」定義並使所有可能性不同。

除了上面提到的是，對於Rabin-Karp算法，我們使用兩個數的等價模以第三個數？這是什麼意思？

Rabin-Karp算法要求您爲正在搜索的子字符串計算散列值。散列時，使用散列函數很重要，即使對於很小的字符串，也可以使用整個可用域。如果您的散列是一個32位整數，並且您只需將相繼的unicode值加在一起，那麼您的散列通常會非常小，導致大量衝突。

所以你需要一個功能，可以給你很大的答案。不幸的是，這也暴露了整數溢出的可能性。因此你使用模算術來防止比較被溢出搞亂。

Answer 2

我會盡量讓你朝正確的方向發展，儘管這不是關於編程。

帶-4的例子是一個等價類的例子，它是一組與所給數字相等的所有數字。因此，在[3] 7中，所有數字都是等效的（模7）到3，並且包括-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。