C - Min period

キーワード

約数

解説

愚直に $T$ の先頭から $i$ 文字目 $(1 \leq i \leq |T|)$ までを $S$ の候補とし，それより後がその文字列の繰り返しになっているかを確認する方法では，最悪ケースで計算量が $O(|T|^{2})$ となり実行時間制限を超過してしまいます。

そこで，$T$ の生成手順に注目すると，$S$ の候補は絞られることが分かります。
$T$ は空文字列に $S$ を $1$ 回以上連結させて生成されるので，$|T|$ は $|S|$ の倍数になっています。
つまり，$|S|$ は $|T|$ の約数になっているので，先頭からの長さが $|T|$ の約数となる文字列のみを調べれば良いです。

$T$ の先頭から長さ $L$ の文字列 $T'$ が $S$ であるかを判定するには，それより後の文字列が $T'$ の繰り返しになっているかを調べます。
$L = |T|$ の場合は $T' = T$ であるので，$T'$ は $S$ です。
$T' \neq T$ の場合は，$L+1 \leq i \leq |T|$ を満たすすべての $i$ について $T[i]=T[{(i-1)\%L+1}]$ が成立するならば $T'$ は $S$ であり，そうでなければ $T'$ は $S$ ではありません。
$L$ が小さいものから調べていき，最初に $S$ として適切なものが答えになります。

最後に計算量についてです。
$|T|$ の約数列挙は， $1$ から順に試し割りをする素朴な実装で $O(|T|)$ です。
そして $S$ の候補は $|T|$ の約数の個数 $O(\sqrt{|T|})$ だけあり，$1$ つの候補を調べるのに $O(|T|)$ かかるので，最終的な計算量は $O(|T|\sqrt{|T|})$ と見積もれます。
実際の約数の個数は， $|T| \leq 4 \times 10^{5}$ では高々 $192$ 個( $332640$ と $360360$ と $393120$ )であり，すべて試して間に合います。
「$|T|$ の約数の個数は $|T| \leq 4 \times 10^{5}$ では高々 $192$ 個」という正確な数値は知っていなくても，$N$ の約数の個数は( $N$ が大きいほど) $N$ に比べて非常に小さいことを知っていれば，ざっくりと計算量を見積もって，間に合うことが予測できます。

なお，この問題は別のアルゴリズムにより $O(|T|)$ で解くこともできます。(ヒント(逆から読め)：nasiekeamonuohpmk)

実装例(C++)