A suffix tree or not a suffix tree?

Tatiana Starikovskaya, Hjalte Wedel Vildhøj

Research output: Contribution to journalJournal articleResearchpeer-review

1 Downloads (Pure)

Abstract

In this paper we study the structure of suffix trees. Given an unlabeled tree τ on n nodes and suffix links of its internal nodes, we ask the question “Is τ a suffix tree?”, i.e., is there a string S whose suffix tree has the same topological structure as τ? We place no restrictions on S, in particular we do not require that S ends with a unique symbol. This corresponds to considering the more general definition of implicit or extended suffix trees. Such general suffix trees have many applications and are for example needed to allow efficient updates when suffix trees are built online. Deciding if τ is a suffix tree is not an easy task, because, with no restrictions on the final symbol, we cannot guess the length of a string that realizes τ from the number of leaves. And without an upper bound on the length of such a string, it is not even clear how to solve the problem by an exhaustive search. In this paper, we prove that τ is a suffix tree if and only if it is realized by a string S of length n-1, and we give a linear-time algorithm for inferring S when the first letter on each edge is known. This generalizes the work of I et al. (2014) [15]. [All rights reserved Elsevier].
Original languageEnglish
JournalJournal of Discrete Algorithms
Volume32
Pages (from-to)14-23
ISSN1570-8667
DOIs
Publication statusPublished - 2015

Keywords

  • Reverse engineering
  • Suffix trees
  • Suffix links
  • Suffix tour graphs

Fingerprint Dive into the research topics of 'A suffix tree or not a suffix tree?'. Together they form a unique fingerprint.

Cite this