Loppuosataulukko

Loppuosataulukko (engl. suffix array) [MM93] on vaihtoehtoinen tietorakenne loppuosapuille. Loppuosataulukko on kaikki $S$:n loppuosat sisältävä järjestetty taulukko. Perinteistä binäärihakua käyttäen tästä taulukosta löydetään kaikki merkkijonon $P$ esiintymät $O(m \log n)$ ajassa, kun $m$ on merkkijonon $P$ pituus. Kun loppuosataulukkoon on liitetty mukaan informaatio kahden taulukon vierekkäin sijaitsevan alkion pisimmistä yhteisistä alkuosista (lcp, longest common prefix), voidaan merkkijonohauissa symbolien välisiä vertailuja ohittaa ja siten vastata kyselyyn $O(m+\log n)$ ajassa.

Loppuosataulukoiden etu verrattuna loppuosapuihin on niiden pienempi koko. Käytännössä tiivistetynkin loppuosapuun koko on kaikilla loppuosapuun toteutuksilla pienimmillään $16n$, kun taas loppuosataulukon kooksi tulee $4n$, olettaen että taulukon alkiot ovat 32-bittisiä kokonaislukuja. Toisin kuin loppuosapuiden tapauksessa, loppuosataulukon koko riippuu ainoastaan tekstin pituudesta.