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$). Se poate observa ca memoria totala folosita in cazul cel mai defavorabil pentru restrictiile din enuntul problemei ar putea depasi $50 MB$. Cu toate acestea, testele folosite pentru evaluare au fost construite in asa fel incat sa garanteze (datorita omogenitatii operatiilor din fisierele de intrare) ca in niciun moment dimensiunea trie-ului nu va fi mai mare de $16 MB$. Aceasta decizie a fost luata in vederea incurajarii unei folosiri eficiente a memoriei (in urma stergerii unor ramuri complete din trie, toate locatiile respective vor fi eliberate).

Mai multe informatii despre structura de date veti 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. Pentru detalii de implementare puteti consulta 'sursa demonstrativa':http://infoarena.ro/job_detail/226157?action=view-source.

Mai multe informatii despre structura de date veti 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. Pentru detalii de implementare puteti consulta 'sursa demonstrativa':http://infoarena.ro/job_detail/248138?action=view-source.

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 intr-un trie este 'ratina':http://infoarena.ro/problema/ratina. De asemenea, cu ajutorul unui trie pot fi rezolvate si:

* '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)

* 'sub':problema/sub
* 'dictree':problema/dictree
* 'xormax':problema/xormax
* 'ratina':problema/ratina
* 'Password Search':http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=11&page=show_problem&problem=843
* "Type printer":http://www.ioi2008.org/images/stories/ioi2008/tasks/day1/printer.pdf, _IOI 2008_
* "Toponyms":http://boi2007.edu.md/index.php?option=com_content&task=view&id=25&Itemid=51, _BOI 2007_

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

3452