On suffix extensions in suffix trees

DOI10.1016/j.tcs.2012.07.018zbMath1251.68081OpenAlexW1918346263WikidataQ61609442 ScholiaQ61609442MaRDI QIDQ714837

Dany Breslauer, Giuseppe F. Italiano

Publication date: 11 October 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.07.018

zbMATH Keywords

string algorithmssuffix trees

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Data structures (68P05) Graph representations (geometric and intersection representations, etc.) (05C62) Algorithms on strings (68W32)

Related Items

A linear time algorithm for shortest cyclic cover of strings, Dynamic construction of an antidictionary with linear complexity, On suffix extensions in suffix trees, A suffix tree or not a suffix tree?

Uses Software

• PATRICIA

Cites Work

• PATRICIA
• On suffix extensions in suffix trees
• A four-stage algorithm for updating a Burrows-Wheeler transform
• Construction of Aho Corasick automaton in linear time for integer alphabets
• Dynamic extended suffix arrays
• Maintaining order in a generalized linked list
• The smallest automaton recognizing the subwords of a text
• Optimal off-line detection of repetitions in a string
• From Ukkonen to McCreight and Weiner: A unifying view of linear-time suffix tree construction
• Linear time algorithms for finding and representing all the tandem repeats in a string
• Transducers and repetitions
• Improved dynamic dictionary matching
• On-line construction of suffix trees
• Near real-time suffix tree construction via the fringe marked ancestor problem
• Constructing suffix arrays in linear time
• Space efficient linear time construction of suffix arrays
• Suffix Arrays: A New Method for On-Line String Searches
• Linear work suffix array construction
• Range Non-overlapping Indexing
• A Space-Economical Suffix Tree Construction Algorithm
• Algorithms on Strings, Trees and Sequences
• Fast incremental planarity testing
• Complete inverted files for efficient text retrieval and analysis
• Uniqueness Theorems for Periodic Functions
• On the sorting-complexity of suffix tree construction
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item