文字列ハッシュ
文字列ハッシュにはさまざまな手法がありますが、このコースでは、その中でも特に一般的で実装が直感的な方法を取り上げます。これは競技プログラミングコンテストやアルゴリズム関連の面接で広く利用されています。
たとえば、文字列 s があり、その文字を とします。これらの部分文字列に対して簡単にハッシュを計算できる仕組みを用意したいとしましょう。
強いハッシュ関数を選ぶ
実際によく使われる強いハッシュ関数の一例として、文字列を受け取り、文字の整数値それぞれに、ある素数の累乗を掛けあわせ、最後に m で割る（mod する）手法があります。
ここで p と m はいずれも素数です。たとえば p としては 1997 や 127 などがよく使われます。また m を大きく設定すると衝突（collision）が起こりにくくなりますが、大きすぎると計算速度が落ちる可能性があります。そのため、よく使用される値として 10^9 + 7 や 10^9 + 9 などがあります。以下のように実装できます。
s = input() # ユーザーが入力する任意の長さの文字列
p = 1997 # p: 素数
m = 1_000_000_007 # m: 十分に大きな素数
h = [0] * (len(s) + 1) # h を 0 で初期化
for i in range(len(s)):
h[i + 1] = h[i] + ord(s[i]) # 現在の文字を加算
h[i + 1] *= p # すべての p の累乗を 1 つずつ上げる
h[i + 1] %= m # 毎回 mod m をとるここでは、すべてのインデックスに対してローリングハッシュを求めています（見た目は prefix sum に似ています）。
この実装では、h の最初の要素（h[0]）はダミーの 0 になっています。また、各 h[k+1] は h[k] に依存する形になっています。
任意の部分文字列のハッシュを計算する
同じ長さの部分文字列 s[l1; r1) と s[l2; r2) を取り、両者が同じかどうかを判定したい場合、それぞれの部分文字列について正規化されたハッシュを計算し、その値が等しければ文字列としても等しいとみなしたいところです。
いま、h 関数を用いて文字列 s のハッシュを計算できるようになりましたが、左右のインデックスの単純な差分だけで部分文字列のハッシュを求めるわけにはいきません。
l と r が与えられたとき、s[l; r) のハッシュを算出したいとします。理想的には、s[l; r) だけを新しい文字列として0から計算したハッシュと同じ値を得たいわけです。各文字に素数 p の累乗を掛けているため、左側を (r - l) の分だけ補正する必要があります。
これは、もし s[l; r) を先頭から改めてハッシュした場合に得られる値と同じです。先頭文字に対する p の累乗が (r-l) となり、最後の文字が p^1 になるのも想定どおりです。
このように [1; 5) と [4; 8) のように別の区間を比べたい場合でも、p の累乗の違いで結果が変わることはありません。同じ文字列なら区間が異なってもハッシュが同じになるように、h[l] を (r - l) 乗でスケーリングします。
# べき乗を事前に計算
pows = [1] * (len(s) + 1) # すべての p の累乗をあらかじめ格納
for i in range(len(s)): # 1...n の累乗
pows[i + 1] = pows[i] * p # p^i = p^(i-1) * p
pows[i + 1] %= m # 毎回 mod m をとる
# [l; r) のハッシュを O(1) で計算
res = h[r] - h[l] * pows[r - l] # (r-l) 乗を用いて h[l] をスケーリング
res %= m # mod m をとる
print(res)たとえば入力文字列 s が hello hellyo だった場合、h や pows は以下のようになり、いくつかのハッシュクエリに対して次の結果が得られます。
# s -> h e l l o h e l l y o
h = [0, 207688, 414954633, 664611981, 230332444, 974109122, 295966923, 46148782, 159318707, 159671329, 863857463, 123583173, 795816426]
pows = [1, 1997, 3988009, 964053924, 215672753, 698484731, 873998049, 374091638, 60995857, 808725582, 24975949, 876969810, 308698313]
# i -> 0 1 2 3 4 5 6 7 8 9 10 11 12
# hash for s[0: 3] (hel) -> 664611981 (l = 0, r = e)
# hash for s[6: 9] (hel) -> 664611981 (l = 6, r = 9)
# hash for s[0: 5] (hello) -> 974109122 (l = 0, r = 5)
# hash for s[6: 11] (helly) -> 974129092 (l = 6, r = 11)文字列にハッシュをかけて、特定の部分文字列のハッシュを求める準備はできましたか？
入力
最初の行に文字列 s が与えられます (1 ≤ |s| ≤ )。
次の行にはクエリの数 q (1 ≤ q ≤ 100 000) が与えられます。
続く q 行には、インデックスの組 (0 ≤ ≤ |s|) が与えられます。
出力
各クエリについて、区間 のハッシュ値を出力してください。
例
入力 | 出力 |
|---|---|
hello hellyo | 664611981 |
Constraints
Time limit: 2.4 seconds
Memory limit: 512 MB
Output limit: 1 MB