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\) に収まります。
