h2. 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':http://infoarena.ro/job_detail/226155?action=view-source.

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 suma lungimilor cuvintelor din lista. O astfel de abordere ar trebui sa obtina in jur de 30 de puncte, iar o sursa demonstrativa se afla 'aici':http://infoarena.ro/job_detail/226155?action=view-source.

Solutia eficienta foloseste o structura de date arborescenta cunoscuta sub numele de *Trie*. Spre deosebire de alte structuri de date, intr-un trie cheile nu sunt identificate prin informatia dintr-un singur nod, ci prin drumul de la radacina trie-ului pana la un anumit nod. Astfel, fiecare nod are un numar de fii egal cu dimensiunea alfabetului folosit, iar fiecare muchie catre un fiu este etichetata cu litera corespunzatoare din alfabet. In figura de mai jos este ilustrat starea trie-ului din exemplu, dupa ce toate operatiile au fost executate. Pentru simplitate grafica, am eliminat din desen muchiile irelevante si am reprezentat ca informatie intr-un nod doar numarul de cuvinte care corespund cheii nodului respectiv:

Solutia eficienta foloseste o structura de date arborescenta cunoscuta sub numele de $Trie$. Spre deosebire de alte structuri de date, intr-un trie cheile nu sunt identificate prin informatia dintr-un singur nod, ci prin drumul de la radacina trie-ului pana la un anumit nod. Astfel, fiecare nod are un numar de fii egal cu dimensiunea alfabetului folosit, iar fiecare muchie catre un fiu este etichetata cu litera corespunzatoare din alfabet. In figura de mai jos este ilustrat starea trie-ului din exemplu, dupa ce toate operatiile au fost executate. Pentru simplitate grafica, am eliminat din desen muchiile irelevante si am reprezentat ca informatie intr-un nod doar numarul de cuvinte care corespund cheii nodului respectiv:

p=. !problema/trie?trie.png!