(ハッシュ関数について)

問題 3 までで事前知識について学習してきたので、ここではハッシュ関数について学習していきます。

ハッシュ関数とは、簡単にいうと、入力に対して、ダイジェストを生成する関数です。

具体的には、ある定義域と定義域より小さい値域に対して、定義域の要素を値域の要素に移す決定的アルゴリズムのことです。

決定的アルゴリズムであるため、同じ入力には同じ出力を行います。そのためダイジェストを生成する際の決まり事を作る必要があります。

今回は素数 P に対して任意の長さの英大文字列を、0 から P - 1 の整数に移す事を考えます。

決まった出力を行う関数であれば、ハッシュ関数として使うことが出来ますが、今回の問題集では以下のような関数を考えます。

2 以上 P - 1 以下の整数 X を 1 つ決める。

長さ N の英大文字列 S に対して、次のような長さ N の配列 T = (T_1, T_2, T_3, ..., T_N) を考える。T_i は S の i 文字目が A ならば 1、B ならば 2、C ならば 3、...、Y なら 25、Z なら 26 である。

ハッシュ値 H(S) を H(S) = T_1 × X ^ {N - 1} + T_2 × X ^ {N - 2} + ... + T_N (mod P) と定める。

では実際に計算してみましょう。

(問題)

素数 P と 2 以上 P - 1 以下の整数 X と長さ N の英大文字列 S が与えられます。上記のハッシュ値 H(S) を計算してください。