問題タブ [rabin-karp]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
string - Rabin Karp アルゴリズムのローリング ハッシュに mod を組み込む方法は?
mod を使用して Rabin Karp アルゴリズムを実装しようとしています。私が使用しているハッシュ関数は次のとおりです。
ここで、cx は文字の ASCII 値です。それをロールするには、最初の項を減算して削除し、次に a を掛けて、新しい項に a^0 を掛けて追加します。
今問題は、mod 操作を使用した大きな値を処理することですが、それを行うと、正しくロールすることができません。私のコードは次のとおりです。
問題は、どの時点でも一致textHashしpatternHashないことです。問題はmod操作にあると確信しています。mod を使用する方法と、ローリング ハッシュを正しく使用する方法を教えてください。とても感謝しています。
rabin-karp - Karp-Rabin アルゴリズム
以下の画像は : 6.006-Introduction to algorithm からのものです。
MIT OCW が提供するコース 6.006-アルゴリズムの紹介を行っているときに、Rabin-Karp アルゴリズムに出会いました。
最初の rs()==rt() が必要な理由を理解できる人はいますか? もしそれが使われているなら、文字列が等しいかどうかを力ずくで確認してから先に進むべきではありませんか? ハッシュが t[0] から行われ、他の文字列の一致を見つけようとするときに、文字列の等価性を考慮していないのはなぜですか?
画像では、rs() はハッシュ値用であり、rs.skip[arg] は、'arg' であると仮定して、その文字列の最初の文字を削除することです。</p>