Linear-size suffix tries and linear-size CDAWGs simplified and improved

DOI10.1007/s00236-024-00465-9MaRDI QIDQ6634511

Shunsuke Inenaga

Publication date: 7 November 2024

Published in: Acta Informatica (Search for Journal in Brave)

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Linear-size suffix tries
• On the structure of compacted subword graphs of Thue-Morse words and their applications
• The level ancestor problem simplified
• The structure of subword graphs and suffix trees of Fibonacci words
• The smallest automaton recognizing the subwords of a text
• Finding level-ancestors in trees
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• On-line construction of compact directed acyclic word graphs
• Discovering instances of poetic allusion from anthologies of classical Japanese poems
• On-line construction of suffix trees
• Efficient computation of substring equivalence classes with suffix arrays
• The Smallest Grammar Problem
• A universal algorithm for sequential data compression
• 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
• At the roots of dictionary compression: string attractors
• Dynamic LCA Queries on Trees
• Linear-time computation of DAWGs, symmetric indexing structures, and MAWs for integer alphabets

This page was built for publication: Linear-size suffix tries and linear-size CDAWGs simplified and improved