8791: [CSES Problem Set] Bit Substrings
[Creator : ]
Description
You are given a bit string of length n. Your task is to calculate for each k between 0…n the number of non-empty substrings that contain exactly k ones.
For example, if the string is 101, there are:
For example, if the string is 101, there are:
-
1 substring that contains 0 ones: 0
-
4 substrings that contain 1 one: 01, 1, 1, 10
-
1 substring that contains 2 ones: 101
- 0 substrings that contain 3 ones
Input
The only input line contains a binary string of length n.
Output
Print n+1 values as specified above.
Constraints
$1 \leq n \leq 2 \times 10^5$
Sample 1 Input
101
Sample 1 Output
1 4 1 0