Research Online

Logo

Goldsmiths - University of London

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]

[img]
Preview
Text
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)νS(d) can there be at (string) depth d in its suffix tree? We prove ν(n,d)=maxS∈ΣnνS(d)ν(n,d)=maxS∈ΣnνS(d) is O((n/d)logn)O((n/d)log⁡n) , and show that this bound is almost tight, describing strings for which νS(d)νS(d) is Ω((n/d)log(n/d))Ω((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.

Departments, Centres and Research Units:

Computing

Dates:

DateEvent
10 July 2017Accepted
6 September 2017Published Online

Item ID:

21677

Date Deposited:

03 Oct 2017 12:30

Last Modified:

09 Jul 2018 13:47

Peer Reviewed:

Yes, this version has been peer-reviewed.

URI:

http://research.gold.ac.uk/id/eprint/21677

View statistics for this item...

Edit Record Edit Record (login required)