Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-12-01 11:21:54.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:trie.in, trie.outSursăArhiva educationala
AutorArhiva EducationalaAdăugată deamadaeusLucian Boca amadaeus
Timp execuţie pe test0.4 secLimită de memorie30480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Trie

Se dau mai multe operatii care gestioneaza o lista de cuvinte, dupa cum urmeaza:

  • 0 w - adauga o aparitie a cuvantului w in lista
  • 1 w - sterge o aparitie a cuvantului w din lista
  • 2 w - tipareste numarul de aparitii ale cuvantului w in lista
  • 3 w - tipareste lungimea celui mai lung prefix comun al lui w cu oricare cuvant din lista

Date de intrare

Fisierul trie.in va contine mai multe linii, pe fiecare linie fiind descierea unei operatii, in formatul precizat mai sus.

Date de iesire

Fisierul trie.out va contine, pentru fiecare operatie de tip 2 si 3 din fisierul de intrare, raspunsul operatiei corespunzatoare (in ordinea ceruta in fisierul de intrare).

Restrictii

  • Pentru toate operatiile, cuvantul w este format din maxim 20 de caractere din intervalul 'a'..'z'
  • Numarul total de operatii nu va depasi 100 000
  • Operatiile de tip 1 w vor aparea numai daca w apare cel putin o data in lista de cuvinte

Exemplu

trie.intrie.out
0 lat
0 mare
0 lac
2 la
0 mare
1 lat
0 ma
0 lung
3 latitudine
0 mari
2 mare
0 lat
0 mic
3 latime
2 lac
3 mire
0
2
2
3
1
2

Solutie

O rezolvare brute-force a problemei mentine o lista a tuturor cuvintelor si rezolva operatiile de tip 0 w si 1 w in timp O(L), iar operatiile de tip 2 w si 3 w in timp O(N*L), unde N este numarul de cuvinte din lista, iar L lungimea cuvantului w. Memoria folosita este O(LungTot), unde LungTot este lungimea totala a cuvintelor din lista. O astfel de abordere ar trebui sa obtina in jur de 30 de puncte, iar o sursa demonstrativa se afla aici.

Solutia eficienta foloseste o structura de date arborescenta cunoscuta sub numele de Trie. Spre deosebire de alte structuri de date, intr-un trie cheile nu sunt identificate prin informatia dintr-un singur nod, ci prin drumul de la radacina trie-ului pana la un anumit nod. Astfel, fiecare nod are un numar de fii egal cu dimensiunea alfabetului folosit, iar fiecare muchie catre un fiu este etichetata cu litera corespunzatoare din alfabet. In figura de mai jos este ilustrat starea trie-ului din exemplu, dupa ce toate operatiile au fost executate. Pentru simpitate grafica, am eliminat din desen muchiile irelevante si am reprezentat ca informatie intr-un nod doar numarul de cuvinte care corespund cheii nodului respectiv:

Pornind de la radacina (careia i se asociaza sirul vid), fiecarui nod i se asociaza (va memora informatii suplimentare despre) cheia al carei nume se obtine prin concatenarea etichetelor tuturor muchiilor de pe drumul de la radacina trie-ului pana in nodul respectiv (in desen este evidentiat modul in care putem identifica nodul a carui cheie este "lat"). 

Acest mod de gestionare a listei de cuvinte permite executarea fiecarei operatii in timp O(L). Spatiul de memorie folosit depinde de structura cuvintelor din lista, mai exact de prefixele lor comune. Totusi, el nu va depasi O(LungTot * |Sigma|), unde Sigma este alfabetul folosit (in cazul de fata |Sigma|=26). Mai multe informatii despre structura de date vezi gasi aici. De asemenea, un tutorial util se afla pe TopCoder.

Aplicatii

Ideile din spatele aceastei structuri de date pot fi adaptate si integrate intr-o larga varietate de algoritmi. O aplicatie ingenioasa este solutia problemei xormax. O alta problema, care se foloseste de cautare binara pe niveluri intr-un trie este ratina. De asemenea, cu ajutorul unui trie pot fi rezolvate si:

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?