Rabin Karpアルゴリズムの法でローリングハッシュがどのように機能するかを理解する

Question

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

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

最初のチャンクは12345です。私は値を保存し、次のウィンドウに6が入り、1が外に出る。

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

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

したがって12345は23に縮小されます。それでは、どうすれば次のウィンドウのローリングハッシュを得ることができますか？23456？

Answer 1

23456と同じ方法で計算しますが、常にモジュロ101で計算します。

(((23 - (10^4 mod 101))*10) mod 101 + 6) mod 101 = 24. 

これは23456 mod 101 = 24なので、これは値です。