408675: GYM103261 B String Algorithm
Description
We give you a string $$$s$$$ of length $$$n$$$.
Let's fix some $$$k$$$ ($$$1 \le k \le n$$$). Create $$$m = \left\lfloor \frac{n}{k} \right\rfloor$$$ strings of length $$$k$$$, the $$$i$$$-th of them being a substring of $$$s$$$ starting with position $$$(i - 1)k + 1$$$: $$$p_{i} = s_{(i-1)k+1}s_{(i-1)k+2} \ldots s_{ik}$$$.
In other words, we cut the string $$$s$$$ into strings of length $$$k$$$ and discard leftovers. Let $$$f(k) = \left| \left\{ (i, j) \; | \; 1 \le i < j \le m, \; \mathit{dist}(p_{i}, p_{j}) \le 1 \right\} \right|$$$, where $$$\mathit{dist}$$$ denotes the Hamming distance. In human words, $$$f(k)$$$ is the number of pairs of strings $$$p$$$ that are different in at most $$$1$$$ position.
We ask you to devise an algorithm to compute $$$f(k)$$$ for all $$$k$$$ from $$$1$$$ to $$$n$$$.
InputThe first line contains one positive integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^{5}$$$) — the length of the string.
The second line contains the string $$$s$$$ of length $$$n$$$, consisting of lowercase English characters.
OutputPrint $$$n$$$ numbers, the $$$k$$$-th of them being $$$f(k)$$$.
ExamplesInput7 kkekeeeOutput
21 2 1 0 0 0 0Input
10 babaiskekeOutput
45 2 0 0 0 0 0 0 0 0Input
11 aaabaaabaaaOutput
55 10 2 1 0 0 0 0 0 0 0