A Suffix Tree Or Not a Suffix Tree?

Tatiana Starikovskaya, Hjalte Wedel Vildhøj

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


In this paper we study the structure of suffix trees. Given an unlabeled tree r on n nodes and suffix links of its internal nodes, we ask the question “Is r a suffix tree?”, i.e., is there a string S whose suffix tree has the same topological structure as r? 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. We prove that r 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.
Original languageEnglish
Title of host publicationRevised Selected Papers of the 25th International Workshop on Combinatorial Algorithms, IWOCA 2014
EditorsJan Kratochvíl, Mirka Miller, Dalibor Froncek
Publication date2015
ISBN (Print)978-3-319-19314-4
ISBN (Electronic)978-3-319-19315-1
Publication statusPublished - 2015
Event25th International Workshop on Combinatorial Algorithms (IWOCA 2014) - Duluth, Minnesota, United States
Duration: 15 Oct 201417 Oct 2014
Conference number: 25


Workshop25th International Workshop on Combinatorial Algorithms (IWOCA 2014)
CountryUnited States
CityDuluth, Minnesota
Internet address
SeriesLecture Notes in Computer Science

Fingerprint Dive into the research topics of 'A Suffix Tree Or Not a Suffix Tree?'. Together they form a unique fingerprint.

Cite this