Hva er forskjellen på et suffikstre og et suffiksarray med hensyn til minnebruk og bruk?
Klikk for å snu kortet
Begge indekserer alle suffiks av en tekst for raske delstrengssøk. Et suffikstre er et komprimert tre (Patricia-trie) over suffiksene som gir O(m) søk, men bruker mye minne (store konstanter, typisk 10–20 byte/tegn pga. noder og pekere). Et suffiksarray lagrer bare de sorterte suffiks-startindeksene (n heltall), bruker langt mindre minne og gir O(m log n) søk (eller O(m + log n) med LCP-array). Suffiksarray foretrekkes derfor i praksis pga. kompakthet og cache-vennlighet.
Space / Enter for å snu