Online algorithms for constructing linear-size suffix trie

DOI10.4230/LIPICS.CPM.2019.30OpenAlexW2964305773MaRDI QIDQ5088922

Diptarama Hendrian, Shunsuke Inenaga, Takuya Takagi

Publication date: 18 July 2022

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

zbMATH Keywords

online algorithmpattern matchingindexing structurelinear-size suffix trie

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Related Items (3)

Linear-time computation of DAWGs, symmetric indexing structures, and MAWs for integer alphabets ⋮ Linear time online algorithms for constructing linear-size suffix trie ⋮ Linear-size suffix tries and linear-size CDAWGs simplified and improved

Cites Work

• Unnamed Item
• Unnamed Item
• Linear-size suffix tries
• On-line construction of position heaps
• Faster Lyndon factorization algorithms for SLP and LZ78 compressed text
• Position heaps: a simple and dynamic text indexing data structure
• The smallest automaton recognizing the subwords of a text
• On-line construction of compact directed acyclic word graphs
• On-line construction of suffix trees
• Near real-time suffix tree construction via the fringe marked ancestor problem
• Efficient computation of substring equivalence classes with suffix arrays
• Alphabet-Dependent String Searching with Wexponential Search Trees
• Suffix Arrays: A New Method for On-Line String Searches
• Linear work suffix array construction
• Fast Label Extraction in the CDAWG
• Linear-Size CDAWG: New Repetition-Aware Indexing and Grammar Compression
• Complete inverted files for efficient text retrieval and analysis
• Random Access to Grammar-Compressed Strings and Trees
• On the sorting-complexity of suffix tree construction

This page was built for publication: Online algorithms for constructing linear-size suffix trie