Hahmontunnistus trie-puuta käyttäen

Hahmon etsiminen trie-puusta on yksinkertaista: lähdetään liikkeelle trie-puun juuresta ja hahmon ensimmäisestä merkistä. Puussa edetään merkki kerrallaan seuraten merkkiä vastaavaa linkkiä. Mikäli merkkiä vastaavaa linkkiä ei löydy, ei etsitty hahmo esiinny puussa. Kun hahmon viimeistä merkkiä vastaava trie-puun solmu on löytynyt, ovat löytyneen solmun alipuun lehdet hahmon esiintymiä vastaavien loppuosien lehtisolmut. Sopivalla tietorakenteella näitä lehtisolmuja vastaavat loppuosien positiot löytyvät tehokkaasti ilman koko alipuun läpikäyntiä. Näin ollen haun aikavaatimus on $O(k\vert P\vert)$.

Edellisessä kappaleessa oletettiin, että trie-puun solmusta päästään hahmon merkillä etenemään seuraavaan solmuun vakioajassa. Tämä pitääkin paikkansa, mikäli trie-puun solmun linkit on toteutettu merkillä indeksoitavana taulukkona. Tällä tavalla toteutetusta trie-puusta tulee kuitenkin hyvin suuri, koska jokaisen solmun kooksi tulee tällöin aakkoston kokoisen taulukon koko $\vert\Sigma\vert$. Käytännössä trie-puun solmussa kannattaa käyttää jotain muuta hakurakennetta, jolloin puun solmusta päästään seuraavaan solmuun ajassa $\log \vert\Sigma\vert$. Ongelma on itse asiassa aivan sama, kuin AC-automaatin tapauksessa luvussa 4.4. Koska trie-puut ovat paljon suurempia kuin AC-automaatit (tekstin koko vastaan hahmojen koot), on ongelma trie-puiden tapauksessa paljon akuutimpi. Jatkossa kuitenkin ajatellaan solmusta toiseen siirtymiseen tarvittavan ajan olevan vakio.