Substring range reporting. (English) Zbl 1360.68375

Summary: We revisit various string indexing problems with range reporting features, namely, position-restricted substring searching, indexing substrings with gaps, and indexing substrings with intervals. We obtain the following main results. cm
We give efficient reductions for each of the above problems to a new problem, which we call substring range reporting. Hence, we unify the previous work by showing that we may restrict our attention to a single problem rather than studying each of the above problems individually.
We show how to solve substring range reporting with optimal query time and little space. Combined with our reductions this leads to significantly improved time-space trade-offs for the above problems. In particular, for each problem we obtain the first solutions with optimal time query and \(O(n\log^{O(1)}n)\) space, where \(n\) is the length of the indexed string.
We show that our techniques for substring range reporting generalize to substring range counting and substring range emptiness variants. We also obtain non-trivial time-space trade-offs for these problems.
Our bounds for substring range reporting are based on a novel combination of suffix trees and range reporting data structures. The reductions are simple and general and may apply to other combinations of string indexing with range reporting.


68P05 Data structures
68W32 Algorithms on strings
Full Text: DOI Link


[1] Alstrup, S.; Brodal, G.; Rauhe, T., Optimal static range reporting in one dimension, 476-482, (2001) · Zbl 1323.68536
[2] Alstrup, S.; Stølting Brodal, G.; Rauhe, T., New data structures for orthogonal range searching, 198-207, (2000)
[3] Amir, A.; Chencinski, E.; Iliopoulos, C.S.; Kopelowitz, T.; Zhang, H., Property matching and weighted matching, Theor. Comput. Sci., 395, 298-310, (2008) · Zbl 1142.68066
[4] Bose, P.; He, M.; Maheshwari, A.; Morin, P., Succinct orthogonal range search structures on a grid with applications to text indexing, No. 5664, 98-109, (2009) · Zbl 1253.68103
[5] Chan, T.M.; Larsen, K.; Pǎtraşcu, M., Orthogonal range searching on the RAM, revisited, 1-10, (2011) · Zbl 1283.68139
[6] Chazelle, B., Filtering search: a new approach to query-answering, SIAM J. Comput., 15, 703-724, (1986) · Zbl 0612.68088
[7] Cohen, H.; Porat, E., Range non-overlapping indexing, No. 5878, 1044-1053, (2009) · Zbl 1273.68097
[8] Crochemore, M.; Iliopoulos, C.S.; Kubica, M.; Rahman, M.S.; Tischler, G.; Walen, T., Improved algorithms for the range next value problem and applications, Theor. Comput. Sci., 434, 23-34, (2012) · Zbl 1244.68031
[9] Crochemore, M.; Iliopoulos, C.S.; Kubica, M.; Rahman, M.S.; Walen, T., Improved algorithms for the range next value problem and applications, No. 1, 205-216, (2008) · Zbl 1259.68226
[10] Crochemore, M.; Iliopoulos, C.S.; Kubica, M.; Rahman, M.S.; Walen, T., Finding patterns in given intervals, Fundam. Inform., 101, 173-186, (2010) · Zbl 1216.68353
[11] Crochemore, M.; Iliopoulos, C.S.; Rahman, M.S., Optimal prefix and suffix queries on texts, Inf. Process. Lett., 108, 320-325, (2008) · Zbl 1191.68205
[12] Crochemore, M.; Tischler, G., The gapped suffix array: A new index structure, No. 6393, 359-364, (2010)
[13] Farach-Colton, M.; Ferragina, P.; Muthukrishnan, S., On the sorting-complexity of suffix tree construction, J. ACM, 47, 987-1011, (2000) · Zbl 1094.68694
[14] Fredman, M.L.; Komlós, J.; Szemerédi, E., Storing a sparse table with \(O\)(1) worst case access time, J. ACM, 31, 538-544, (1984) · Zbl 0629.68068
[15] Gusfield, D.: Algorithms on strings, trees, and sequences: computer science and computational biology. Cambridge University Press, Cambridge (1997) · Zbl 0934.68103
[16] Hagerup, T.; Miltersen, P.B.; Pagh, R., Deterministic dictionaries, J. Algorithms, 41, 69-85, (2001) · Zbl 1002.68503
[17] Han, Y., Deterministic sorting in \(O\)(\(n\)loglog\(n\)) time and linear space, J. Algorithms, 50, 96-105, (2004) · Zbl 1106.68028
[18] Iliopoulos, C.S.; Rahman, M.S., Faster index for property matching, Inf. Process. Lett., 105, 218-223, (2008) · Zbl 1184.68353
[19] Iliopoulos, C.S.; Rahman, M.S., Indexing factors with gaps, Algorithmica, 55, 60-70, (2009) · Zbl 1180.68127
[20] JáJá, J.; Mortensen, C.W.; Shi, Q., Space-efficient and fast algorithms for multidimensional dominance reporting and counting, No. 3341, 558-568, (2004) · Zbl 1116.68629
[21] Juan, M.; Liu, J.; Wang, Y., Errata for “faster index for property matching”, Inf. Process. Lett., 109, 1027-1029, (2009) · Zbl 1202.68273
[22] Mäkinen, V.; Navarro, G., Position-restricted substring searching, 703-714, (2006) · Zbl 1145.68392
[23] Mäkinen, V.; Navarro, G., Rank and select revisited and extended, Theor. Comput. Sci., 387, 332-347, (2007) · Zbl 1144.68023
[24] Mehlhorn, K.; Nähler, S., Bounded ordered dictionaries in \(O\)(loglog\(N\)) time and \(O\)(\(n\)) space, Inf. Process. Lett., 35, 183-189, (1990) · Zbl 0702.68042
[25] Mortensen, C.W.; Pagh, R.; Pǎtraçcu, M., On dynamic range reporting in one dimension, 104-111, (2005) · Zbl 1192.68184
[26] Pǎtraşcu, M., Lower bounds for 2-dimensional range counting, 40-46, (2007) · Zbl 1232.68068
[27] Pǎtraşcu, M.; Thorup, M., Time-space trade-offs for predecessor search, 232-240, (2006) · Zbl 1301.68150
[28] Porat, E.: Personal communication (2011) · Zbl 0612.68088
[29] Thorup, M., Space efficient dynamic stabbing with fast queries, 649-658, (2003) · Zbl 1192.68143
[30] Emde Boas, P., Preserving order in a forest in less than logarithmic time and linear space, Inf. Process. Lett., 6, 80-82, (1977) · Zbl 0364.68053
[31] Emde Boas, P.; Kaas, R.; Zijlstra, E., Design and implementation of an efficient priority queue, Math. Syst. Theory, 10, 99-127, (1977) · Zbl 0363.60104
[32] Yu, C.-C.; Hon, W.-K.; Wang, B.-F., Improved data structures for the orthogonal range successor problem, Comput. Geom., 44, 148-159, (2011) · Zbl 1209.65027
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.