Linear time online algorithms for constructing linear-size suffix trie

DOI10.1016/j.tcs.2024.114765MaRDI QIDQ6614010

Mitsuru Funakoshi, Takuya Takagi, Diptarama Hendrian, Keisuke Goto, Shunsuke Inenaga

Publication date: 7 October 2024

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

zbMATH Keywords

online algorithmpattern matchingindexing structurelinear-size suffix trienearest marked ancestor

Mathematics Subject Classification ID

Data structures (68P05) Online algorithms; streaming algorithms (68W27)

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
• A linear-time algorithm for a special case of disjoint set union
• 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
• Dynamic orthogonal segment intersection search
• Online algorithms for constructing linear-size suffix trie
• 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: Linear time online algorithms for constructing linear-size suffix trie