Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-11-30 18:23:21.
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.2 secLimită de memorie131072 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 lung
0 lume
2 lu
2 lume
3 lungime
0 lume
1 lung
3 luntre
0 lacat
2 lume
2 lung
3 lac
0
1
4
2
2
0
3

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 in Trie este ratina. De asemenea, cu ajutorul unui Trie pot fi rezolvate si urmatoarele:

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?