Fișierul intrare/ieșire | rocker.in, rocker.out | Sursă | ad-hoc |
---|---|---|---|
Autor | Cătălin Frâncu | Adăugată de | 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 |
Vezi soluțiile trimise | Statistici
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!