Improved algorithms for the range next value problem and applications. (English) Zbl 1259.68226

Albers, Susanne (ed.) et al., STACS 2008. 25th international symposium on theoretical aspects of computer science, Bordeaux, France, February 21–23, 2008. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-06-4). LIPIcs – Leibniz International Proceedings in Informatics 1, 205-216, electronic only (2008).
Summary: The Range Next Value problem (Problem RNV) is a recent interesting variant of the range search problems, where the query is for the immediate next (or equal) value of a given number within a given interval of an array. Problem RNV was introduced and studied very recently by the second author et. al in [Fundam. Inform. 101, No. 3, 173–186 (2010; Zbl 1216.68353)]. In this paper, we present improved algorithms for Problem RNV. We also show how this problem can be used to achieve optimal query time for a number of interesting variants of the classic pattern matching problems.
For the entire collection see [Zbl 1213.68020].


68W05 Nonnumerical algorithms
68P05 Data structures


Zbl 1216.68353
Full Text: DOI Link