Fișierul intrare/ieșire rocker.in, rocker.out Sursă ad-hoc
Autor Cătălin Frâncu Adăugată de avatar Catalin.Francu Cătălin Frâncu Catalin.Francu
Timp de execuție pe test 1 sec Limită de memorie 12288 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Rocker

Un rocker își pregătește următorul concert astfel. Mai întâi, emite N vocale ‘E’ sau ‘I’. Apoi, consideră toate subsecvențele continue de K sunete ale șirului. Acestea sunt melodiile (NK + 1 la număr) pe care le va cânta.

Pentru a-și memora repertoriul, rockerul ordonează melodiile alfabetic. El dorește să afle, pentru fiecare două melodii consecutive, numărul de vocale identice la începutul melodiei. Misiunea voastră este să-l ajutați să calculeze acest vector.

Date de intrare

Fișierul de intrare rocker.in conține, pe prima linie, numerele N și K, iar pe a doua linie N caractere ‘E’ sau ‘I’, urmate de un caracter linie nouă.

Date de ieșire

În fișierul de ieșire rocker.out se vor scrie N – K numere, câte unul pe linie. Cel de-al i-lea număr indică lungimea celui mai lung prefix comun între melodiile i și i + 1, din repertoriul de melodii ordonate alfabetic.

Restricții

  • 1 ≤ N ≤ 1.000.000
  • 1 ≤ K ≤ 20
  • KN

Exemplu

rocker.in rocker.out
10 4
IEIEIEEEII
2
1
3
0
2
4

Explicație

Se formează 7 melodii: { IEIE, EIEI, IEIE, EIEE, IEEE, EEEI, EEII }. Repertoriul ordonat este { EEEI, EEII, EIEE, EIEI, IEEE, IEIE, IEIE }. Melodiile EEEI și EEII au primele două note comune, melodiile EEII și EIEE au prima notă comună, ..., melodiile IEIE și IEIE au toate cele patru note comune.

Notă

Există un mod naiv și un mod eficient de a calcula vectorul. Din păcate, ambele sunt dominate de timpul necesar pentru sortare. Străduiți-vă oricum să găsiți algoritmul eficient!

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 5 categorii