408675: GYM103261 B String Algorithm

Memory Limit:0 MB Time Limit:15 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

B. String Algorithmtime limit per test15 secondsmemory limit per test512 mebibytesinputstandard inputoutputstandard output

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

Input

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.

Output

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

ExamplesInput
7
kkekeee
Output
21 2 1 0 0 0 0 
Input
10
babaiskeke
Output
45 2 0 0 0 0 0 0 0 0 
Input
11
aaabaaabaaa
Output
55 10 2 1 0 0 0 0 0 0 0 

加入题单

上一题 下一题 算法标签: