D - Destroy the Duplicated Poem
Editorial
Time Limit: 3 sec / Memory Limit: 256 MB
問題文
これは問題です。
これは Xmas Contest 2015 の問題です。
これは Xmas Contest 2015 の問題で文字列に関するものです。
これは Xmas Contest 2015 の問題で文字列に関するもので漸化式に基づいてたくさんの文字列を作ります。
これは Xmas Contest 2015 の問題で文字列に関するもので漸化式に基づいてたくさんの文字列を作ってそれらの周期を求めます。
これは Xmas Contest 2015 の問題で文字列に関するもので漸化式に基づいてたくさんの文字列を作ってそれらの周期を求めるけどあと 4 時間で AC しないといけません。
ぼくのすきな事はプログラミングコンテストです。 ぼくのゆめは Xmas Contest 2015 で全部の問題を解くことです。
これは Xmas Contest 2015 の問題です。
これは Xmas Contest 2015 の問題で文字列に関するものです。
これは Xmas Contest 2015 の問題で文字列に関するもので漸化式に基づいてたくさんの文字列を作ります。
これは Xmas Contest 2015 の問題で文字列に関するもので漸化式に基づいてたくさんの文字列を作ってそれらの周期を求めます。
これは Xmas Contest 2015 の問題で文字列に関するもので漸化式に基づいてたくさんの文字列を作ってそれらの周期を求めるけどあと 4 時間で AC しないといけません。
ぼくのすきな事はプログラミングコンテストです。 ぼくのゆめは Xmas Contest 2015 で全部の問題を解くことです。
2016 年になってもコンテストシステムにやさしくします。
(参考: https://twitter.com/kyuridenamida/status/678495822946811904)
要素の整数列 と、 文字の英小文字からなる文字列 を使って以下のように 個の文字列 を生成する。
- まず を空文字列とする。
- について、文字列 は文字列 の末尾に の 番目の文字を付け加えたものである。ただし、任意の について が成り立つ。
このようにして作られた文字列のうち の 個についてその周期を求めよ。
ただし文字列 の周期とは、 がある文字列 を無限回繰り返してできる文字列の接頭辞になっているような のうち最も短いものの長さである。たとえば abcabca
の周期は であり、abcabd
の周期は である。
入力
入力は以下の形式で標準入力から与えられる。
…
- 行目には整数 が与えられる。
- 行目には 要素の整数列 が空白区切りで与えられる。すべての に対し を満たす。
- 行目には 文字の文字列 が与えられる。 は英小文字のみからなる。
出力
行出力せよ。そのうち 行目には文字列 の周期を表す整数を つ出力せよ。
出力の末尾にも改行を入れること。
入力例 1Copy
Copy
8 0 1 2 3 4 5 6 5 abcabcad
出力例 1Copy
Copy
1 2 3 3 3 3 3 6
この例において各 とその周期は次のようになる。
- は
a
となり、その周期は である。 - は
ab
となり、その周期は である。 - は
abc
となり、その周期は である。 - は
abca
となり、その周期は である。 - は
abcab
となり、その周期は である。 - は
abcabc
となり、その周期は である。 - は
abcabca
となり、その周期は である。 - は
abcabd
となり、その周期は である。
入力例 2Copy
Copy
11 0 0 1 2 3 1 2 5 4 3 6 xmascontest
出力例 2Copy
Copy
1 1 2 2 3 2 2 4 3 3 3