Alphabet-Dependent String Searching with Wexponential Search Trees

DOI10.1007/978-3-319-19929-0_14zbMath1432.68087arXiv1302.3347OpenAlexW1884472997MaRDI QIDQ2942254

Johannes Fischer, Paweł Gawrychowski

Publication date: 20 August 2015

Published in: Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1302.3347

Mathematics Subject Classification ID

Searching and sorting (68P10) Data structures (68P05) Algorithms on strings (68W32)

Related Items (17)

Full-fledged real-time indexing for constant size alphabets ⋮ Alphabet-Dependent String Searching with Wexponential Search Trees ⋮ Lempel Ziv Computation in Small Space (LZ-CISS) ⋮ Engineering Practical Lempel-Ziv Tries ⋮ Linear-time computation of DAWGs, symmetric indexing structures, and MAWs for integer alphabets ⋮ Subsequences in bounded ranges: matching and analysis problems ⋮ Time-Optimal Top-$k$ Document Retrieval ⋮ Unnamed Item ⋮ Practical Evaluation of Lempel-Ziv-78 and Lempel-Ziv-Welch Tries ⋮ Fast compressed self-indexes with deterministic linear-time construction ⋮ Unnamed Item ⋮ Lempel-Ziv-78 compressed string dictionaries ⋮ Lempel-Ziv factorization powered by space efficient suffix trees ⋮ Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing ⋮ Online algorithms for constructing linear-size suffix trie ⋮ Fully-online suffix tree and directed acyclic word graph construction for multiple texts ⋮ Fast Compressed Self-Indexes with Deterministic Linear-Time Construction

Cites Work

• Unnamed Item
• Optimal bounds for the predecessor problem and related problems
• Suffix trays and suffix trists: structures for faster text indexing
• Near real-time suffix tree construction via the fringe marked ancestor problem
• Full-fledged real-time indexing for constant size alphabets
• Managing Unbounded-Length Keys in Comparison-Driven Data Structures with Applications to Online Indexing
• Alphabet-Dependent String Searching with Wexponential Search Trees
• Suffix Arrays: A New Method for On-Line String Searches
• Constructing Efficient Dictionaries in Close to Sorting Time
• Dynamic ordered sets with exponential search trees
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• A Space-Economical Suffix Tree Construction Algorithm
• Dynamic Binary Search

This page was built for publication: Alphabet-Dependent String Searching with Wexponential Search Trees