408675: GYM103261 B String Algorithm

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$$$.

The 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.

Print $$$n$$$ numbers, the $$$k$$$-th of them being $$$f(k)$$$.

7
kkekeee

21 2 1 0 0 0 0 

10
babaiskeke

45 2 0 0 0 0 0 0 0 0 

11
aaabaaabaaa

55 10 2 1 0 0 0 0 0 0 0