附加文件

题目描述

给定长为 $n$ 的字符串 $s$，定义 $f(k)$ 为以下问题的答案：

• 最多能从 $s$ 中选出多少个长度为 $k$ 的、互不相交的、相同的子串？

求 $f(1),f(2),\cdots,f(n)$。

输入格式

一行一个字符串 $s$，$s$ 只包含小写英文字母。

输出格式

输出一行 $n$ 个正整数表示 $f(1),\cdots,f(n)$。

样例 $1$ 输入

ababababa

样例 $1$ 输出

5 4 2 2 1 1 1 1 1

样例 $1$ 解释

对于 $k=1$，选择子串 a

对于 $k=2$，选择子串 ab

对于 $k=3$，选择子串 aba

样例 $2$ 输入

abcbabcba

样例 $2$ 输出

4 2 2 2 1 1 1 1 1

样例 $3 \sim 6$

见下发文件，这些样例依次满足子任务 $2,3,4,5$ 的约束。

测试点约束

对于所有数据，$1\le |s|\le 2\times 10^5$，$s$ 只包含小写英文字母。