周期性補題の利用 : Blocks(CC:UWCOI20F)

Blocks を解くときに使った、新規性のある話題なのでメモ。

長さ \(N\) の文字列 \(S\) があります。

「単位文字列が何度繰り返されているか」を (文字列の長さ) / (文字列の長さの約数である、文字列の周期) の 最大値で定義します。

例えば、

"hellohellohello" なら 3 (周期長:5)

"heyhello" なら 1 (周期長:8)

"aabaabaabaab" なら 4 (周期長:3)

"zzzzz" なら 5 (周期長:1) 

となります。

文字列 \(S=S_0S_1S_2...S_{N-1}\) に対する以下のクエリを高々 \(Q\) 回使って、「単位文字列が何度繰り返されているか」を求めてください。

・? x \(S_0\) と \(S_x\) から1文字づつ進めて比較を行うことを、両者が一致しなくなるか \(x=N\) に達するまで繰り返す。このとき、両者が一致した回数を返す。

例えば、

"aabaabaab" に対して

? 1 \(= 1\)

a[a]baabaab 

*[a]abaabaab

? 2 \(= 0\)

aabaabaab 

**aabaabaab

? 3 \(= 6\)

aab[aabaab] 

***[aabaab]aab

となります。

\(1 \le N \le 10^6\)

\(Q = 9\)

( (小課題1) \(Q=240\) , (小課題2) \(Q=20\) )

結局、求めるべきものは文字列の長さの約数である最短の周期です。

まず、文字列の周期と聞いて思い浮かぶのは  KMPを利用したこれ。  しかし、今回はこれではうまくいきそうにありません。(何せ元の \(S\) に関する情報は得られないので…)

ここで、 周期性補題 - Qiita という話題を見つけました。証明はリンク先にぶん投げて、以下の結論(周期性補題)だけを取り出して活用します。

文字列 \(S\) が周期 \(p,q\)を持つとする。

\(p+q \le |S| + gcd(p,q)\) ならば、 \(gcd(p,q)\) も文字列 \(S\) の周期。

ここで、今回考えているのは、\(|S|\) の約数である周期 \(p,q\) です。この条件のもとでは、以下が全面的に成立します。

文字列 \(S\) が周期 \(p,q\)を持つならば、 \(gcd(p,q)\) も文字列 \(S\) の周期。

(証明)

(i) \(p,q\) の少なくとも一方が \(|S|\) の場合、考えている \(p,q\) が \(|S|\) の約数であることから \(gcd(p,|S|) = p\) または \(gcd(|S|,q) = q\)が成立する。

(ii) \(p,q\) がともに \(|S|\) 未満の場合、 \(p,q\) は \(|S|\) の約数なので、ともに高々 \(\frac{|S|}{2}\) である。 よって、 \(p+q \le |S|\) が成立するので周期性補題より成立。

元の問題に戻ります。\(x\) を \(|S|\) の約数とすると、「? x \(= N-x\)」⇔「文字列 \(S\) は周期 \(x\) をもつ」が成立します。

ここまで来れば、あとは具体例を用いて理解するのが早いでしょう。

\(N=720=2^4 \times 3^2 \times 5\) とします。

ここで、解が \(gcd\) を使って求められることを念頭に置くと、素因数の数をひとつづつ当てたくなります。

例えば、解に含まれる \(2\) の素因数を当てたい場合、 \(\frac{720}{2^k}\) がどこまで周期となるかを二分探索してやればよいです。これを全ての素因数について順番に行うと、 \(Q=9\) に収まります。