(部分文字列のハッシュ計算について)

ここでは、S の部分文字列に注目していきます。今回 S の L 文字目から R 文字目までの部分文字列を V とします。

今回の問題集では、素数 P と 2 以上 P - 1 以下の整数 X について S のハッシュ値は以下のように計算しています。

H(S) = T_1 × X ^ {N - 1} + T_2 × X ^ {N - 2} + ... + T_L × X ^ {N - L} + T_{L + 1} × X ^ {N - L - 1} + ... + T_R × X ^ {N - R} + ... + T_N (mod P) (T_i は S の i 文字目が A ならば 1、B ならば 2、C ならば 3、...、Y なら 25、Z なら 26)

同様に V に対しても計算できます。

H(V) = T_L × X ^ {R - L} + T_{L + 1} × X ^ {R - L - 1} + ... + T_R (mod P)

上記の式を見比べてみます。H(S) には T_L × X ^ {N - L} + T_{L + 1} × X ^ {N - L - 1} + ... + T_R × X ^ {N - R} = X ^ {N - R} × (T_L × X ^ {R - L} + T_{L + 1} × X ^ {R - L - 1} + ... + T_R) = X ^ {N - R} × H(V) という部分がありここを上手く取り出すことで H(V) を計算することが出来ます。

取り出し方について見ていきます。

事前に、S のハッシュ値をfor文で前からそれぞれの項を足し合わせて計算する最中に記録をとることで、すべての i (1 ≦ i ≦ N) に対して h_i = T_1 × X ^ {N - 1} + T_2 × X ^ {N - 2} + ... + T_i × X ^ {N - i} は計算することが出来ます。これらの値を用いることで、T_L × X ^ {N - L} + T_{L + 1} × X ^ {N - L - 1} + ... + T_R × X ^ {N - R} = h_R - h_{L - 1} (mod P) (ただし、h_0 = 0) と計算することが出来ます。この値を、X ^ {N - R} で割る、つまり、X ^ {N - R} の逆元を掛けることによって、H(V) を計算できます。

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

(問題)

素数 P と 2 以上 P - 1 以下の整数 X と長さ N の英大文字列 S が与えられます。Q 個のクエリに対して前から順番に処理してください。i (1 ≦ i ≦ Q) 番目のクエリは以下の通りです。

S の L_i 文字目から R_i 文字目までの部分文字列のハッシュ値を出力する。ただし、ハッシュ値の計算方法は問題 4 の方法とする。