問題タブ [rabin-karp]

たとえば、string1:"AB" は string2:"CABA" にある必要があります。string1 h1=('A'*27 + 'B') および h2=('A'*29 + 'B') の場合、string2 の場合は hash1 および hash2 関数を計算します (h2.1='C'*27 + 'A', h2.2='C'*29 + 'C') そして、結果を string1 のハッシュ関数と比較します。

すべての文字列または部分文字列に対して異なるベースを持つ 2 つのハッシュ関数が必要な理由がわかりません。

How to extend rabin karp to look for an mxm pattern among nxn characters?

Can anyone come up with a pseudo code? And Will there be any affect on the time complexity of the algorithm?

関数のソース コード ( Rabin Karp アルゴリズム) をパスカル (フリー パスカル バージョン) で提供してもらえますか?

Karp-Rabin を実装し、テスト ファイルと 2 番目の部分で実行するという 2 つの宿題の問題があります。

2. q を法とするハッシュ値について、q を 2 の累乗として使用することがなぜ悪い考えなのかを説明してください。たとえば、q=64 と n=15 の場合のひどい例を作成できますか?

これはアルゴリズムの私の実装です:

...質問の2番目の部分は、コード/アルゴリズムのこの部分を参照しています:

q を 2 のべき乗として使用することがなぜ悪い考えなのか理解できません。提供されたテスト ファイル (ecoli のゲノム) でアルゴリズムを実行してみましたが、識別可能な違いはありません。

ハッシュがどのように導出されるかについての式を調べてみました (私は数学が苦手です)。q が 2 の累乗である場合、ハッシュに対して多くの衝突が発生するはずなので、文字列をさらに比較する必要があるように感じますが、それらの線に沿って何も見つかりませんでした。

私は困惑しているので、これについて助けていただければ幸いです。最初の部分で改善できる点 (コードの効率、読みやすさ、正確さなど) を誰かが指摘したい場合は、それについての意見もお待ちしています。

karp-rabin 部分文字列マッチング アルゴリズムを実装しています。私の実装は、部分文字列に対して hash_string() メソッドを呼び出すと正常に動作しますが、ローリング ハッシュを実装すると失敗します。ローリング ハッシュ値が増え続けていますが、その理由がわかりません。

より具体的には、ここで問題が発生します。

部分文字列の長さが同じままであっても、ローリング ハッシュ値は桁違いに増加します。このローリング ハッシュの実装は正しいですか?

Rabin Karp は複数のパターンで高速であることは知っていますが、同じ長さにする必要があります。しかし、今では10パターンの長さが異なり、テキストで検索する必要があります。どのように効果的に機能しますか? ありがとう！

素数で除算してハッシュをモジュラス値に減らした後、ローリング ハッシュ アルゴリズムがどのように機能するかを理解するのに苦労しています。

数字の 5 桁のシーケンスを考えてみましょう123456。

最初のチャンクは12345. 値を保存すると、次のウィンドウで 6 が入って 1 が出てきます。

したがって、新しいハッシュは(12345-1*10^4)*10 + 6 = 23456. これはかなり直感的です。

明らかなように、これらの数値は大きいため、数値を小さく保つモジュラス関数が必要です。101この目的のために素数を取るとします。

したがって12345、 に減少し23ます。では、これから、次のウィンドウのローリング ハッシュをどのように導き出すの23456でしょうか?

dはアルファベットの大きさ は
T[1...n]検索する文字列
P[1...m]はパターン（mはパターンの大きさ）
qは素数

h = d^m-1 (mod q)m 桁のテキスト ウィンドウの上位位置にある桁 "1" の値です。

この行はどういう意味ですか? とはどういう意味hですか?