Fişierul intrare/ieşire:	trie.in, trie.out	Sursă	Arhiva educationala
Autor	Arhiva Educationala	Adăugată de	Lucian Boca •amadaeus
Timp execuţie pe test	0.2 sec	Limită de memorie	131072 kbytes
Scorul tău	N/A	Dificultate	N/A

Poti vedea testele pentru aceasta problema accesand atasamentele.

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

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 suma lungimilor 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 simplitate 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 veti gasi aici. De asemenea, un tutorial util se afla pe TopCoder. Pentru detalii de implementare puteti consulta sursa demonstrativa.

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:

• sub (infoarena)
• dictree (infoarena)
• Password Search (uva)
• Type printer (IOI 2008)
• Toponyms (BOI 2007)

Cum se trimit solutii?