Fişierul intrare/ieşire:rocker.in, rocker.outSursăad-hoc
AutorCatalin FrancuAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test1 secLimită de memorie12288 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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 (N - K + 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.inrocker.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 sa te autentifici pentru a trimite solutii. Click aici