Improved Algorithms for the Range Next Value Problem and Applications
Costas S. Iliopoulos, Maxime Crochemore, Marcin Kubica, Md. Saidur Rahman, Tomasz Waleń · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2008
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 Crochemore et. al [Finding Patterns In Given Intervals, MFCS 2007]. 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.