第24回日本情報オリンピック　一次予選(第3回)

2024年11月18日
情報オリンピック日本委員会

解説

周期を構成する文字列の長さの候補 m   (1 ≦ m < N) ごとに，実際に S が自身の先頭 m 文字の繰り返しで得られるか判定すれば良い．

繰り返しになっているかの判定には，具体的に以下の方法が挙げられる．

• S の先頭 m 文字を N ÷ m 回繋げた文字列を実際に作り，S と一致するか判定する．
• i   (1 ≦ i ≦ N-m) 文字目について，i+m 文字目と一致するか判定する．

前者を実装したのが Python の解答例，後者を実装したのが C++ の解答例である．

なお，N で割り切れない m についても判定してしまった場合，後者は `abcabcab` のような文字列に対しても m=3 で周期的であると判定してしまうので注意すること．