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, ISSN 0304-3975 [Article] (In Press)

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:

Article

Identification Number (DOI):

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

Keywords:

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

Departments, Centres and Research Units:

Computing

Dates:

DateEvent
8 November 2020Accepted
20 November 2020Published Online

Item ID:

28732

Date Deposited:

11 Jun 2020 12:02

Last Modified:

27 Nov 2020 10:41

Peer Reviewed:

Yes, this version has been peer-reviewed.

URI:

https://research.gold.ac.uk/id/eprint/28732

View statistics for this item...

Edit Record Edit Record (login required)