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 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. Aceasta permite executarea tuturor operatiilor in timp O(L). Spatiul de memorie folosit depinde de structura cuvintelor din lista, mai exact de prefixele lor comune. Totusi, ea 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 urmatoarele:

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

Cum se trimit solutii?