JAG Summer Camp 2015 Day 2 F - ほぼ周期文字列

• 問題
• AC

ローリングハッシュを使う。

文字列$s$とインデックス$x, y$が与えられたとき、$s$の接尾辞$s[x..]$と$s[y..]$のLCP（最長共通接頭辞）の長さを$\operatorname{LCP}(x, y)$とする。$s$の区間$[l, r)$が周期$t$の文字列であることは、$\operatorname{LCP}(l, l+t) \ge r-(l+t)$であることと同値である。まず、これが成り立てばYesを返してよい。

$\operatorname{LCP}(l, l+t) < r-(l+t)$の場合、文字$s[l+\operatorname{LCP}(l, l+t)]$と$s[l+t+\operatorname{LCP}(l, l+t)]$が異なっている。一方の文字をもう一方の文字に変更すれば周期$t$の文字列になる可能性がある。

これを確かめるためには、連続部分列$s[l .. r-t]$と$s[l+t .. r]$について、$s[l+\operatorname{LCP}(l, l+t)]$を$s[l+t+\operatorname{LCP}(l, l+t)]$に変えたもの（あるいはその逆）のハッシュ値が等しいか調べればよい。

---

ローリングハッシュを初めて使った。例題と聞いて手をつけたのでLCPを使う方針はすぐに浮かんだが、正しい実装に時間がかかった。以下はメモ。

• ローリングハッシュに偽陽性（異なる文字列に対して同じハッシュ値を返す）はあるが偽陰性（一致する文字列に対して異なるハッシュ値を返す）はないので、2つの文字列を複数modで比較してひとつでもハッシュ値が異なれば異なる文字列である。
• LCPの場合、偽陽性は真の値より長い区間をLCPと判定するという形で現れるので、複数modによる最小値をLCPの長さとして採用すればよい。