Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2016-09-23 10:45:47.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:pmk.in, pmk.outSursăFinala ONIS 2016
AutorPaul Diac, Stefan CiobacaAdăugată dediac_paulPaul Diac diac_paul
Timp execuţie pe test0.05 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Pmk

Algoritmul KMP este folosit pentru a cauta eficient aparitiile un cuvant intr-un text. In prima faza el calculeaza functia prefix pentru cuvant. Functia prefix se calculeaza pentru orice prefix al cuvantului si are ca rezultat lungimea celui mai lung prefix care este si sufix al prefixului. Nu se ia in considerare ca prefix sau sufix sirul intreg (ci doar prefixe si sufixe proprii). Ca si conventie de implementare, rezultatul functiei prefix retinut pe pozitia i este functia pentru prefixul de la prima pozitia pana la pozitia i exclusiv, iar pentru prima pozitie se considera ca functia returneaza -1. Un exemplu de functie prefix poate fi urmatorul:

i indexat de la 0
0
123456789
sir[i]abbaabbbba
prefix[i]
-1
0
0
0
1
1
2
3
0
0

de exemplu prefix [6] = prefix("abbaab") = lungime("ab") = 2

Cunoscand rezultatul functiei prefix pentru un sir de lungime data, determinati cel mai mic sir lexicografic pentru care functia prefix are valorile respective. Sirul va fi format doar din litere mici ale alfabetului englez.

Date de intrare

Fişierul de intrare pmk.in contine o singura linie cu N: lungimea sirului urmat de N numere, valori valide pentru functia prefix a unui sir de lungime N.

Date de ieşire

În fişierul de ieşire pmk.out afisati un sir de caractere pentru care functia prefix are valorile specificate.

Restricţii

  • 1 ≤ N ≤ 10000
  • Va exista cel putin o solutie care contine doar litere mici ale alfabetului englez.

Exemplu

pmk.inpmk.out
10 -1 0 0 0 1 1 2 3 0 0
abbaabbbba
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?