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)

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

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

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

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

入力

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

N
A_1 A_2 … A_N
C
  • 1 行目には整数 N (1≦N≦5 \times 10^5) が与えられる。
  • 2 行目には N 要素の整数列 A が空白区切りで与えられる。すべての i (1≦i≦N) に対し 0≦A_i<i を満たす。
  • 3 行目には N 文字の文字列 C が与えられる。C は英小文字のみからなる。

出力

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

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

入力例 1

8
0 1 2 3 4 5 6 5
abcabcad

出力例 1

1
2
3
3
3
3
3
6

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

  • S_1 は a となり、その周期は 1 である。
  • S_2 は ab となり、その周期は 2 である。
  • S_3 は abc となり、その周期は 3 である。
  • S_4 は abca となり、その周期は 3 である。
  • S_5 は abcab となり、その周期は 3 である。
  • S_6 は abcabc となり、その周期は 3 である。
  • S_7 は abcabca となり、その周期は 3 である。
  • S_8 は abcabd となり、その周期は 6 である。

入力例 2

11
0 0 1 2 3 1 2 5 4 3 6
xmascontest

出力例 2

1
1
2
2
3
2
2
4
3
3
3