| Fişierul intrare/ieşire: | rocker.in, rocker.out | Sursă | ad-hoc |
| Autor | Catalin Francu | Adăugată de |  Catalin Francu •Catalin.Francu |
| Timp execuţie pe test | 1 sec | Limită de memorie | 12288 kbytes |
| Scorul tău | N/A | Dificultate |   1/5 |
Poti vedea testele pentru aceasta problema accesand atasamentele.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
- K ≤ N
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!
