๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

A Note on the Height of Suffix Trees

โœ Scribed by Devroye, Luc; Szpankowski, Wojciech; Rais, Bonita


Book ID
118178092
Publisher
Society for Industrial and Applied Mathematics
Year
1992
Tongue
English
Weight
587 KB
Volume
21
Category
Article
ISSN
0097-5397

No coin nor oath required. For personal study only.


๐Ÿ“œ SIMILAR VOLUMES


Suffix Trees on Words
โœ A. Andersson; N. J. Larsson; K. Swanson ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› Springer ๐ŸŒ English โš– 148 KB
On the sorting-complexity of suffix tree
โœ Farach-Colton, Martin; Ferragina, Paolo; Muthukrishnan, S. ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› Association for Computing Machinery ๐ŸŒ English โš– 175 KB
The suffix tree of a tree and minimizing
โœ Dany Breslauer ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 1013 KB

This paper gives a linear-time algorithm for the construction of the suffix tree of a tree, which was introduced by Kosaraju, as a natural generalization of the suffix tree of a string. The suffix tree of a tree is used to obtain an efficient algorithm for the minimization of sequential transducers.