2

Introduction to Algorithms by Cormen などで Rabin-Karp アルゴリズムを読んでいます。

www.cs.uml.edu/~kdaniels/courses/ALG_503_F08/503_lecture11.ppt

== が mod 演算子として使用されていることに注意してください

上記のスライド 13 の注記、つまり式 34.2 は、ここに図として添付されています。方程式では、h == (d)powerof((m-1) (mod q) は、m 桁のテキスト ウィンドウの上位位置にある桁 "1" の値です。

ここでの私の質問は、「m桁のテキストウィンドウの上位位置にある数字「1」の値」とはどういう意味ですか?

スライド 14 で、著者はどのようにして (7-3.3).10 + 2 (mod 13) を 8 (mod 13) として得たのでしょうか?

Average case analysis では、q を法として値を減らすことは sigma* から Z へのランダムなマッピングのように機能するという仮定に基づいてヒューリスティック分析を行うことができると述べられています。

4

1 に答える 1

1

あなたの 2 番目の質問は、-ve 数値を使用した剰余算術についてのようです。これを考える 1 つの方法は、M は 0 mod M と等しいので、mod M を使用すると M を好きなだけ追加または減算できるということです。つまり、(7-3.3).10 + 2 (mod 13) = -2.10 + 2 = -18 = 13 + 13 - 18 = 8 mod 13

あなたの最初の質問は私にはよくわかりませんが、詳しく説明させてください。文字が最初にテキスト ウィンドウに表示されたとき、その文字は単に追加されます。次に、文字はテキスト ウィンドウに沿って移動します。最後に、その文字のすべてのメモリを削除して、文字がテキスト ウィンドウから出た後、文字に影響を与えないようにします。ハッシュ値。

最初に文字 x を見て、それをこれまでのハッシュ値に追加すると、hd + x が得られます。次の文字が表示されたら、それを d で乗算し (そして、説明しようとしている他のことを行います)、新しい文字を追加します (y とします)。したがって、... + x*d + y が得られます。次のステップでは、... + x*d*d + y*d + z が得られます。文字を取り除こうとすると、x*d^(m-1) + .... のハッシュ値が得られます。ここで .... は、x の後の文字のみに依存します。したがって、d を掛ける前に x*d^(m-1) を引くことにより、ハッシュ値に対する x の影響を取り除くことができます。

于 2011-12-30T11:20:48.373 に答える