Sufixový strom

Sufixový strom je speciální druh trie, která uchovává všechny sufixy (podřetězce od nějakého znaku až do konce) nějakého řetězce. Každý vnitřní vrchol odpovídá prefixu nějakého sufixu, tedy nějakému podslovu.

Je-li tato trie komprimovaná (cesty ve stromu jsou nahrazeny hranou), dá se reprezentovat v prostoru lineárním k délce řetězce. Existují algoritmy pro postavení sufixového stromu v lineárním čase.

Sufixový strom umožňuje rychle řešit řadu řetězcových úloh, například inverzní vyhledávání, hledání nejdelšího opakujícího se podslova nebo Burrowsovu-Wheelerovu transformaci.

Externí odkazy

[url=https://people.ksp.sk/~kuko/gnarley-trees/SuffixTree.html]Vizualizace suffixového stromu[/url]

Kategorie:Stromy (datové struktury)