Dynamic construction of an antidictionary with linear complexity

DOI10.1016/j.tcs.2014.01.021zbMath1358.68082OpenAlexW1994720947MaRDI 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

zbMATH Keywords

data compressionsuffix treelinear computational complexityincremental constructionantidictionary

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05)

Related Items

Minimal Unique Substrings and Minimal Absent Words in a Sliding Window, Absent words in a sliding window with applications

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