De ce contează?
Deschide un dicționar la litera „a”. Cuvintele care încep la fel stau una lângă alta: „ana”, „an”, „are” împart toate primul „trunchi” de litere — pe „a”. Un trie e fix asta, dar ridicat în picioare: un arbore în care fiecare muchie e o literă, iar cuvintele cu același început împart aceleași prime muchii ale drumului.
Ce este
Un trie (arbore de prefixe) e un arbore cu rădăcină în care fiecare muchie poartă o literă, iar un drum de la rădăcină în jos citește un prefix. Imaginează-ți că pleci dintr-o rădăcină goală și, de fiecare dată când cobori pe o muchie, „scrii” litera de pe ea. Un cuvânt e atunci un drum complet. Dacă două cuvinte încep la fel, primele lor litere sunt aceleași, deci urmează același drum până în punctul unde se despart. Prefixul comun e stocat o singură dată — exact ca în dicționar.
Aici e tot câștigul: cuvintele cu prefix comun împart fizic drumul, deci ca să cauți un cuvânt cobori câte o muchie pe literă și gata. Costul e O(lungimea cuvantului) — nu depinde deloc de câte cuvinte ai în structură, fie ele zece sau un milion.