On Suffix Tree Breadth

Tools

Badkobeh, Golnaz; Karkkainen, Juha; Puglisi, Simon and Zhukova, Bella. 2017. On Suffix Tree Breadth. Lecture Notes in Computer Science, 1058, pp. 68-73. ISSN 0302-9743 [Article]

Preview

Text
suffix-tree-breadth.pdf - Accepted Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.
Download (246kB) | Preview

Official URL: https://link.springer.com/chapter/10.1007/978-3-31...

Abstract or Description

The suffix tree—the compacted trie of all the suffixes of a string—is the most important and widely-used data structure in string processing. We consider a natural combinatorial question about suffix trees: for a string S of length n, how many nodes νS(d) can there be at (string) depth d in its suffix tree? We prove ν(n,d)=maxS∈ΣnνS(d) is O((n/d)logn) , and show that this bound is almost tight, describing strings for which νS(d)=d is Ω((n/d)log(n/d))

Item Type:

Article

Identification Number (DOI):

https://doi.org/10.1007/978-3-319-67428-5_6

Additional Information:

Part of the Lecture Notes in Computer Science book series (LNCS, volume 10508).
*
G. Badkobeh—Supported by a Leverhulme Early Career Fellowship.

S.J. Puglisi and B. Zhukova—Supported by the Academy of Finland via grant 294143.