Fully-online suffix tree and directed acyclic word graph construction for multiple texts

DOI10.1007/s00453-019-00646-wzbMath1432.68611arXiv1507.07622OpenAlexW2988247461MaRDI QIDQ2309475

Takuya Takagi, Hiroki Arimura, Diptarama Hendrian, Shunsuke Inenaga, Dany Breslauer

Publication date: 1 April 2020

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1507.07622

zbMATH Keywords

online algorithmsstring algorithmssuffix treesDAWGsmultiple texts

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Data structures (68P05) Online algorithms; streaming algorithms (68W27) Algorithms on strings (68W32)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The smallest automaton recognizing the subwords of a text
• Transducers and repetitions
• On-line construction of suffix trees
• Near real-time suffix tree construction via the fringe marked ancestor problem
• Alphabet-Dependent String Searching with Wexponential Search Trees
• Compressed indexes for dynamic text collections
• Algorithms on Strings, Trees and Sequences
• Improved Dynamic Text Indexing
• Fast incremental planarity testing
• Complete inverted files for efficient text retrieval and analysis
• Fully-online Construction of Suffix Trees for Multiple Texts.

This page was built for publication: Fully-online suffix tree and directed acyclic word graph construction for multiple texts