Faster suffix tree construction with missing suffix links

Richard Cole, Ramesh Hariharan

Research output: Contribution to journalArticlepeer-review

Abstract

We consider suffix tree construction for situations with missing suffix links. Two examples of such situations are suffix trees for parameterized strings and suffix trees for two-dimensional arrays. These trees also have the property that the node degrees may be large. We add a new back-propagation component to McCreight's algorithm and also give a high probability hashing scheme for large degrees. We show that these two features enable construction of suffix trees for general situations with missing suffix links in O(n) time, with high probability. This gives the first randomized linear time algorithm for constructing suffix trees for parameterized strings.

Original languageEnglish (US)
Pages (from-to)26-42
Number of pages17
JournalSIAM Journal on Computing
Volume33
Issue number1
DOIs
StatePublished - Nov 2003

Keywords

  • Dynamic perfect hashing
  • Parameterized strings
  • Suffix tree
  • Two-dimensional suffix trees

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Faster suffix tree construction with missing suffix links'. Together they form a unique fingerprint.

Cite this