'우승' 유전자

Farmer John은 여러 해 동안 게임을 열면서 Bessie가 몇 번이고 1등을 차지하는 것을 지켜봤다. 이것이 우연일 리 없다고 판단한 그는 Bessie의 DNA에 "우승" 유전자가 들어 있다고 결론 내리고, 그 유전자를 찾아 나섰다.

그는 이 유전자의 후보를 찾는 절차를 고안했다. Bessie의 유전체는 길이 $N$인 문자열 $S$이며, $1 \leq N \leq 3000$이다. 그는 $(K,L)$ 쌍을 고른다. 여기서 $1 \leq L \leq K \leq N$이다. 유전자 후보의 길이는 $L$이고, 길이 $K$인 부분 문자열 안에 놓인다.

그는 $S$에서 길이 $K$인 부분 문자열을 모두 뽑는데, 이를 $k$-mer라고 부른다. 각 $k$-mer에서 길이 $L$인 부분 문자열을 모두 구하고, 사전순으로 가장 앞선 것을 우승 유전자 후보로 고른다. 여럿이 같으면 가장 왼쪽의 것을 고른다. 그리고 그 부분 문자열이 $S$에서 시작하는 0부터 세는 위치 $p_i$를 집합 $P$에 적는다.

아직 $K$와 $L$을 정하지 않은 그는 각 $(K,L)$ 쌍마다 후보가 몇 개 나오는지 알고 싶어 한다.

첫 줄에 문자열의 길이 $N$이 주어진다. 둘째 줄에 문자열 $S$가 주어진다. $S$의 모든 문자는 대문자 알파벳이며, $s_i \in A-Z$이다.

$1$부터 $N$까지의 각 $v$에 대해, $|P|=v$인 $(K,L)$ 쌍의 개수를 한 줄에 하나씩 출력한다.