给定一个由 n 个小写英文字母组成的字符串 S,其重复函数 fS(x) 定义如下:
- 对于正整数 1≤i≤n, fS(i) 的值是字符串 S 的一个最长子字符串 A,它可以将给定字符串 S 表示为 S=A#A#⋯A#A,其中字符串 A 恰好出现 i 次,而其中的 # 可以是任意字符串(包括空串)。如果不存在满足要求的子字符串 A,则 fS(i) 为空串。
重复函数问题:对于给定的由 n 个小写英文字母组成的字符串 S,计算函数 fS(i) 的值,及其长度 |fS(i)|,2≤i≤n。
输入格式
测试数据的第一行有一个由小写英文字母组成的字符串 S。
输出格式
依次输出给定的字符串 S 的 n−1 个子串 fS(i) 的长度 fS(i),2≤i≤n。
样例数据
样例输入
abaabacdabaaba
样例输出
6 3 3 1 1 1 1 0 0 0 0 0 0
子任务
测试数据中 10% 的数据满足 n≤300 。
测试数据中 30% 的数据满足 n≤3000 。
测试数据中 80% 的数据满足 n≤200000 。
测试数据中 100% 的数据满足 n≤1000000 。