G - Edit to Match 解説
by 
Kiri8128
ハッシュを使う方法
\(S_k\) の長さを \(l_k\) とします。 \(k\) 番目を見るとき、前から \(c\) 文字が一致するものが \(S_1\) から \(S_{k-1}\) までに出現していたら、それらのうち最も短いものの長さを \(l_{min}\) として \(l_k + l_{min} - 2c\) を達成できます。 既に現われた接頭辞をすべてハッシュ化し、それらのうち最も短いものの長さを dict で管理すれば、すべての \(c\) について調べても間に合います。
ハッシュはローリングハッシュやランダムベクトルとの内積を取る方法などがあります。
実装例（Python）
ハッシュの衝突率
ハッシュ 1 回の衝突率を \(\displaystyle\frac{1}{P}\) とすると、ケースごとの衝突率は \(\displaystyle\frac{L^2}{P}\) 以下なので \(P\) を \(\displaystyle\frac{L^2}{\varepsilon}\) 程度にすれば \(1-\varepsilon\) 程度以上の確率で AC することができます。
ただし \(L=\displaystyle \sum_{i=1}^N |S_i|\) です。 dict を全体でひとつではなく長さごとに管理するとケースごとの衝突率は \(\displaystyle\frac{N^2}{P}\) 以下になります。
投稿日時:
最終更新: