×

A linear-space data structure for range-LCP queries in poly-logarithmic time. (English) Zbl 1455.68045

In this paper, the authors study the range-LCP problem (or rlcp), which asks, given a text \(T\) of length \(n\), for the Longest Common Prefix (LCP) of suffixes of \(T\) (namely \(T[i,n]\) and \(T[j,n]\)) among all \(\alpha\leq i\neq j\leq \beta\), where \(\alpha\) and \(\beta\) are integers (satisfying \(1\leq \alpha<\beta\leq n\)) given as input.
The main question raised and positively answered by the authors is whether it is possible to answer rlcp in polylogarithmic time, using a linear-space data structure. More precisely, the data structure used takes \(O(n)\) space and is constructed in \(O(n\log n)\) time. Using the above-mentioned data structure, rlcp can then be answered in \(O(\log^{1+\varepsilon} n)\) time, for any \(\varepsilon>0\).
Papers dealing with string algorithms are not always easy to follow for the non-specialist, as this topic has a long and rich history, uses many notations, and (as is the case here) aims at improving time/space complexities and thus provides detailed and thorough analyses. This paper is no exception. One has to be familiar with string algorithms (and in particular with suffix arrays, suffix trees and of course LCP issues) to understand the paper’s contents.

MSC:

68P05 Data structures
68Q25 Analysis of algorithms and problem complexity
68W32 Algorithms on strings
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abedin, P.; Ganguly, A.; Hon, W.; Nekrich, Y.; Sadakane, K.; Shah, R.; Thankachan, S. V., A linear-space data structure for range-lcp queries in poly-logarithmic time, (Computing and Combinatorics - 24th International Conference. Computing and Combinatorics - 24th International Conference, COCOON 2018, Qing Dao, China, July 2-4, 2018, Proceedings (2018)), 615-625 · Zbl 1441.68021
[2] Amir, A.; Apostolico, A.; Landau, G. M.; Levy, A.; Lewenstein, M.; Porat, E., Range LCP, (Algorithms and Computation - 22nd International Symposium. Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Yokohama, Japan, December 2011, Proceedings (2011)), 683-692 · Zbl 1350.68298
[3] Amir, A.; Apostolico, A.; Landau, G. M.; Levy, A.; Lewenstein, M.; Porat, E., Range LCP, J. Comput. Syst. Sci., 80, 7, 1245-1253 (2014) · Zbl 1410.68414
[4] Amir, A.; Lewenstein, M.; Thankachan, S. V., Range LCP queries revisited, (String Processing and Information Retrieval - 22nd International Symposium. String Processing and Information Retrieval - 22nd International Symposium, SPIRE 2015, London, UK, September 1-4, 2015, Proceedings (2015)), 350-361 · Zbl 1320.68019
[5] Patil, M.; Shah, R.; Thankachan, S. V., Faster range LCP queries, (String Processing and Information Retrieval - 20th International Symposium. String Processing and Information Retrieval - 20th International Symposium, SPIRE 2013, Jerusalem, Israel, October 7-9, 2013, Proceedings (2013)), 263-270 · Zbl 1442.68040
[6] Gagie, T.; Karhu, K.; Navarro, G.; Puglisi, S. J.; Sirén, J., Document listing on repetitive collections, (Combinatorial Pattern Matching, 24th Annual Symposium. Combinatorial Pattern Matching, 24th Annual Symposium, CPM 2013, Bad Herrenalb, Germany, June 17-19, 2013, Proceedings (2013)), 107-119 · Zbl 1381.68076
[7] Cormode, G.; Muthukrishnan, S., Substring compression problems, (Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-25 (2005)), 321-330 · Zbl 1297.68278
[8] Keller, O.; Kopelowitz, T.; Feibish, S. L.; Lewenstein, M., Generalized substring compression, Theor. Comput. Sci., 525, 42-54 (2014) · Zbl 1295.68112
[9] Lewenstein, M., Orthogonal range searching for text indexing, (Space-Efficient Data Structures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday (2013)), 267-302 · Zbl 1394.68099
[10] Nekrich, Y.; Navarro, G., Sorted range reporting, (Algorithm Theory - SWAT 2012 - 13th Scandinavian Symposium and Workshops. Algorithm Theory - SWAT 2012 - 13th Scandinavian Symposium and Workshops, Helsinki, Finland, July 4-6, 2012, Proceedings (2012)), 271-282 · Zbl 1347.68343
[11] Chan, T. M.; Larsen, K. G.; Patrascu, M., Orthogonal range searching on the ram, revisited, (Proceedings of the 27th ACM Symposium on Computational Geometry. Proceedings of the 27th ACM Symposium on Computational Geometry, Paris, France, June 13-15, 2011 (2011)), 1-10 · Zbl 1283.68139
[12] Patil, M.; Thankachan, S. V.; Shah, R.; Nekrich, Y.; Vitter, J. S., Categorical range maxima queries, (Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS’14, Snowbird, UT, USA, June 22-27 (2014)), 266-277
[13] Ganguly, A.; Patil, M.; Shah, R.; Thankachan, S. V., A linear space data structure for range LCP queries, Fundam. Inform., 163, 3, 245-251 (2018) · Zbl 1405.68463
[14] Willard, D. E., Log-logarithmic worst-case range queries are possible in space theta(n), Inf. Process. Lett., 17, 2, 81-84 (1983) · Zbl 0509.68106
[15] Fischer, J.; Heun, V., Space-efficient preprocessing schemes for range minimum queries on static arrays, SIAM J. Comput., 40, 2, 465-492 (2011) · Zbl 1222.05024
[16] Chazelle, B., A functional approach to data structures and its use in multidimensional searching, SIAM J. Comput., 17, 3, 427-462 (1988) · Zbl 0679.68074
[17] Weiner, P., Linear pattern matching algorithms, (14th Annual Symposium on Switching and Automata Theory. 14th Annual Symposium on Switching and Automata Theory, Iowa City, Iowa, USA, October 15-17 (1973)), 1-11
[18] Gawrychowski, P.; Lewenstein, M.; Nicholson, P. K., Weighted ancestors in suffix trees, (Algorithms - ESA 2014 - 22nd Annual European Symposium. Algorithms - ESA 2014 - 22nd Annual European Symposium, Wroclaw, Poland, September 8-10, 2014, Proceedings (2014)), 455-466 · Zbl 1425.68087
[19] Farach, M.; Muthukrishnan, S., Perfect hashing for strings: formalization and algorithms, (Combinatorial Pattern Matching, 7th Annual Symposium. Combinatorial Pattern Matching, 7th Annual Symposium, CPM 96, Laguna Beach, California, USA, June 10-12, 1996, Proceedings (1996)), 130-140
[20] Harel, D.; Tarjan, R. E., Fast algorithms for finding nearest common ancestors, SIAM J. Comput., 13, 2, 338-355 (1984) · Zbl 0535.68022
[21] Sleator, D. D.; Tarjan, R. E., A data structure for dynamic trees, J. Comput. Syst. Sci., 26, 3, 362-391 (1983) · Zbl 0509.68058
[22] Abedin, P.; Ganguly, A.; Pissis, S. P.; Thankachan, S. V., Range shortest unique substring queries, (Brisaboa, N. R.; Puglisi, S. J., String Processing and Information Retrieval - 26th International Symposium. String Processing and Information Retrieval - 26th International Symposium, SPIRE 2019, Segovia, Spain, October 7-9, 2019, Proceedings. String Processing and Information Retrieval - 26th International Symposium. String Processing and Information Retrieval - 26th International Symposium, SPIRE 2019, Segovia, Spain, October 7-9, 2019, Proceedings, Lecture Notes in Computer Science, vol. 11811 (2019), Springer), 258-266
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.