P14729 [ICPC 2022 Seoul R] Longest Substring

对于一个长度为 $n \geq 1$ 的字符串 $S$ 和一个正整数 $k$ ($1 \leq k \leq n$)，$S$ 的一个非空子串被称为 **$k$-子串**，如果该子串在 $S$ 中**恰好**出现 $k$ 次。这 $k$ 次出现不一定是互不重叠的，即可能重叠。例如，如果 $S = \text{ababa}$，则对于每个 $k = 1, ..., 5$，$S$ 的 $k$-子串如下： - $S$ 中有四个 1-子串：$\text{abab}$、$\text{ababa}$、$\text{bab}$ 和 $\text{baba}$，因为这些子串在 $S$ 中恰好出现一次。注意，$\text{aba}$ 不是 1-子串，因为它出现了两次。 - $S$ 中有四个 2-子串：$\text{ab}$、$\text{aba}$、$\text{b}$ 和 $\text{ba}$。子串 $\text{ab}$ 恰好不重叠地出现了两次。子串 $\text{aba}$ 的两次出现在字符 $\text{a}$ 处重叠，但它的出现次数不超过两次。 - $S$ 中只有一个 3-子串：$\text{a}$。 - $S$ 中不存在 4-子串或 5-子串。 对于 $S$ 的一个 $k$-子串 $T$，令 $d(T)$ 表示 $T$ 在 $S$ 中互不重叠出现的最大次数。例如，一个 2-子串 $T = \text{ab}$ 可以不重叠地选择两次，即互不重叠出现的最大次数为 $2$，所以 $d(T) = 2$。对于一个 2-子串 $T = \text{aba}$，它无法不重叠地选择两次，所以 $d(T) = 1$。对于一个 3-子串 $T = \text{a}$，它可以不重叠地选择三次，这是最大值，所以 $d(T) = 3$。 令 $f(k)$ 表示对于 $1 \leq k \leq n$，在所有 $k$-子串 $T$ 中，具有最大 $d(T)$ 的那些子串中最长的长度。例如，对于 $S = \text{ababa}$ 和 $k = 1, ..., 5$，$f(k)$ 如下： - 当 $k = 1$ 时，所有 1-子串 $T$ 只能不重叠地选择一次，因此 $d(T) = 1$。所以，在所有 $d(T) = 1$ 的 1-子串中，最长的是 $\text{ababa}$，因此 $f(1) = 5$。 - 当 $k = 2$ 时，对于 $T = \text{aba}$ 有 $d(T) = 1$，但对于其他 2-子串 $T = \text{ab}$、$\text{b}$、$\text{ba}$ 有 $d(T) = 2$。在 $d(T) = 2$ 的 2-子串中，$\text{ab}$ 和 $\text{ba}$ 是最长的，因此 $f(2) = 2$。 - 当 $k = 3$ 时，因为只有一个 3-子串 $\text{a}$，所以 $f(3) = 1$。 - 当 $k = 4, 5$ 时，不存在 $k$-子串，因此 $f(4) = 0$，$f(5) = 0$。 给定一个长度为 $n$ 的字符串 $S$，请编写一个程序，输出 $f(k)$ 从 $k = 1$ 到 $k = n$ 的 $n$ 个值。对于上面的例子，输出应为 $5\ 2\ 1\ 0\ 0$。

你的程序需要从标准输入读取数据。输入的第一行包含一个由 $n$ ($1 \leq n \leq 50,000$) 个小写字母组成的字符串 $S$。

你的程序需要向标准输出写入数据。输出恰好一行。该行应包含恰好 $n$ 个非负整数，用空格分隔，表示按顺序从 $k = 1$ 到 $k = n$ 的 $f(k)$ 值，即 $f(1)\ f(2)\ ...\ f(n)$。注意，如果对于某个 $k$ 不存在 $k$-子串，则 $f(k)$ 应为 $0$。

翻译由 DeepSeek V3 完成