AtCoder Beginner Contest 141 E - Who Says a Pun?

E - Who Says a Pun?

解説で別解として紹介されている二分探索＋ローリングハッシュで通したので書いておきます。

解法

条件を満たす長さで二分探索

「文字列 $S$ の連続部分文字列として位置が重ならずに2回以上出現する、長さ $L$ の文字列が存在する」ということを単に「長さ $L$ は条件を満たす」と呼ぶことにします。

注目すべき性質として、もし長さ $L$ が条件を満たす場合、必ず長さ $L-1$ も条件を満たします。単に長さ $L$ で条件を満たしている文字列の末尾を除いた文字列を考えれば良いです。

この性質から二分探索ができるので、「長さ $L$ をある値に固定した時、それは条件を満たすか？」という判定問題が解ければ良いことになります。

ローリングハッシュで一致判定

判定問題を解くために「ローリングハッシュ」というものを使います。これはある与えられた文字列について、その部分文字列の一致判定を大量に行いたい時に便利なアルゴリズムです。

ハッシュとは文字列などをある規則で整数（ハッシュ値）に変換したもので、2つの文字列をそれぞれ変換した整数が一致していれば文字列が一致したと見なします。与えられた文字列について前計算を行っておくことで、部分文字列のハッシュを $O(1)$ で計算できるのがローリングハッシュです。

固定したある長さ $L$ について、開始位置を1つずつずらしながら長さ $L$ の部分文字列のハッシュ値を求めていきます。そして「既に登場したハッシュ値」をsetなどに入れておくことで、同じハッシュ値が2回登場した時に検出することができます。

ただし「位置が重ならない」という条件があるので、求めたハッシュ値を即座にsetに入れてはいけません。今見ている位置と重ならなくなったタイミング、具体的には S.substr(i, L) を見る直前のタイミングで S.substr(i-L, L) のハッシュ値をsetに入れると良いです。ここで S.substr(s, l) は開始位置 $s$ 、長さ $l$ の部分文字列を表します。

f:id:betrue12:20190916012509p:plain

この方法で、位置が重ならずに2回以上登場する長さ $L$ の部分文字列があるかを判定できます。二分探索の判定1回の中でハッシュ値を最大で $N$ 個setに入れるので、setの $\log$ と二分探索の $\log$ が付いて全体計算量は $O(N(\log N)^{2})$ になります。

ハッシュの衝突について

文字列をハッシュ値に変換するときに、異なる文字列を変換して同じハッシュ値になることがあり得ます。これをハッシュの「衝突」と呼びます。

もちろんその確率が十分小さくなるように工夫しますが、今回のような問題だと「最大 $N$ 個のハッシュ値のうち1ペアでも衝突したらアウト」なので、「誕生日のパラドックス」と呼ばれる性質によりそこそこの確率で衝突します。

それを避ける方法として、パラメータが異なる複数のハッシュ値を用意しておいて、その全てが一致したら文字列が一致したと判定する方法があります。また特定のパラメータに対して衝突を起こすような恣意的な入力や、コードを見てから衝突ケースを流し込めるCodeforcesのhackなどに対策するために、乱数でパラメータを決定する場合もあります。

以下のACコードではパラメータが異なる2つのハッシュ値を計算しています。