문자열 알고리즘

길이 $n$인 문자열 $s$가 주어진다.

$k$ ($1 \le k \le n$)를 고정하자. $m = \lfloor n/k \rfloor$개의 길이 $k$ 문자열을 만들고, $i$번째 문자열은 $s$에서 위치 $(i-1)k+1$부터 시작하는 부분 문자열로 정의한다: $p_i = s_{(i-1)k+1} s_{(i-1)k+2} \dots s_{ik}$.

다시 말해, 문자열 $s$를 길이 $k$의 문자열들로 자르고 남는 부분은 버린다. $f(k) = |\{(i, j) \mid 1 \le i < j \le m, \operatorname{dist}(p_i, p_j) \le 1\}|$로 정의한다. 여기서 $\operatorname{dist}$는 해밍 거리이다. 즉, $f(k)$는 서로 다른 위치가 최대 1개인 문자열 쌍 $p$의 개수이다.

$k = 1$부터 $n$까지 모든 $k$에 대해 $f(k)$를 계산하는 알고리즘을 설계하라.

첫째 줄에 양의 정수 $n$이 주어진다 ($1 \le n \le 2 \cdot 10^5$). $n$은 문자열의 길이이다.

둘째 줄에 길이 $n$인 문자열 $s$가 주어진다. $s$는 영소문자로만 이루어져 있다.

$n$개의 수를 출력한다. $k$번째 수는 $f(k)$이다.