Diferente pentru problema/pmk intre reviziile #19 si #36

Diferente intre titluri:

pmk
G. pmk

Diferente intre continut:

== include(page="template/taskheader" task_id="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 funtia returneaza -1. Un exemplu de functie prefix poate fi urmatorul:
Algoritmul KMP este folosit pentru a cauta eficient aparitiile unui cuvant intr-un text.
In prima faza el calculeaza functia prefix pentru orice prefix al cuvantului.
Pentru un sir functia are ca rezultat lungimea celui mai lung prefix propriu care este si sufix (propriu) al sirului. Un prefix propriu al unui sir e un prefix diferit de sir (sirul intreg nu e prefix propriu).
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 pentru valorile functiei prefix este urmatorul:
| **i** indexat de la 0
| **i** (indexat de la 0)
| 0
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| **sir[i]** |{background:lightgray}. **a** |{background:lightgray}. **b** |{background:lightgray}. b |{background:lightgray}. a |{background:lightgray}. **a** |{background:lightgray}. **b** | b | b | b | a |
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.
Cunoscand rezultatul functiei prefix pentru un sir de lungime data, determinati primul sir in ordine lexicografica pentru care functia prefix are valorile respective. Sirul va fi format doar din litere mici ale alfabetului englez.
h2. Date de intrare
Fişierul de intrare $pmk.in$ contime pe prima linie numarul de teste **T**.
Urmatoarele **T** linii contin numarul **N**, lungimea sirului urmat de **N** numere ce reprezinta valori valide pentru functia prefix a unui sir de lungime **N**.
Fişierul de intrare $pmk.in$ contine o singura linie cu numarul **N**, lungimea sirului urmat de **N** numere, valori valide pentru functia prefix ale unui sir de lungime **N**.
h2. Date de ieşire
În fişierul de ieşire $pmk.out$ afisati **T** siruri de caractere pe cate o linie, raspunsurile pentru fiecare test in ordine.
În fişierul de ieşire $pmk.out$ afisati un sir de caractere pentru care functia prefix are valorile specificate.
h2. Restricţii
* **T** ≤ 20
* 1 ≤ **N** ≤ 10000
* Pentru fiecare test va exista cel putin o solutie care contine doar litere mici ale alfabetului englez.
* Va exista cel putin o solutie care contine doar litere mici ale alfabetului englez.
h2. Exemplu
table(example). |_. pmk.in |_. pmk.out |
| 1
10 -1 0 0 0 1 1 2 3 0 0
| 10 -1 0 0 0 1 1 2 3 0 0
| abbaabbbba
|

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.