2026-07-26T19:56:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1359 2024-03-06T10:32:58Z ddc:004 open_access

Improved Algorithms for the Range Next Value Problem and Applications Iliopoulos, Costas S. Crochemore, Maxime Kubica, Marcin Rahman, M. Sohel Walen, Tomasz Algorithms Data structures 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Costas S. Iliopoulos and Maxime Crochemore and Marcin Kubica and M. Sohel Rahman and Tomasz Walen 2008 Is Part Of LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2008.1359 urn:nbn:de:0030-drops-13596 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1359 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode