18489번 - String Algorithm 다국어

We give you a string s of length n.

Let’s fix some k (1 ≤ k ≤ n). Create m = ⌊n/k⌋ 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+1s_(i−1)k+2 . . . s_ik.

In other words, we cut the string s into strings of length k and discard leftovers. Let f(k) = |{(i, j) | 1 ≤ i < j ≤ m, dist(p_i, p_j) ≤ 1}|, where 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 ≤ n ≤ 2 · 10⁵) — 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).