The 'Winning' Gene

문제

After years of hosting games and watching Bessie get first place over and over, Farmer John has realized that this can't be accidental. Instead, he concludes that Bessie must have winning coded into her DNA so he sets out to find this "winning" gene.

He devises a process to identify possible candidates for this "winning" gene. He takes Bessie's genome, which is a string $SS$ of length $NN$ where $1\le N\le 30001\; \backslash leq\; N\; \backslash leq\; 3000$. He picks some pair $(K,L)(K,L)$ where $1\le L\le K\le N1\; \backslash leq\; L\; \backslash leq\; K\; \backslash leq\; N$ representing that the "winning" gene candidates will have length $LL$ and will be found within a larger $KK$ length substring. To identify the gene, he takes all $KK$ length substrings from $SS$ which we will call a $kk$-mer. For a given $kk$-mer, he takes all length $LL$ substrings, identifies the lexicographically minimal substring as a winning gene candidate (choosing the leftmost such substring if there is a tie), and then writes down the $00$-indexed position $p_{i}p\_i$ where that substring starts in $SS$ to a set $PP$.

Since he hasn't picked $KK$ and $LL$ yet, he wants to know how many candidates there will be for every pair of $(K,L)(K,L)$.

For each $vv$ in $1\dots N1\backslash dots\; N$, help him determine the number of $(K,L)(K,L)$ pairs with $\mathrm{\mid }P\mathrm{\mid }=v|P|=v$.

입력

$NN$ representing the length of the string. $SS$ representing the given string. All characters are guaranteed to be uppercase characters where $s_i\in A-Zs\_i\; \backslash in\; A-Z$ since bovine genetics are far more advanced than ours.

출력

For each $vv$ in $1\dots N1\backslash dots\; N$, output the number of $(K,L)(K,L)$ pairs with $\mathrm{\mid }P\mathrm{\mid }=v|P|=v$, with each number on a separate line.

8
AGTCAACG

11
10
5
4
2
2
1
1