Trie per le ricerche sui prefissi

Un trie è un albero che memorizza le parole condividendo i prefissi comuni. Rende velocissime le query sui prefissi. 🌳

Un set risponde alle ricerche di parole intere, ma i trie consentono anche query sui prefissi, ad esempio per verificare se una parola inizia con pre.

Ogni nodo rappresenta una posizione in una parola e ogni arco è etichettato con un carattere lungo il percorso dalla radice.

In Python, il nodo più semplice è un dict che associa un carattere al nodo figlio corrispondente. È una soluzione chiara e flessibile.

Per inserire una parola, percorra i caratteri uno alla volta e crei un figlio ogni volta che ne manca uno.

Dopo l'inserimento, imposti un flag end per distinguere una parola completa da un semplice prefisso.

Per cercare una parola, segua i caratteri: se manca un passaggio, la parola non è presente. Controlli poi il flag end.

Una query su un prefisso segue lo stesso percorso, ma senza controllare il flag end. Raggiungere l'ultimo nodo significa che la risposta è sì.

L'inserimento e la ricerca costano O(L), dove L è la lunghezza della parola, indipendentemente dal numero di parole memorizzate. Conta la lunghezza.

Memorizzi un conteggio in ogni nodo per rispondere immediatamente a quante parole memorizzate condividono un determinato prefisso.

I trie sono alla base dell'autocomplete, delle verifiche nei dizionari e dei problemi di massimo XOR sui bit. Sono uno strumento essenziale nei problemi di stringhe dei contest.

Ora può costruire un trie, inserire e cercare in O(L) e rispondere rapidamente a query sui prefissi e sui conteggi. 🌟