On updating suffix tree labels

DOI10.1016/S0304-3975(97)00243-0MaRDI QIDQ1129015zbMATH OpenOpenAlexFDO

Authors Roberto Grossi, Manuela Montangero, Paolo Ferragina

Publication date 13 August 1998

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

Full work available at URL https://doi.org/10.1016/s0304-3975(97)00243-0

zbMATH Keywords

combinatorial coloring problemdata compressiondynamic data structurestring processingtext indexing

Mathematics Subject Classification ID

Data structures (68P05) Parallel algorithms in computer science (68W10)

Recommendations

• A linear time lower bound on McCreight and general updating algorithms for suffix trees
• Dynamic Text Indexing under String Updates
• Near real-time suffix tree construction via the fringe marked ancestor problem
• Dynamic extended suffix arrays

Cites work

• A Generalization of the Suffix Tree to Square Matrices, with Applications
• A locally adaptive data compression scheme
• A Space-Economical Suffix Tree Construction Algorithm
• A theory of parameterized pattern matching
• A universal algorithm for sequential data compression
• An efficient algorithm for the all pairs suffix-prefix problem
• Compression of individual sequences via variable-rate coding
• Data compression via textual substitution
• Dictionary-Matching on Unbounded Alphabets: Uniform Length Dictionaries
• Dynamic dictionary matching
• Dynamic dictionary matching with failure functions
• Dynamic Text Indexing under String Updates
• Efficient string matching
• Fast parallel and serial approximate string matching
• Fast string matching with k differences
• scientific article; zbMATH DE number 1003303 (Why is no real title available?)
• scientific article; zbMATH DE number 432822 (Why is no real title available?)
• scientific article; zbMATH DE number 1306892 (Why is no real title available?)
• scientific article; zbMATH DE number 826058 (Why is no real title available?)
• scientific article; zbMATH DE number 910911 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• Improved dynamic dictionary matching
• Optimal off-line detection of repetitions in a string
• Structural properties of the string statistics problem
• Sublinear approximate string matching and biological applications
• The design of dynamic data structures
• The suffix tree of a tree and minimizing sequential transducers

Cited in

(6)

• A linear time lower bound on McCreight and general updating algorithms for suffix trees
• Online Suffix Tree Construction for Streaming Sequences
• Contracted Suffix Trees: A Simple and Dynamic Text Indexing Data Structure
• In-place update of suffix array while recoding words
• Position heaps: a simple and dynamic text indexing data structure
• Efficiency issues in the KBMAG procedure

This page was built for publication: On updating suffix tree labels

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1129015)