Internal shortest absent word queries in constant time and linear space
From MaRDI portal
Publication:2672592
DOI10.1016/j.tcs.2022.04.029OpenAlexW3171998682MaRDI QIDQ2672592
Panagiotis Charalampopoulos, Golnaz Badkobeh, Solon P. Pissis, Dmitry Kosolobov
Publication date: 13 June 2022
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2106.01763
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Automata and forbidden words
- Computing minimal and maximal suffixes of a substring
- Using minimal absent words to build phylogeny
- Semi-local string comparison: algorithmic techniques and applications
- Fast string matching with k differences
- Complexity of sequences and dynamical systems
- Surpassing the information theoretic bound with fusion trees
- Words and forbidden factors
- A substring-substring LCS data structure
- Alignment-free sequence comparison using absent words
- Internal dictionary matching
- Constructing antidictionaries of long texts in output-sensitive space
- A data structure for substring-substring LCS length queries
- Dynamic and internal longest common substring
- Absent words in a sliding window with applications
- Sublinear algorithms for approximating string compressibility
- Generalized substring compression
- Time-space trade-offs for longest common extensions
- Word assembly through minimal forbidden words
- Tight lower bounds for the longest common extension problem
- Longest Common Extensions in Sublinear Space
- Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
- Minimal Unique Substrings and Minimal Absent Words in a Sliding Window
- Fast Algorithms for Finding Nearest Common Ancestors
- Recursive Star-Tree Parallel Data Structure
- A Linear Space Data Structure for Range LCP Queries*
- Small-space LCE data structure with constant-time queries
- Locally Consistent Parsing for Text Indexing in Small Space
- Counting Palindromes in Substrings
- String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure
- Uniqueness Theorems for Periodic Functions
- Internal Pattern Matching Queries in a Text and Applications
- Wavelet Trees Meet Suffix Trees
- Deterministic Sub-Linear Space LCE Data Structures With Efficient Construction
- Minimal Suffix and Rotation of a Substring in Optimal Time
- More Haste, Less Waste: Lowering the Redundancy in Fully Indexable Dictionaries
- Orthogonal range searching on the RAM, revisited
- Practical Performance of Space Efficient Data Structures for Longest Common Extensions.
- Minimal forbidden factors of circular words
- A linear-space data structure for range-LCP queries in poly-logarithmic time
- Range LCP
- On extended special factors of a word
This page was built for publication: Internal shortest absent word queries in constant time and linear space
