Tight Upper and Lower Bounds on Suffix Tree Breadth

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

doi:10.1016/j.tcs.2020.11.037

Tight Upper and Lower Bounds on Suffix Tree Breadth

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

Research output: Contribution to journal › Article › Scientific › peer-review

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.

Original language	English
Journal	Theoretical Computer Science
Volume	854
Pages (from-to)	63-67
Number of pages	5
ISSN	0304-3975
DOIs	https://doi.org/10.1016/j.tcs.2020.11.037
Publication status	Published - 16 Jan 2021
MoE publication type	A1 Journal article-refereed

Fields of Science

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

Access to Document

10.1016/j.tcs.2020.11.037

FinaldraftAccepted author manuscript, 445 KBLicence: CC BY-NC-ND

Cite this

@article{d0b1b061d2bf45e2bb59b929c277338e,

title = "Tight Upper and Lower Bounds on Suffix Tree Breadth",

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.",

keywords = "113 Computer and information sciences, String, Suffix tree, Suffix array, Longest common prefix, Combinatorics",

author = "Golnaz Badkobeh and Pawel Gawrychowski and Juha K{\"a}rkk{\"a}inen and Simon Puglisi and Bella Zhukova",

year = "2021",

month = jan,

day = "16",

doi = "10.1016/j.tcs.2020.11.037",

language = "English",

volume = "854",

pages = " 63--67",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier Scientific Publ. Co",

}

TY - JOUR

T1 - Tight Upper and Lower Bounds on Suffix Tree Breadth

AU - Badkobeh, Golnaz

AU - Gawrychowski, Pawel

AU - Kärkkäinen, Juha

AU - Puglisi, Simon

AU - Zhukova, Bella

PY - 2021/1/16

Y1 - 2021/1/16

N2 - 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.

AB - 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.

KW - 113 Computer and information sciences

KW - String

KW - Suffix tree

KW - Suffix array

KW - Longest common prefix

KW - Combinatorics

U2 - 10.1016/j.tcs.2020.11.037

DO - 10.1016/j.tcs.2020.11.037

M3 - Article

SN - 0304-3975

VL - 854

SP - 63

EP - 67

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -