Fişierul intrare/ieşire:	trie.in, trie.out	Sursă	ad-hoc
Autor	Din Folclor	Adăugată de	Catalin Francu •Catalin.Francu
Timp execuţie pe test	0.2 sec	Limită de memorie	6144 kbytes
Scorul tău	N/A	Dificultate	4/5

Poti vedea testele pentru aceasta problema accesand atasamentele.

Vezi solutiile trimise

Trie (clasele 11 și 12)

Notă: Această problemă este o clonă a problemei Trie de la Infoarena. Diferenţele sunt marcate cu bold.

Se dau mai multe operaţii care gestionează o listă de cuvinte, după cum urmează:

• 0 w - adaugă o apariţie a cuvântului w în listă
• 1 w - şterge o apariţie a cuvântului w din listă
• 2 w - tipăreşte numărul de apariţii ale cuvântului w în listă
• 3 w - tipăreşte lungimea celui mai lung prefix comun al lui w cu oricare cuvânt din listă

Date de intrare

Fişierul de intrare trie.in va conţine mai multe linii, pe fiecare linie fiind descrierea unei operaţii, în formatul precizat mai sus.

Date de ieşire

Fişierul de ieşire trie.out va conţine, pentru fiecare operaţie de tip 2 şi 3 din fişierul de intrare, răspunsul operaţiei corespunzătoare (în ordinea cerută în fişierul de intrare).

Restricţii

• Pentru toate operaţiile, cuvântul w este format din maxim 20 de caractere din intervalul 'a'..'z'
• Numărul total de operaţii nu va depasi 100.000
• Operaţiile de tip 1 w vor apărea numai dacă w apare cel puţin o dată în lista de cuvinte
• Numărul de şiruri distincte din listă nu va depăşi în niciun moment 40.000.
• Am redus limita de memorie la 6 MB pentru a impune compactarea arborelui trie.
• Veţi avea nevoie de puţină inspiraţie pentru a dimensiona corect vectorii. Vestea bună este că porţiunile supradimensionate pe care nu le folosiţi nu contează şi nu cauzează depăşirea limitelor.

Exemplu