×

zbMATH — the first resource for mathematics

Improved algorithms for the range next value problem and applications. (English) Zbl 1244.68031
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 M. Crochemore, C. S. Iliopoulos and M. S. Rahman [Lect. Notes Comput. Sci. 4708, 645–656 (2007; Zbl 1147.68470)]. 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.

MSC:
68P10 Searching and sorting
68P05 Data structures
68W05 Nonnumerical algorithms
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Apostolico, Alberto; Preparata, Franco P., Data structures and algorithms for the string statistics problem, Algorithmica, 15, 5, 481-494, (1996) · Zbl 0846.68023
[2] Bender, Michael A.; Farach-Colton, Martin, The LCA problem revisited, (), 88-94 · Zbl 0959.68133
[3] Omer Berkman, Uzi Vishkin, Recursive star-tree parallel data structure, 22(2) (1993) 221-242. · Zbl 0770.68044
[4] Brodal, Gerth Stølting; Lyngsø, Rune B.; Östlin, Anna; Pedersen, Christian N. S., Solving the string statistics problem in time \(O(n \log n)\), (), 728-739 · Zbl 1057.68599
[5] Crochemore, Maxime; Iliopoulos, Costas S.; Kubica, Marcin; Rahman, Mohammad Sohel; Walen, Tomasz, Improved algorithms for the range next value problem and applications, (), 205-216 · Zbl 1259.68226
[6] Crochemore, Maxime; Iliopoulos, Costas S.; Rahman, M. Sohel, Finding patterns in given intervals, (), 645-656 · Zbl 1147.68470
[7] Crochemore, Maxime; Kubica, Marcin; Walen, Tomasz; Iliopoulos, Costas S.; Rahman, M. Sohel, Finding patterns in given intervals, Fundam. inform., 101, 3, 173-186, (2010) · Zbl 1216.68353
[8] Fischer, Johannes, Optimal succinctness for range minimum queries, (), 158-169 · Zbl 1283.68141
[9] Fischer, Johannes, Combined data structure for previous- and next-smaller-values, Theoretical computer science, 412, 22, 2451-2456, (2011) · Zbl 1215.68084
[10] Fischer, Johannes; Heun, Volker, A new succinct representation of RMQ-information and improvements in the enhanced suffix array, (), 459-470 · Zbl 1176.68058
[11] H. Gabow, J. Bentley, R. Tarjan, Scaling and related techniques for geometry problems, in: Symposium on the Theory of Computing (STOC), 1984, pp. 135-143.
[12] Roberto Grossi, Ankur Gupta, Jeffrey Scott Vitter, High-order entropy-compressed text indexes, in: SODA, 2003, pp. 841-850. · Zbl 1092.68584
[13] Dov Harel, Robert Endre Tarjan, Fast algorithms for finding nearest common ancestors, 13(2) (1984) 338-355. · Zbl 0535.68022
[14] Jacobson, G., Space-efficient static trees and graphs, (), 549-554
[15] Keller, Orgad; Kopelowitz, Tsvi; Lewenstein, Moshe, Range non-overlapping indexing and successive List indexing, (), 625-636 · Zbl 1209.68160
[16] Mäkinen, Veli; Navarro, Gonzalo, Position-restricted substring searching, (), 703-714 · Zbl 1145.68392
[17] Mäkinen, Veli; Navarro, Gonzalo, Rank and select revisited and extended, Theoretical computer science, 387, 3, 332-347, (2007) · Zbl 1144.68023
[18] Munro, J. I., Tables, (), 37-42
[19] Ely Porat, Private communication.
[20] Sadakane, Kunihiki, Succinct data structures for flexible text retrieval systems, Journal of discrete algorithms, 5, 1, 12-22, (2007) · Zbl 1137.68360
[21] Baruch Schieber, Uzi Vishkin, On finding lowest common ancestors: Simplification and parallelization 17(6) (1988) 1253-1262. · Zbl 0669.68049
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.