← 返回题目列表

AtCoder · xmascontest2015_d

D. 销毁重复的诗

中文机器翻译题面 查看原题

問題文

这是一个问题。
这是 2015 年圣诞节竞赛的问题。
这是2015年圣诞节竞赛中涉及字符串的问题。
这是 2015 年圣诞节竞赛中的一个问题,涉及字符串并根据递归公式创建许多字符串。
这是 2015 年圣诞节竞赛中的一个问题,涉及字符串,涉及根据递归公式创建许多字符串并查找它们的周期。
这是 2015 年圣诞竞赛的一道题,是关于字符串的。我正在根据递归公式创建很多字符串并找到它们的周期,但我必须在 4 小时内完成 AC。

我最喜欢的是编程竞赛。 我的梦想是解决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