Linear-time computation of DAWGs, symmetric indexing structures, and MAWs for integer alphabets
From MaRDI portal
Publication:6093582
DOI10.1016/j.tcs.2023.114093zbMath1520.68229arXiv2307.01428OpenAlexW4385360496MaRDI QIDQ6093582
Shunsuke Inenaga, Hideo Bannai, Yuta Fujishige, Yuki Tsujimaru, Masayuki Takeda
Publication date: 7 September 2023
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2307.01428
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Automata and forbidden words
- Linear-size suffix tries
- Efficient computation of shortest absent words in a genomic sequence
- The smallest automaton recognizing the subwords of a text
- Linear bidirectional on-line construction of affix trees
- Words and forbidden factors
- On-line construction of compact directed acyclic word graphs
- Alignment-free sequence comparison using absent words
- Transducers and repetitions
- Suffix trees, DAWGs and CDAWGs for forward and backward tries
- Compressed suffix trees with full functionality
- Versatile Succinct Representations of the Bidirectional Burrows-Wheeler Transform
- Alphabet-Dependent String Searching with Wexponential Search Trees
- Suffix Arrays: A New Method for On-Line String Searches
- Efficient Computation of Substring Equivalence Classes with Suffix Arrays
- A Space-Economical Suffix Tree Construction Algorithm
- New text indexing functionalities of the compressed suffix arrays
- Online algorithms for constructing linear-size suffix trie
- Complete inverted files for efficient text retrieval and analysis
- Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
- On the sorting-complexity of suffix tree construction
- On extended special factors of a word
