== include(page="template/taskheader" task_id="trie") ==

Poveste şi cerinţă...

Se dau mai multe operatii care gestioneaza o lista de cuvinte, dupa cum urmeaza:
 
* $+w$ - adauga o aparitie a cuvantului $w$ in lista
* $-w$ - sterge o aparitie a cuvantului $w$ din lista
* $#w$ - tipareste numarul de aparitii ale cuvantului $w$ in lista
* $?w$ - tipareste lungimea celui mai lung prefix comun al lui $w$ cu oricare cuvant din lista

h2. Date de intrare

Fişierul de intrare $trie.in$ ...

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

h2. Date de ieşire

h2. Date de iesire

În fişierul de ieşire $trie.out$ ...

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

h2. Restricţii

h2. Restrictii

* $... ≤ ... ≤ ...$

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

h2. Exemplu
table(example). |_. trie.in |_. trie.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| +lung
+lume
#lu
#lume
?lungime
+lume
-lung
?luntre
+lacat
#lume
#lung
?lac
| 0
1
4
2
2
0
3

|

h3. Explicaţie

h3. Explicatie
 
O rezolvare brute-force a problemei mentine o lista a tuturor cuvintelor si rezolva operatiile de tip $+w$ si $-w$ in timp $O(L)$, iar operatiile de tip $#w$ si $?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':http://en.wikipedia.org/wiki/Trie. De asemenea, un tutorial util se afla pe 'TopCoder':http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=usingTries.

...

== include(page="template/taskfooter" task_id="trie") ==