Tight Upper and Lower Bounds on Suffix Tree Breadth

Golnaz Badkobeh, Pawel Gawrychowski, Juha Kärkkäinen, Simon Puglisi, Bella Zhukova

Forskningsoutput: TidskriftsbidragArtikelVetenskapligPeer review


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.

TidskriftTheoretical Computer Science
Sidor (från-till) 63-67
Antal sidor5
StatusPublicerad - 16 jan. 2021
MoE-publikationstypA1 Tidskriftsartikel-refererad


  • 113 Data- och informationsvetenskap

Citera det här