On Suffix Tree Breadth

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]

suffix-tree-breadth.pdf - Accepted Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (246kB) | Preview

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:


Identification Number (DOI):


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.

Departments, Centres and Research Units:



10 July 2017Accepted
6 September 2017Published Online

Item ID:


Date Deposited:

03 Oct 2017 12:30

Last Modified:

09 Jun 2020 11:52

Peer Reviewed:

Yes, this version has been peer-reviewed.



View statistics for this item...

Edit Record Edit Record (login required)