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.

Original languageEnglish
JournalTheoretical Computer Science
Pages (from-to) 63-67
Number of pages5
Publication statusPublished - 16 Jan 2021
MoE publication typeA1 Journal article-refereed

Fields of Science

  • 113 Computer and information sciences
  • String
  • Suffix tree
  • Suffix array
  • Longest common prefix
  • Combinatorics

Cite this