文字列ラビン - カープ基本数表記

Question

私は以下のCormenなど

によってアルゴリズムの紹介のStringアルゴリズムについて読んでいますが、いくつかの基本的数論の表記に関するテキストです。

注：以下の文章では、モジュロ同値としてのrefere ==です。

ある整数の残りの部分を別のものに分割してよく定義された概念が与えられている場合、余りの等価を示すために特別な表記を提供すると便利です。 （a mod n）=（b mod n）なら、a == b（mod n）と書いて、aはbをmod nに等しくすると言う。言い換えると、aとbがnで除算されたときに同じ剰余を持つ場合、a == b（mod n）です。同様に、a | = b（mod 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を[b] nに書くことは、a == b（mod n）と書くことと同じです。私の質問.---------->式1

- ：そのようなすべての同値類のセットは

のZn = {1 0 <は= < = N [A] N}であります上の文章では、方程式1に "a"は0とn-1の間でなければならないと述べられていますが、例として、0から6の間ではない-4として与えられます。

上記に加えて、Rabin-Karpアルゴリズムでは、3番目の数を法とする2つの数値の等価性を使用することが言及されていますか？これは何を意味するのでしょうか？

Answer 1

これは、プログラミングの質問ではありませんが、気にしない...

それが「」0とn-1の間であることを述べているが、一例では、それがある-4のように与えられます0と6の間ではなく、なぜですか？

[-4] N [X] nとして例えば0 < = X < Nその一部xに対して同じ等価クラスであるので。したがって、方程式1は、事実を利用して定義を「整理」し、すべての可能性を区別します。ラビン - カープ文字列検索アルゴリズムのために、我々は2つの数の等価の第3の数を法として使用することが記載されている上記に加え

？これは何を意味するのでしょうか？

Rabin-Karpアルゴリズムでは、検索する部分文字列のハッシュ値を計算する必要があります。ハッシングの場合、非常に小さな文字列に対しても、利用可能なドメイン全体を使用するハッシュ関数を使用することが重要です。ハッシュが32ビットの整数で、連続したユニコード値を加算するだけの場合、ハッシュ値は通常は非常に小さくなり、多くの衝突が発生します。

あなたには大きな回答を与える機能が必要です。残念ながら、これは整数オーバーフローの可能性も示します。したがって、モジュロ算術を使用して、比較がオーバーフローによって混乱しないようにします。

Answer 2

プログラミングに関してではありませんが、私は正しい方向にあなたを微調整しようとします。

-4を含む例は等価クラスの例であり、これは与えられた数に等しいすべての数の集合です。したがって、[3] 7では、すべての数値は3と等価（7を法とする）で、-4と17と710、およびその他の無限を含みます。 3に相当し、すべての数（モジュロ7）が10

に同じ時間相当（モジュロ7）であるため、

また、最後の定義が与え、同じクラス[10] 7に名前を付けることができすべて明確な同値クラスのセット、およびモジュロ7のために、正確に7それらのがあり、そして0から6までの数字で製造することができます。また、

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

を言うことができると意味が残ると述べています[0] 7は[7] 7と同じものなので、[6] 7は[13] 7と同じものです。