QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100
[-4]

# 6181. 重复函数问题

Statistics

给定一个由 n 个小写英文字母组成的字符串 S,其重复函数 fS(x) 定义如下:

  • 对于正整数 1infS(i) 的值是字符串 S 的一个最长子字符串 A,它可以将给定字符串 S 表示为 S=A#A#A#A,其中字符串 A 恰好出现 i 次,而其中的 # 可以是任意字符串(包括空串)。如果不存在满足要求的子字符串 A,则 fS(i) 为空串。

重复函数问题:对于给定的由 n 个小写英文字母组成的字符串 S,计算函数 fS(i) 的值,及其长度 |fS(i)|2in

输入格式

测试数据的第一行有一个由小写英文字母组成的字符串 S

输出格式

依次输出给定的字符串 Sn1 个子串 fS(i) 的长度 fS(i)2in

样例数据

样例输入

abaabacdabaaba

样例输出

6 3 3 1 1 1 1 0 0 0 0 0 0

子任务

测试数据中 10% 的数据满足 n300

测试数据中 30% 的数据满足 n3000

测试数据中 80% 的数据满足 n200000

测试数据中 100% 的数据满足 n1000000