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 で全部の問題を解くことです。

2016 年になってもコンテストシステムにやさしくします。

(参考: https://twitter.com/kyuridenamida/status/678495822946811904)


NN 要素の整数列 AA と、NN 文字の英小文字からなる文字列 CC を使って以下のように N+1N+1 個の文字列 S0,S1,...,SNS_0, S_1, ..., S_N を生成する。

  • まず S0S_0 を空文字列とする。
  • i=1,2,...,Ni = 1, 2, ..., N について、文字列 SiS_i は文字列 SAiS_{A_i} の末尾に CCii 番目の文字を付け加えたものである。ただし、任意の ii について Ai<iA_i < i が成り立つ。

このようにして作られた文字列のうち S1,S2,...,SNS_1, S_2, ..., S_NNN 個についてその周期を求めよ。

ただし文字列 TT の周期とは、TT がある文字列 XX を無限回繰り返してできる文字列の接頭辞になっているような XX のうち最も短いものの長さである。たとえば abcabca の周期は 33 であり、abcabd の周期は 66 である。


入力

入力は以下の形式で標準入力から与えられる。

NN
A1A_1 A2A_2ANA_N
CC
  • 11 行目には整数 N(1N5×105)N (1≦N≦5 \times 10^5) が与えられる。
  • 22 行目には NN 要素の整数列 AA が空白区切りで与えられる。すべての i(1iN)i (1≦i≦N) に対し 0Ai<i0≦A_i<i を満たす。
  • 33 行目には NN 文字の文字列 CC が与えられる。CC は英小文字のみからなる。

出力

NN 行出力せよ。そのうち i(1iN)i (1≦i≦N) 行目には文字列 SiS_i の周期を表す整数を 11 つ出力せよ。

出力の末尾にも改行を入れること。


入力例 1Copy

Copy
8
0 1 2 3 4 5 6 5
abcabcad

出力例 1Copy

Copy
1
2
3
3
3
3
3
6

この例において各 SiS_i とその周期は次のようになる。

  • S1S_1a となり、その周期は 11 である。
  • S2S_2ab となり、その周期は 22 である。
  • S3S_3abc となり、その周期は 33 である。
  • S4S_4abca となり、その周期は 33 である。
  • S5S_5abcab となり、その周期は 33 である。
  • S6S_6abcabc となり、その周期は 33 である。
  • S7S_7abcabca となり、その周期は 33 である。
  • S8S_8abcabd となり、その周期は 66 である。

入力例 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


2025-04-04 (Fri)
21:33:27 +00:00