AT_xmascontest2015_d Destroy the Duplicated Poem

[problemUrl]: https://atcoder.jp/contests/xmascontest2015noon/tasks/xmascontest2015_d 这是一个问题。 这是 Xmas Contest 2015 的一道题目。 这是 Xmas Contest 2015 的一道关于字符串的问题。 这是 Xmas Contest 2015 的一道关于字符串的问题，需要基于递推式生成大量字符串。 这是 Xmas Contest 2015 的一道关于字符串的问题，需要基于递推式生成大量字符串，并求出它们的周期。 这是 Xmas Contest 2015 的一道关于字符串的问题，需要基于递推式生成大量字符串，并求出它们的周期，但还剩 4 小时必须 AC。 我喜欢的事情是参加编程竞赛。我的梦想是在 Xmas Contest 2015 中解出所有题目。即使到了 2016 年，我也会对竞赛系统保持友好。 （参考：） ------ 给定一个长度为 $N$ 的整数序列 $A$ 和一个长度为 $N$ 的仅包含小写英文字母的字符串 $C$，按照如下方式生成 $N+1$ 个字符串 $S_0,\ S_1,\ldots,\ S_N$。 - 首先，令 $S_0$ 为一个空字符串。 - 对于 $i=1,2,\ldots,N$，字符串 $S_i$ 是在字符串 $S_{A_i}$ 的末尾添加 $C$ 的第 $i$ 个字符得到的。并且对于任意 $i$，都有 $A_i < i$。 请对这样生成的 $N$ 个字符串 $S_1,\ S_2,\ldots,\ S_N$，分别求出它们的周期。 这里，字符串 $T$ 的周期定义为：$T$ 能够作为某个字符串 $X$ 无限重复拼接后所得字符串的前缀的所有 $X$ 中，最短的 $X$ 的长度。例如，`abcabca` 的周期为 $3$，`abcabd` 的周期为 $6$。

输入通过标准输入给出，格式如下： > $N$ > $A_1\ A_2\ \ldots\ A_N$ > $C$ - 第 $1$ 行包含一个整数 $N$，满足 $1 \leq N \leq 5 \times 10^5$。 - 第 $2$ 行包含 $N$ 个整数 $A$，以空格分隔。对于所有 $i\ (1 \leq i \leq N)$，都有 $0 \leq A_i < i$。 - 第 $3$ 行包含一个长度为 $N$ 的字符串 $C$，仅由小写英文字母组成。

输出共 $N$ 行。第 $i\ (1 \leq i \leq N)$ 行输出字符串 $S_i$ 的周期，输出一个整数。 输出末尾也要换行。

### 样例解释 1 在本例中，各 $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$。 由 ChatGPT 4.1 翻译