Cormen文字列私はCormenによってアルゴリズムの導入によりラビン - カープ文字列検索アルゴリズムを読んでいますラビン - カープ

Question

を合わせるなど

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

注意==スライド上の注意事項上記のmod演算子

として使用されています13すなわち式34.2を参照してください。方程式では、m桁のテキストウィンドウの高位位置のh ==（d）powerof（（m-1）（mod q）は数字 "1"の値です）

ここで私の質問は何ですか著者番号：

スライド14では、著者は（7-3.3）.10 + 2（mod 13）を8（ mod 13）？

平均的なケース分析では、モジュロqの値を減らすことは、シグマ*からZへのランダムマッピングのように動作するという仮定に基づいてヒューリスティックな分析を行うことができると述べられています。

Answer 1

あなたの2番目の質問は、ちょうど-ve数のモジュラー算術についてのようです。これを考える方法の1つは、Mを0 mod Mに相当するので、mod Mを自由に追加したり減算したりすることができるということです。したがって、（7-3.3）.10 + 2（mod 13） = -2.10 + 2 = -18 = 13 + 13-18 = 8 mod 13

あなたの最初の質問は私にはあまり明確ではありませんが、詳しく説明します。文字ウィンドウに文字が最初に表示されると、その文字ウィンドウがテキストウィンドウに沿って移動し、最終的にはそのすべてのメモリが削除されます。ハッシュ値。

まず、文字xを見て、これまでのハッシュ値に加えて、h.d + xを得ます。次の文字を見ると、dでそれを掛けて（そして私が説明しようとしている他のものを行います）、次に新しい文字を追加します。だから我々は... + x * d + yを得る。次のステップは、我々に+ x * d * d + y * d + zを与える。文字を取り除こうとすると、x * d ^（m-1）+ ...のハッシュ値を持ちます。ここで....はxの後の文字のみに依存します。したがって、dを乗算する前にx * d ^（m-1）を減算することで、xのハッシュ値への影響を取り除くことができます。