Tight Upper and Lower Bounds on Suffix Tree Breadth

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

No full text available
[img] Text
main.pdf - Accepted Version
Permissions: Administrator Access Only until 20 November 2021.
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (456kB)

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:


Identification Number (DOI):



String, Suffix tree, Suffix array, Longest common prefix, Combinatorics

Departments, Centres and Research Units:



8 November 2020Accepted
20 November 2020Published Online

Item ID:


Date Deposited:

11 Jun 2020 12:02

Last Modified:

19 Mar 2021 12:29

Peer Reviewed:

Yes, this version has been peer-reviewed.



View statistics for this item...

Edit Record Edit Record (login required)