Dynamic construction of an antidictionary with linear complexity
From MaRDI portal
Publication:2437769
DOI10.1016/j.tcs.2014.01.021zbMath1358.68082MaRDI QIDQ2437769
Takahiro Ota, Hiroyoshi Morita, Hirotada Fukae
Publication date: 13 March 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2014.01.021
data compression; suffix tree; linear computational complexity; incremental construction; antidictionary
68Q25: Analysis of algorithms and problem complexity
68P30: Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
68P05: Data structures
Related Items
Absent words in a sliding window with applications, Minimal Unique Substrings and Minimal Absent Words in a Sliding Window
Cites Work
- Unnamed Item
- Automata and forbidden words
- On suffix extensions in suffix trees
- The smallest automaton recognizing the subwords of a text
- From Ukkonen to McCreight and Weiner: A unifying view of linear-time suffix tree construction
- On-line construction of suffix trees
- Algorithms on Strings, Trees and Sequences
- Combinatorial Pattern Matching