文字列の一致判定について

いよいよハッシュ関数を用いて、文字列の一致判定を行います。

決定的アルゴリズムなので、S = T ならば、H(S) = H(T) であることを利用し、文字列が一致しているかを確認します。

このように、文字列判定を行うアルゴリズムをRolling Hashと呼びます。

ここで、Rolling Hashには落とし穴があります。それは、全く違う文字列であるのにもかかわらずハッシュ値が一致してしまうハッシュ衝突があることです。

たとえば、P = 4957, X = 4139 として、H("PAIZA") と H("HELLO") を計算してみてください。どちらも 2817 になっていると思います。

このようなハッシュ衝突を完全に避けることは、定義域よりより小さい値域に移すというハッシュ関数の性質がある以上不可能です。

しかし、以下の対策をとることによって、ハッシュ衝突の確率を無視できるほど小さくすることができます。

値域を大きいものにする(今回でいうならば十分に大きい P を用いる)

複数のハッシュ関数で判定を行う(今回でいうならば複数の (P,X) のペアを用いて判定する。)

では、実際に行ってみましょう。

(問題)

N 個の英大文字列 S_1, S_2, ..., S_N が与えられます。S_i = S_j となるペア (i,j) (1 ≦ i < j ≦N) の個数を求めてください。