QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100

# 6181. 重复函数问题

Statistics

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

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

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

输入格式

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

输出格式

依次输出给定的字符串 $S$ 的 $n − 1$ 个子串 $f_{S}(i)$ 的长度 $f_S(i)$,$2 \leq i \leq n$。

样例数据

样例输入

abaabacdabaaba

样例输出

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

子任务

测试数据中 $10\%$ 的数据满足 $n \leq 300$ 。

测试数据中 $30\%$ 的数据满足 $n \leq 3\,000$ 。

测试数据中 $80\%$ 的数据满足 $n \leq 200\,000$ 。

测试数据中 $100\%$ 的数据满足 $n \leq 1\,000\,000$ 。