Near real-time suffix tree construction via the fringe marked ancestor problem

DOI10.1016/J.JDA.2012.07.003MaRDI QIDQ2376800zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Giuseppe F. Italiano, Dany Breslauer

Publication date 24 June 2013

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2012.07.003

zbMATH Keywords

string algorithmssuffix trees

Mathematics Subject Classification ID

Data structures (68P05) Algorithms on strings (68W32)

Recommendations

• On-line construction of suffix trees
• From Ukkonen to McCreight and Weiner: A unifying view of linear-time suffix tree construction
• Time optimal left to right construction of position trees
• Real-time pattern matching and quasi-real-time construction of suffix trees (preliminary version)
• On-line suffix tree construction with reduced branching

Cited in

(13)

• On updating suffix tree labels
• Fully-online suffix tree and directed acyclic word graph construction for multiple texts
• Real-time pattern matching and quasi-real-time construction of suffix trees (preliminary version)
• Alphabet-dependent string searching with wexponential search trees
• Online detection of repetitions with backtracking
• Linear-size suffix tries
• The longest common substring problem
• Online algorithms for constructing linear-size suffix trie
• Searching Long Repeats in Streams
• The online house numbering problem: min-max online list labeling
• Linear time online algorithms for constructing linear-size suffix trie
• Faster sliding window string indexing in streams
• On suffix extensions in suffix trees

This page was built for publication: Near real-time suffix tree construction via the fringe marked ancestor problem

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