\(O(N\sqrt{N})\)

\(N\) の約数は高々 \(O(\sqrt{N})\) 個なので、公式解説の方針は \(O(N\sqrt{N})\) です。

\(O(N)\)

「\(S\) が \(m\) 回の繰り返しになっている」と「\(m\) が \(N\) の約数であり、かつ \(S\) の \(1+m\) 文字目以降を取り出したものは、 \(S\) の接頭辞である」は同値です。

これは、 Z-algorithm を用いることで \(O(N)\) で解くことができます。