Improved algorithms for the range next value problem and applications

DOI10.1016/j.tcs.2012.02.015zbMath1244.68031OpenAlexW2026496324WikidataQ61677872 ScholiaQ61677872MaRDI QIDQ428870

Maxime Crochemore, Marcin Kubica, M. Sohel Rahman, German Tischler, Costas S. Iliopoulos, Tomasz Walen

Publication date: 25 June 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.02.015

zbMATH Keywords

algorithmsdata structuresrange search problems

Mathematics Subject Classification ID

Searching and sorting (68P10) Nonnumerical algorithms (68W05) Data structures (68P05)

Related Items

Range selection and predecessor queries in data aware space and time, Position-restricted substring searching over small alphabets, Unnamed Item, I/O-efficient data structures for non-overlapping indexing, Substring range reporting, Ranked document selection, Orthogonal Range Searching for Text Indexing, Data structures on event graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Combined data structure for previous- and next-smaller-values
• Succinct data structures for flexible text retrieval systems
• Data structures and algorithms for the string statistics problem
• Rank and select revisited and extended
• Finding Patterns In Given Intervals
• Fast Algorithms for Finding Nearest Common Ancestors
• Finding Patterns in Given Intervals
• Position-Restricted Substring Searching
• Optimal Succinctness for Range Minimum Queries
• Range Non-overlapping Indexing and Successive List Indexing
• A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• Recursive Star-Tree Parallel Data Structure