問題タブ [rabin-karp]

だから私はこの問題（Rabin Karpのアルゴリズム）を解決していて、この解決策を書きました：

mod = 1000000007 の場合、このコードは単純に機能しませんが、他の素数 (1e5+7 などの十分な大きさ) を取得するとすぐに、コードは魔法のように機能し始めます!

コードのロジックが失敗した行は次のとおりです。

なぜこれが起こっているのか誰か教えてください??? たぶんこれはばかげた疑問ですが、私には理解できません。

Python でのパターン検索用に Rabin-Karp 2D アルゴリズムを実装しました。ただし、私の実装は、1000x2000 マトリックスでブルート フォース バージョンよりも遅くなります。ボトルネックを特定するのを手伝ってください。ありがとう、そして私はあなたのコメントに感謝します。

注1：コードはパターンが一致する位置を見つけるのに適していますが、私のコンピューターのブルートフォースバージョンでは0.54秒に対して1.23秒です。

注 2: Rabin-Karp が力ずくで遅くなるような最悪のケースを考え出すことはできますが、与えられたテスト ケースは意図的に O(m(n-m+1)) にするように設計されていません。

免責事項 : この問題は Sedgewick と Wayne による Algorithms, 4th Edition の割り当て問題ですが、私の宿題ではありません。私はこのアルゴリズムを学んでいます。

コードは次のとおりです。

私は現在、Rabin Karp アルゴリズムについて読んでおり、その一環として、文字列多項式ハッシュを理解する必要があります。私が理解していることから、文字列のハッシュは次の式で与えられます。

どこ：

• char_i_val: によって与えられる文字に 1 を加えた整数値です。string[i]-'a' + 1
• p は、文字セットより大きい素数です
• m は大きな素数です

Web サイト cp-algorithms には、件名に関する次のエントリがあります。上記を記述するコードは次のようになると言われています。

プログラムが何をしようとしているのかは理解できますが、なぜそれが正しいのかわかりません。

私の質問

上記のコードが正しい理由を理解できません。モジュラー計算を行ってから長い時間が経ちました。オンラインで検索したところ、剰余加算と剰余乗算の次の式があることがわかりました。

上記に基づいて、コードは次のようになるべきではありませんか？

私は何が欠けていますか？理想的には、コードの内訳と最初のバージョンが正しい理由の説明を求めています。