Improved algorithms for the range next value problem and applications

详细信息    查看全文

• 作者：Maxime Crochemore^a ; ^b ; ^{maxime.crochemore@kcl.ac.uk} ; Costas S. Iliopoulos^a ; ^{csi@dcs.kcl.ac.uk} ; Marcin Kubica^c ; ^{kubica@mimuw.edu.pl} ; M. Sohel Rahman^d ; ^{msrahman@cse.buet.ac.bd} ; German Tischler^e ; ^{tischler@informatik.uni-wuerzburg.de} ; Tomasz Wale¨½^c ; ^{walen@mimuw.edu.pl}
• 关键词：Algorithms ; Data structures ; Range search problems
• 刊名：Theoretical Computer Science
• 出版年：2012
• 出版时间：25 May, 2012
• 年：2012
• 卷：434
• 期：Complete
• 页码：23-34
• 全文大小：356 K

文摘

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. [Maxime Crochemore, Costas S. Iliopoulos, M. Sohel Rahman, Finding patterns in given intervals, in: Antonin Kucera, Ludek Kucera (Eds.), MFCS, 22 in: Lecture Notes in Computer Science, vol. 4708, Springer, 2007, pp. 645-656]. In this paper, we present improved algorithms for problem RNV and algorithms for extended versions of the RNV problem. 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.