AtCoder Regular Contest 077 F. SS

本質的な補題を証明してから解いたら3時間ぐらいかかった。解説見たらその部分「周期の最小性より」で省略されてたけど、そんな単純に成り立つものだと僕は思えてないんだよね、そんな簡単に証明できる？？？ということで補題と証明を以下に書きます。

補題 $\require{cancel}$ 最小周期 $p$ の長さ $n$ の文字列 $S$ を考え、 $p \cancel{|} n$ であるとする。 $P = S[0, p)$ とする。この時、 $S P$ の最長borderは $P$ 。すなわち最小周期は $n$ 。

証明

$P$ は明らかに $S P$ のborderであるから、これ以上長いborderがないことを示せば良い。 $m = n \bmod p$ とおけば、正整数 $k$ を用いて、 $SP = P^{k} P[0, m) P$ である。

以下、3ケースに場合分けする。

a) $P[m-l, m) P$

$0 \lt l \leq m$ として、↑がborderであると仮定する。 $k \geq 1$ に注意すれば、これは

$PP[0, l) = P[m-l, m) P$

と同値である。この等式の両辺の最後の $l$ 文字に注目すると

$P[0, l) = P[p-l, p)$

から $p-l$ は周期。他方、両辺の $l$ 文字目から $p-1$ 文字目までに注目すると

$P[l, p) = P[0..p-l)$

より、 $l$ は周期。 $P$ の最小周期を $w$ とおいておく。当然、

$w \leq min(l, p-l)$

が成立する。 $\min(l, p-l) \leq \frac{p}{2}$ であることに気をつけると、そのような $l$ が存在するには、 $w \leq \frac{p}{2}$ が必要。今、明らかに $l + (p-l) \leq p + gcd(l, p-l)$ であるから、周期性補題から $gcd(l, p-l)$ も周期になる。

これを $g$ とおく。 $g$ も $\frac{p}{2}$ 以下であるから、 $g, w$ に対して同様に周期性補題を用いれば、 $g$ は $w$ の倍数である事がわかる。したがって、 $l, p-l, p$ も全て $w$ の倍数。これは、 $S$ の周期として $w$ が取れることを意味するから $p$ の最小性に反する。以上からこのようなborderが取れることはない。

b) $kp$ 未満の周期のうち、比較的短いもの

$SP$ が $kp$ 未満の周期 $w'$ があると仮定する。すなわち、borderとして

$P[l, p) P ... P P[0, m) P$

という形になっているものを考える。この時、 $S$ も同様に周期 $w'$ を持つことに気をつける。

この $w'$ と $p$ に対して $S$ に関する周期性補題を適用出来る場合を考える。これがケースb)である。すなわち

$w' + p \leq kp + m + gcd(w', p)$

が成立する時を考える。この時、 $p = gcd(w', p)$ が成立するから $w'$ は $p$ の倍数。

したがって $w'$ に対応するborderは

$P...PP[0, m)P$

のような形をしている。 borderの最後の $p$ 文字について注目すると、suffix側のborderは明らかに $P$ である。他方、prefix側は（ $P[0, m)$ の後に続いているわけなので） $P[m, p) P[0, m)$ である。これは $m, p-m$ の双方が $P$ の周期であることを表す。よって、ケースa)の議論と同様にして矛盾する。

c) $kp$ 未満の周期のうち、長いもの

ケースb)では周期性補題が利用できるほど周期が比較的短い場合には矛盾するということが言えた。残りは周期性補題の不等式が成立しない場合である。すなわち、

$w' + p \gt kp + m + gcd(w', p)$

であるケースを考える。 $w'$ は少なくとも、

$w' + p \gt kp + m + 1 \iff w' \gt kp + m + 1 - p$

より $kp+m+2-p$ 以上の長さを持つ。すなわち、 $w'$ に対応する $SP$ のborderは高々 $2p-2$ 程度の長さしか持たない。よって、borderは

$P[p-l,p)P[0,m)P$

のような形で表せる（ $l+m \leq p-2$ ）。 $k = 1$ の時、すなわち $SP = PP[0,m)P$ のように表せる場合は、borderの先頭 $l$ 文字および末尾 $l$ 文字に注目すると、 $l, p-l$ が $P$ の周期となりa), b)と同様に矛盾する。

$k \geq 2$ の時、prefix側のborderは $PP$ のprefixである。したがって、このborderの末尾p文字に注目すると、 $l+m, p-(l+m)$ が $P$ の周期であることが分かる。よって、これも同様に矛盾する。

以上で全てのケースを尽くせているから、 $S P$ の最長borderが $P$ であることが示された。

割と、こうやって場合分けをしないと、borderや周期を考えるまではいいけど、どのタイミングで $P[0,m)$ にぶつかるかが不透明すぎて頭が爆発すると思っている。ただ議論自体は全部同じように進むので、もしかしたら慎重に注目する場所と長さを選べば全部ひとまとめで考えられるのかなあ、いやそんなことない気がする