私は現在、Rabin Karp アルゴリズムについて読んでおり、その一環として、文字列多項式ハッシュを理解する必要があります。私が理解していることから、文字列のハッシュは次の式で与えられます。
hash = ( char_0_val * p^0 + char_1_val * p^1 + ... + char_n_val ^ p^n ) mod m
どこ：
- char_i_val: によって与えられる文字に 1 を加えた整数値です。
string[i]-'a' + 1 - p は、文字セットより大きい素数です
- m は大きな素数です
Web サイト cp-algorithms には、件名に関する次のエントリがあります。上記を記述するコードは次のようになると言われています。
long long compute_hash(string const& s) {
const int p = 31;
const int m = 1e9 + 9;
long long hash_value = 0;
long long p_pow = 1;
for (char c : s) {
hash_value = (hash_value + (c - 'a' + 1) * p_pow) % m;
p_pow = (p_pow * p) % m;
}
return hash_value;
}
プログラムが何をしようとしているのかは理解できますが、なぜそれが正しいのかわかりません。
私の質問
上記のコードが正しい理由を理解できません。モジュラー計算を行ってから長い時間が経ちました。オンラインで検索したところ、剰余加算と剰余乗算の次の式があることがわかりました。
a+b (mod m) = (a%m + b%m)%m
a*b (mod m) = (a%m * b%m)%m
上記に基づいて、コードは次のようになるべきではありませんか？
long long compute_hash(string const& s) {
const int p = 31;
const int m = 1e9 + 9;
long long hash_value = 0;
long long p_pow = 1;
for (char c : s) {
int char_value = (c - 'a' + 1);
hash_value = (hash_value%m + ((char_value%m * p_pow%m)%m)%m ) % m;
p_pow = (p_pow%m * p%m) % m;
}
return hash_value;
}
私は何が欠けていますか？理想的には、コードの内訳と最初のバージョンが正しい理由の説明を求めています。