A Linear Space Data Structure for Range LCP Queries

• Autorzy: Ganguly A. , Shah R. , Patil M. , Thankachan S. V.

Identyfikatory

DOI

10.3233/FI-2018-1741

• Języki publikacji: EN

Abstrakty

EN

Range LCP (longest common prefix) is an extension of the classical LCP problem and is defined as follows: Preprocess a string S[1...n] of n characters, such that whenever an interval [i; j] comes as a query, we can report max{LCP(S_p,S_q) i ≤ p < q ≤ j} Here LCP((S_p, S_q) is the longest common prefix of the suffixes of S starting at locations p and q, and LCP((S_p,S_q)) is its length. This problem was first addressed by Amir et al. [ISAAC, 2011]. They showed that the query can be answered in O(log log n) time using an O(n log ^1+ε n) space data structure for an arbitrarily small constant ε > 0. In an attempt to reduce the space bound, they presented a linear space data structure of O(d log log n) query time, where d = (j - i + 1). In this paper, we present a new linear space data structure with an improved query time of O[formula].

Słowa kluczowe

EN

string algorithms; suffix tree; range query

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2018
• Tom: Vol. 163, nr 3
• Strony: 245--251
• Opis fizyczny: Bibliogr. 15 poz.

Twórcy

autor

Ganguly A.

• Department of Computer Science, University of Wisconsin-Whitewater, USA

autor

Shah R.

• Department of Computer Science, Louisiana State University, USA

autor

Patil M.

• Facebook, Inc., Menlo Park, California, USA

autor

Thankachan S. V.

• Department of Computer Science, University of Central Florida, USA

Bibliografia

• [1] Abedin P, Ganguly A, Hon W, Nekrich Y, Sadakane K, Shah R, Thankachan SV. A Linear-Space Data Structure for Range-LCP Queries in Poly-Logarithmic Time, Computing and Combinatorics - 24th International Conference, COCOON 2018, Qing Dao, China, July 2-4, 2018, Proceedings, 2018 pp. 615-625. doi:10.1007/978-3-319-94776-1_51.
• [2] Amir A, Apostolico A, Landau GM, Levy A, Lewenstein M, Porat E. Range LCP, Journal of Computer and System Sciences, 2014;80(7):1245-1253. URL https://doi.org/10.1016/j.jcss.2014.02.010.
• [3] Amir A, Lewenstein M, Thankachan SV. Range LCP queries revisited, International Symposium on String Processing and Information Retrieval, vol 9309 Springer, 2015 pp. 350-361. doi:10.1007/978-3-319-23826-5_33.
• [4] Bender MA, Farach-Colton M. The LCA Problem Revisited, LATIN 2000: Theoretical Informatics, 4th Latin American Symposium, Punta del Este, Uruguay, April 10-14, 2000, Proceedings, 2000 pp. 88-94. doi:10.1007/10719839_9.
• [5] Cohen H, Porat E. Fast set intersection and two-patterns matching, Theoretical Computer Science, 2010;411(40-42):3795-3800. URL https://doi.org/10.1016/j.tcs.2010.06.002.
• [6] Cormode G, Muthukrishnan S. Substring compression problems, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, Society for Industrial and Applied Mathematics, 2005 pp.321-330. ISBN-0-89871-585-7.
• [7] Gagie T, Karhu K, Navarro G, Puglisi SJ, Sirén J. Document listing on repetitive collections, Annual Symposium on Combinatorial Pattern Matching, vol 7922 Springer, 2013 pp. 107-119. doi:10.1007/978-3-642-38905-4_12.
• [8] Gusfield D. Algorithms on strings, trees and sequences: computer science and computational biology, Cambridge university press, 1997.
• [9] Keller O, Kopelowitz T, Feibish SL, Lewenstein M. Generalized substring compression, Theoretical Computer Science, 2014;525:42-54. URL https://doi.org/10.1016/j.tcs.2013.10.010.
• [10] Lenhof HP, Smid MHM. Using Persistent Data Structures for Adding Range Restrictions to Searching Problems, ITA, 1994;28(1):25-49.
• [11] Lewenstein M. Orthogonal range searching for text indexing, in: Space-Efficient Data Structures, Streams, and Algorithms, Springer, 2013 pp. 267-302. doi:10.1007/978-3-642-40273-9_18.
• [12] Nekrich Y, Navarro G. Sorted Range Reporting, SWAT, vol 7357. Springer, Berlin 2012 pp. 271-282. doi:10.1007/978-3-642-31155-0_24.
• [13] Patil M, Shah R, Thankachan SV. Faster range LCP queries, International Symposium on String Processing and Information Retrieval, vol 8214 Springer, 2013 pp. 263-270. doi:10.1007/978-3-319-02432-5_29.
• [14] Raman R, Raman V, Satti SR. Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets, ACM Transactions on Algorithms (TALG), 2007;3(4): 43. doi:10.1145/1290672.1290680.
• [15] Weiner P. Linear Pattern Matching Algorithms, SWAT, 1973 pp. 1-11. doi:10.1109/SWAT.1973.13.