{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,4]],"date-time":"2025-05-04T04:03:28Z","timestamp":1746331408212,"version":"3.40.4"},"publisher-location":"Cham","reference-count":34,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319079585"},{"type":"electronic","value":"9783319079592"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-07959-2_37","type":"book-chapter","created":{"date-parts":[[2014,6,10]],"date-time":"2014-06-10T16:44:25Z","timestamp":1402418665000},"page":"436-447","source":"Crossref","is-referenced-by-count":0,"title":["Improved and Extended Locating Functionality on Compressed Suffix Arrays"],"prefix":"10.1007","author":[{"given":"Simon","family":"Gog","sequence":"first","affiliation":[]},{"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"37_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"748","DOI":"10.1007\/978-3-642-23719-5_63","volume-title":"Algorithms \u2013 ESA 2011","author":"D. Belazzougui","year":"2011","unstructured":"Belazzougui, D., Navarro, G.: Alphabet-independent compressed text indexing. In: Demetrescu, C., Halld\u00f3rsson, M.M. (eds.) ESA 2011. LNCS, vol.\u00a06942, pp. 748\u2013759. Springer, Heidelberg (2011)"},{"key":"37_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/978-3-642-21458-5_26","volume-title":"Combinatorial Pattern Matching","author":"P. Bille","year":"2011","unstructured":"Bille, P., G\u00f8rtz, I.L.: Substring range reporting. In: Giancarlo, R., Manzini, G. (eds.) CPM 2011. LNCS, vol.\u00a06661, pp. 299\u2013308. Springer, Heidelberg (2011)"},{"unstructured":"Burrows, M., Wheeler, D.: A block sorting lossless data compression algorithm. Technical Report 124, Digital Equipment Corporation (1994)","key":"37_CR3"},{"doi-asserted-by":"crossref","unstructured":"Ferragina, P., Gonz\u00e1lez, R., Navarro, G., Venturini, R.: Compressed text indexes: From theory to practice. ACM J. Exp. Alg.\u00a013, article 12 (2009)","key":"37_CR4","DOI":"10.1145\/1412228.1455268"},{"doi-asserted-by":"crossref","unstructured":"Ferragina, P., Manzini, G.: Opportunistic data structures with applications. In: Proc. FOCS, pp. 390\u2013398 (2000)","key":"37_CR5","DOI":"10.1109\/SFCS.2000.892127"},{"issue":"4","key":"37_CR6","doi-asserted-by":"publisher","first-page":"552","DOI":"10.1145\/1082036.1082039","volume":"52","author":"P. Ferragina","year":"2005","unstructured":"Ferragina, P., Manzini, G.: Indexing compressed texts. J. ACM\u00a052(4), 552\u2013581 (2005)","journal-title":"J. ACM"},{"doi-asserted-by":"crossref","unstructured":"Ferragina, P., Manzini, G., M\u00e4kinen, V., Navarro, G.: Compressed representations of sequences and full-text indexes. ACM Trans. Alg.\u00a03(2), article 20 (2007)","key":"37_CR7","DOI":"10.1145\/1240233.1240243"},{"issue":"4","key":"37_CR8","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1007\/s00453-013-9782-3","volume":"67","author":"P. Ferragina","year":"2013","unstructured":"Ferragina, P., Sir\u00e9n, J., Venturini, R.: Distribution-aware compressed full-text indexes. Algorithmica\u00a067(4), 529\u2013546 (2013)","journal-title":"Algorithmica"},{"issue":"2","key":"37_CR9","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1137\/090779759","volume":"40","author":"J. Fischer","year":"2011","unstructured":"Fischer, J., Heun, V.: Space-efficient preprocessing schemes for range minimum queries on static arrays. SIAM J. Comp.\u00a040(2), 465\u2013492 (2011)","journal-title":"SIAM J. Comp."},{"issue":"51","key":"37_CR10","doi-asserted-by":"publisher","first-page":"5354","DOI":"10.1016\/j.tcs.2009.09.012","volume":"410","author":"J. Fischer","year":"2009","unstructured":"Fischer, J., M\u00e4kinen, V., Navarro, G.: Faster entropy-bounded compressed suffix trees. Theor. Comp. Sci.\u00a0410(51), 5354\u20135364 (2009)","journal-title":"Theor. Comp. Sci."},{"doi-asserted-by":"crossref","unstructured":"Gog, S., Petri, M.: Optimized succinct data structures for massive data. In: Soft. Prac. & Exp. (2013) (to appear), http:\/\/dx.doi.org\/10.1002\/spe.2198","key":"37_CR11","DOI":"10.1002\/spe.2198"},{"unstructured":"Gonnet, G., Baeza-Yates, R., Snider, T.: New indices for text: Pat trees and Pat arrays. In: Information Retrieval: Data Structures and Algorithms, ch. 3, pp. 66\u201382. Prentice-Hall (1992)","key":"37_CR12"},{"unstructured":"Grossi, R., Gupta, A., Vitter, J.S.: High-order entropy-compressed text indexes. In: Proc. SODA, pp. 636\u2013645 (2003)","key":"37_CR13"},{"doi-asserted-by":"crossref","unstructured":"Grossi, R., Vitter, J.: Compressed suffix arrays and suffix trees with applications to text indexing and string matching. In: Proc. STOC, pp. 397\u2013406 (2000)","key":"37_CR14","DOI":"10.1145\/335305.335351"},{"issue":"2","key":"37_CR15","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1137\/S0097539702402354","volume":"35","author":"R. Grossi","year":"2006","unstructured":"Grossi, R., Vitter, J.: Compressed suffix arrays and suffix trees with applications to text indexing and string matching. SIAM J. Comp.\u00a035(2), 378\u2013407 (2006)","journal-title":"SIAM J. Comp."},{"key":"37_CR16","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/j.jda.2012.09.002","volume":"17","author":"W.-K. Hon","year":"2012","unstructured":"Hon, W.-K., Shah, R., Thankachan, S., Vitter, J.: On position restricted substring searching in succinct space. J. Discr. Alg.\u00a017, 109\u2013114 (2012)","journal-title":"J. Discr. Alg."},{"issue":"6","key":"37_CR17","doi-asserted-by":"publisher","first-page":"918","DOI":"10.1145\/1217856.1217858","volume":"53","author":"J. K\u00e4rkk\u00e4inen","year":"2006","unstructured":"K\u00e4rkk\u00e4inen, J., Sanders, P., Burkhardt, S.: Linear work suffix array construction. J. ACM\u00a053(6), 918\u2013936 (2006)","journal-title":"J. ACM"},{"issue":"2-4","key":"37_CR18","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1016\/j.jda.2004.08.019","volume":"3","author":"D. Kim","year":"2005","unstructured":"Kim, D., Sim, J., Park, H., Park, K.: Constructing suffix arrays in linear time. J. Discr. Alg.\u00a03(2-4), 126\u2013142 (2005)","journal-title":"J. Discr. Alg."},{"issue":"2-4","key":"37_CR19","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/j.jda.2004.08.002","volume":"3","author":"P. Ko","year":"2005","unstructured":"Ko, P., Aluru, S.: Space efficient linear time construction of suffix arrays. J. Discr. Alg.\u00a03(2-4), 143\u2013156 (2005)","journal-title":"J. Discr. Alg."},{"issue":"3","key":"37_CR20","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1016\/j.tcs.2007.07.013","volume":"387","author":"V. M\u00e4kinen","year":"2007","unstructured":"M\u00e4kinen, V., Navarro, G.: Rank and select revisited and extended. Theor. Comp. Sci.\u00a0387(3), 332\u2013347 (2007)","journal-title":"Theor. Comp. Sci."},{"issue":"5","key":"37_CR21","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U. Manber","year":"1993","unstructured":"Manber, U., Myers, G.: Suffix arrays: a new method for on-line string searches. SIAM J. Comp.\u00a022(5), 935\u2013948 (1993)","journal-title":"SIAM J. Comp."},{"issue":"3","key":"37_CR22","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1145\/382780.382782","volume":"48","author":"G. Manzini","year":"2001","unstructured":"Manzini, G.: An analysis of the Burrows-Wheeler transform. J. ACM\u00a048(3), 407\u2013430 (2001)","journal-title":"J. ACM"},{"key":"37_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/3-540-45061-0_29","volume-title":"Automata, Languages and Programming","author":"J. Munro","year":"2003","unstructured":"Munro, J., Raman, R., Raman, V., Rao, S.: Succinct representations of permutations. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 345\u2013356. Springer, Heidelberg (2003)"},{"unstructured":"Muthukrishnan, S.: Efficient algorithms for document retrieval problems. In: Proc. SODA, pp. 657\u2013666 (2002)","key":"37_CR24"},{"doi-asserted-by":"crossref","unstructured":"Navarro, G., M\u00e4kinen, V.: Compressed full-text indexes. ACM Comp. Surv.\u00a039(1), article 2 (2007)","key":"37_CR25","DOI":"10.1145\/1216370.1216372"},{"key":"37_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/978-3-642-31155-0_24","volume-title":"Algorithm Theory \u2013 SWAT 2012","author":"Y. Nekrich","year":"2012","unstructured":"Nekrich, Y., Navarro, G.: Sorted range reporting. In: Fomin, F.V., Kaski, P. (eds.) SWAT 2012. LNCS, vol.\u00a07357, pp. 271\u2013282. Springer, Heidelberg (2012)"},{"doi-asserted-by":"crossref","unstructured":"Okanohara, D., Sadakane, K.: Practical entropy-compressed rank\/select dictionary. In: Proceedings of the Workshop on Algorithm Engineering and Experiments. SIAM (2007)","key":"37_CR27","DOI":"10.1137\/1.9781611972870.6"},{"doi-asserted-by":"crossref","unstructured":"Raman, R., Raman, V., Rao, S.S.: Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Trans. Alg.\u00a03(4), article 43 (2007)","key":"37_CR28","DOI":"10.1145\/1290672.1290680"},{"issue":"6","key":"37_CR29","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1016\/S0020-0190(01)00298-8","volume":"82","author":"S. Rao","year":"2002","unstructured":"Rao, S.: Time-space trade-offs for compressed suffix arrays. Inf. Proc. Lett.\u00a082(6), 307\u2013311 (2002)","journal-title":"Inf. Proc. Lett."},{"key":"37_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1007\/3-540-40996-3_35","volume-title":"Algorithms and Computation","author":"K. Sadakane","year":"2000","unstructured":"Sadakane, K.: Compressed text databases with efficient query algorithms based on the compressed suffix array. In: Lee, D.T., Teng, S.-H. (eds.) ISAAC 2000. LNCS, vol.\u00a01969, pp. 410\u2013421. Springer, Heidelberg (2000)"},{"issue":"2","key":"37_CR31","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1016\/S0196-6774(03)00087-7","volume":"48","author":"K. Sadakane","year":"2003","unstructured":"Sadakane, K.: New text indexing functionalities of the compressed suffix arrays. J. Alg.\u00a048(2), 294\u2013313 (2003)","journal-title":"J. Alg."},{"issue":"4","key":"37_CR32","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1007\/s00224-006-1198-x","volume":"41","author":"K. Sadakane","year":"2007","unstructured":"Sadakane, K.: Compressed suffix trees with full functionality. Theor. Comp. Sys.\u00a041(4), 589\u2013607 (2007)","journal-title":"Theor. Comp. Sys."},{"issue":"1","key":"37_CR33","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/j.jda.2006.03.011","volume":"5","author":"K. Sadakane","year":"2007","unstructured":"Sadakane, K.: Succinct data structures for flexible text retrieval systems. J. Disc. Alg.\u00a05(1), 12\u201322 (2007)","journal-title":"J. Disc. Alg."},{"doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear pattern matching algorithm. In: Proc. 14th IEEE Symposium on Switching and Automata Theory, pp. 1\u201311 (1973)","key":"37_CR34","DOI":"10.1109\/SWAT.1973.13"}],"container-title":["Lecture Notes in Computer Science","Experimental Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-07959-2_37","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T09:04:20Z","timestamp":1746263060000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-07959-2_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319079585","9783319079592"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-07959-2_37","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}