Tight Upper and Lower Bounds on Suffix Tree Breadth

Tools

Badkobeh, Golnaz; Gawrychowski, Pawel; Kärkkäinen, Juha; Puglisi, Simon J. and Zhukova, Bella. 2021. Tight Upper and Lower Bounds on Suffix Tree Breadth. Theoretical Computer Science, 854, pp. 63-67. ISSN 0304-3975 [Article]

Preview

Text
main.pdf - Accepted Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.
Download (456kB) | Preview

Official URL: https://doi.org/10.1016/j.tcs.2020.11.037

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) log(n/d)), and show that this bound is asymptotically tight, describing strings for which νS(d) is Ω((n/d)log(n/d)).

Item Type:

Article

Identification Number (DOI):

https://doi.org/10.1016/j.tcs.2020.11.037