Tight Upper and Lower Bounds on Suffix Tree Breadth

Show full item record




Badkobeh , G , Gawrychowski , P , Kärkkäinen , J , Puglisi , S & Zhukova , B 2021 , ' Tight Upper and Lower Bounds on Suffix Tree Breadth ' , Theoretical Computer Science , vol. 854 , pp. 63-67 . https://doi.org/10.1016/j.tcs.2020.11.037

Title: Tight Upper and Lower Bounds on Suffix Tree Breadth
Author: Badkobeh, Golnaz; Gawrychowski, Pawel; Kärkkäinen, Juha; Puglisi, Simon; Zhukova, Bella
Contributor organization: Department of Computer Science
Practical Algorithms and Data Structures on Strings research group / Juha Kärkkäinen
Helsinki Institute for Information Technology
Algorithmic Bioinformatics
Genome-scale Algorithmics research group / Veli Mäkinen
Date: 2021-01-16
Language: eng
Number of pages: 5
Belongs to series: Theoretical Computer Science
ISSN: 0304-3975
DOI: https://doi.org/10.1016/j.tcs.2020.11.037
URI: http://hdl.handle.net/10138/341373
Abstract: 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 nu(S)(d) can there be at (string) depth d in its suffix tree? We prove nu(n, d) = max(S) (is an element of Sigma n) nu(S)(d) is O ((n/d) log(n/d)), and show that this bound is asymptotically tight, describing strings for which nu(S)(d) is Omega((n/d)log(n/d)). (C) 2020 Elsevier B.V. All rights reserved.
Subject: 113 Computer and information sciences
Suffix tree
Suffix array
Longest common prefix
Peer reviewed: Yes
Rights: cc_by_nc_nd
Usage restriction: openAccess
Self-archived version: acceptedVersion

Files in this item

Total number of downloads: Loading...

Files Size Format View
Finaldraft.pdf 445.4Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record