P10420 [Lanqiao Cup 2023 National A] Substrings

Given a string $S$ consisting only of lowercase English letters, ask how many distinct strings appear in $S$ exactly $1 \sim |S|$ times. If two strings differ in length or in the character at any position, we consider them different.

Input one line containing a string $S$, consisting of lowercase English letters.

Output $|S|$ lines, each containing an integer. The integer on line $i$ denotes the number of strings that appear exactly $i$ times in $S$.

**[Sample Explanation 1]** `a`, `ab`, `bb`, `abb` appear once, and `b` appears twice. **[Test Case Size and Conventions]** For $20\%$ of the test cases, $|S| \le 300$. For $40\%$ of the test cases, $|S| \le 5000$. For all test cases, $1 \le |S| \le 10^6$. Translated by ChatGPT 5