UOJ Logo

NOI.AC

#82. 周期

统计

题目描述

老虎和蒜头是好朋友。

中秋节时,老虎收到了一个长度为 $ n $ 的由小写字母构成的串 $ S $,老虎想要和蒜头一起分享这份喜悦。蒜头当然和老虎的想法不同,虽然蒜头也认为这很有意思,但蒜头更关心的是,如果我们现在可以在 $ S $ 中修改一个字符,那么所有可能的周期长度是多少?

一个长度 $ 1 \le T < n $ 被称为字符串 $ S $ 的周期,当且仅当对任意 $ 1 \le i \le n - T $ ,都有 $ S_i = S_{i + T} $ 。

输入格式

共一行,一个长度为 $ n $ 的,只由小写字母构成的串 $ S $ 。

输出格式

输出共两行。在第一行你应当输出可能的周期长度的个数 $ m $。不妨假设 $ c = \lceil \frac{m}{10^5} \rceil $ ,而所有可能的周期长度升序排列后为 $ l_1, l_2, \ldots, l_m $ ,那么你应当输出 $ l_c, l_{2c}, \ldots, l_{\lfloor \frac{m}{c} \rfloor c} $ 。

样例数据

样例一

input

abaabac

output

3
3 5 6

数据范围及限制

对于 100% 的数据,$ 1 \le n \le 10^7 $ 。

对于 20% 的数据,$ n \le 100 $ 。

对于 40% 的数据,$ n \le 2000 $ 。

对于 60% 的数据,$ n \le 20000 $ 。

对于 80% 的数据,$ n \le 5 \times 10^5 $ 。

对于另外 10% 的数据,字符串中只含a,b两种字符。

时间限制: 1s

空间限制: 512MB