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

* $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

h2. Date de intrare

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

* Numarul total de operatii nu va depasi $100 000$
* Operatiile de tip $0 w$ vor aparea numai daca $w$ apare cel putin o data in lista de cuvinte

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

| +lung
+lume
#lu
#lume
?lungime
+lume
-lung
?luntre
+lacat
#lume
#lung
?lac

| 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

3
|

h3. Explicatie

h2. Solutie

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.

h2. 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':http://infoarena.ro/problema/xormax. O alta problema, care se foloseste de cautare binara pe niveluri in Trie este 'ratina':http://infoarena.ro/problema/ratina. De asemenea, cu ajutorul unui Trie pot fi rezolvate si urmatoarele:
 
* 'sub':http://infoarena.ro/problema/sub (infoarena)
* 'dictree':http://infoarena.ro/problema/dictree (infoarena)
* 'Password Search':http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=11&page=show_problem&problem=843 (uva)
* _Type printer_ (IOI 2008)
* _Toponyms_ (BOI 2007)

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