5129. 脚本

单点时限: 2.0 sec

内存限制: 512 MB

你最后还是决定饮茶放工,出去和队友吃火锅。不过在此之前火锅店老板已经对评论区进行了一次公关,你已经看不到多少中肯的评价了。同时,你也在评论区发现了一些端倪:因为老板请了水军,评论区的评论呈现出有一些有趣的特点。例如每一条评论的开头都离不开某几句话,因此你用一个小写字母 (a - z) 来表示一种评论。

你还发现评论都是用比较拙劣的自动化工具刷的,因为不仅只有几种评论,依次查看评论甚至发现了 循环节。根据你多年的脚本经验,这个脚本里面有一个长度为 $p$ 的评论列表,这个脚本会按顺序循环往复地发布这 $p$ 条评论。如果我们用字符串 $s = s_1 s_2\dots s_{|s|}$ 表示一系列连续的评论,那么我们说 $p$ 是 $s$ 的循环节,当且仅当:

  • $p \leq |s|$;
  • $\forall 1\le i\le |s|-p, s_i=s_{i+p}$.

你现在爬取了评论区所有的 $n$ 条评论,你很好奇老板刷评论的脚本里面的评论列表长什么样。不过,在老板操作以前可能已经存在一些评论了,你不知道老板是从哪一条评论开始用脚本刷评论的,因此你想知道每一个后缀的周期性。具体而言,对于 $i=1 \dots n$,假设最后的 $i$ 条评论是用脚本刷的,你需要求出脚本中所有可能循环节的大小(也即评论列表长度)之和 $a_i$ :
$$ a_i = \sum_{p \text{是} s_{n - i + 1\dots n} \text{的周期}} p .$$

输入格式

输入包含多组数据。第一行包含一个整数 $T$,代表数据组数。

每组数据的第一行包含一个正整数 $n$ ($1 \le n \le 10^6$),代表评论区评论的数量;第二行包含一个仅包含小写字母的字符串 $s$。

保证所有数据的 $n$ 总和不超过 $10^6$。

输出格式

对每组数据,在一行内输出 $n$ 个用空格分隔的整数 $a_1,\ a_2,\ \dots,\ a_n$。

样例

Input
3
5
ababa
14
nunhehhehahhhh
8
shanghai
Output
1 2 5 6 11 
1 3 6 10 5 11 7 15 24 10 21 12 13 14 
1 2 3 4 5 6 7 8 

提示

对于第一组数据而言:

  • 当 $i=1$ 时,评论列表只有可能为 $a$。
  • 当 $i=2$ 时,评论列表只有可能为 $ba$。
  • 当 $i=3$ 时,评论列表可能为 $aba$ 或者 $ab$。
  • 当 $i=4$ 时,评论列表可能为 $baba$ 或者 $ba$。
  • 当 $i=5$ 时,评论列表可能为 $ababa$, $abab$ 或者 $ab$。

83 人解决,110 人已尝试。

93 份提交通过,共有 348 份提交。

3.8 EMB 奖励。

创建: 9 月前.

修改: 9 月前.

最后提交: 5 月,2 周前.

来源: N/A

题目标签