{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:24:16Z","timestamp":1759638256197,"version":"3.41.0"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319947754"},{"type":"electronic","value":"9783319947761"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-94776-1_51","type":"book-chapter","created":{"date-parts":[[2018,6,29]],"date-time":"2018-06-29T01:48:06Z","timestamp":1530236886000},"page":"615-625","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A Linear-Space Data Structure for Range-LCP Queries in Poly-Logarithmic Time"],"prefix":"10.1007","author":[{"given":"Paniz","family":"Abedin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arnab","family":"Ganguly","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wing-Kai","family":"Hon","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yakov","family":"Nekrich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kunihiko","family":"Sadakane","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rahul","family":"Shah","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sharma V.","family":"Thankachan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,6,29]]},"reference":[{"key":"51_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"683","DOI":"10.1007\/978-3-642-25591-5_70","volume-title":"Algorithms and Computation","author":"A Amir","year":"2011","unstructured":"Amir, A., Apostolico, A., Landau, G.M., Levy, A., Lewenstein, M., Porat, E.: Range LCP. In: Asano, T., Nakano, S., Okamoto, Y., Watanabe, O. (eds.) ISAAC 2011. LNCS, vol. 7074, pp. 683\u2013692. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-25591-5_70"},{"issue":"7","key":"51_CR2","doi-asserted-by":"publisher","first-page":"1245","DOI":"10.1016\/j.jcss.2014.02.010","volume":"80","author":"A Amir","year":"2014","unstructured":"Amir, A., Apostolico, A., Landau, G.M., Levy, A., Lewenstein, M., Porat, E.: Range LCP. J. Comput. Syst. Sci. 80(7), 1245\u20131253 (2014)","journal-title":"J. Comput. Syst. Sci."},{"key":"51_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1007\/978-3-319-23826-5_33","volume-title":"String Processing and Information Retrieval","author":"A Amir","year":"2015","unstructured":"Amir, A., Lewenstein, M., Thankachan, S.V.: Range LCP queries revisited. In: Iliopoulos, C., Puglisi, S., Yilmaz, E. (eds.) SPIRE 2015. LNCS, vol. 9309, pp. 350\u2013361. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-23826-5_33"},{"key":"51_CR4","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Larsen, K.G., Patrascu, M.: Orthogonal range searching on the RAM, revisited. In: Symposium on Computational Geometry, pp. 1\u201310 (2011)","DOI":"10.1145\/1998196.1998198"},{"issue":"3","key":"51_CR5","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1137\/0217026","volume":"17","author":"B Chazelle","year":"1988","unstructured":"Chazelle, B.: A functional approach to data structures and its use in multidimensional searching. SIAM J. Comput. 17(3), 427\u2013462 (1988)","journal-title":"SIAM J. Comput."},{"key":"51_CR6","unstructured":"Cormode, G., Muthukrishnan, S.: Substring compression problems. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 321\u2013330. Society for Industrial and Applied Mathematics (2005)"},{"key":"51_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1007\/3-540-61258-0_11","volume-title":"Combinatorial Pattern Matching","author":"M Farach","year":"1996","unstructured":"Farach, M., Muthukrishnan, S.: Perfect hashing for strings: formalization and algorithms. In: Hirschberg, D., Myers, G. (eds.) CPM 1996. LNCS, vol. 1075, pp. 130\u2013140. Springer, Heidelberg (1996). https:\/\/doi.org\/10.1007\/3-540-61258-0_11"},{"issue":"2","key":"51_CR8","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. Comput. 40(2), 465\u2013492 (2011)","journal-title":"SIAM J. Comput."},{"key":"51_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/978-3-642-38905-4_12","volume-title":"Combinatorial Pattern Matching","author":"T Gagie","year":"2013","unstructured":"Gagie, T., Karhu, K., Navarro, G., Puglisi, S.J., Sir\u00e9n, J.: Document listing on repetitive collections. In: Fischer, J., Sanders, P. (eds.) CPM 2013. LNCS, vol. 7922, pp. 107\u2013119. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-38905-4_12"},{"key":"51_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1007\/978-3-662-44777-2_38","volume-title":"Algorithms - ESA 2014","author":"P Gawrychowski","year":"2014","unstructured":"Gawrychowski, P., Lewenstein, M., Nicholson, P.K.: Weighted ancestors in suffix trees. In: Schulz, A.S., Wagner, D. (eds.) ESA 2014. LNCS, vol. 8737, pp. 455\u2013466. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-44777-2_38"},{"issue":"2","key":"51_CR11","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D Harel","year":"1984","unstructured":"Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestors. SIAM J. Comput. 13(2), 338\u2013355 (1984)","journal-title":"SIAM J. Comput."},{"key":"51_CR12","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/j.tcs.2013.10.010","volume":"525","author":"O Keller","year":"2014","unstructured":"Keller, O., Kopelowitz, T., Feibish, S.L., Lewenstein, M.: Generalized substring compression. Theor. Comput. Sci. 525, 42\u201354 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"51_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/978-3-642-40273-9_18","volume-title":"Space-Efficient Data Structures, Streams, and Algorithms","author":"M Lewenstein","year":"2013","unstructured":"Lewenstein, M.: Orthogonal range searching for text indexing. In: Brodnik, A., L\u00f3pez-Ortiz, A., Raman, V., Viola, A. (eds.) Space-Efficient Data Structures, Streams, and Algorithms. LNCS, vol. 8066, pp. 267\u2013302. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40273-9_18"},{"key":"51_CR14","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. 7357, pp. 271\u2013282. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-31155-0_24"},{"key":"51_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/978-3-319-02432-5_29","volume-title":"String Processing and Information Retrieval","author":"M Patil","year":"2013","unstructured":"Patil, M., Shah, R., Thankachan, S.V.: Faster range LCP queries. In: Kurland, O., Lewenstein, M., Porat, E. (eds.) SPIRE 2013. LNCS, vol. 8214, pp. 263\u2013270. Springer, Cham (2013). https:\/\/doi.org\/10.1007\/978-3-319-02432-5_29"},{"key":"51_CR16","doi-asserted-by":"crossref","unstructured":"Patil, M., Thankachan, S.V., Shah, R., Nekrich, Y., Vitter, J.S.: Categorical range maxima queries. In: Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2014, 22\u201327 June 2014, Snowbird, UT, USA, pp. 266\u2013277 (2014)","DOI":"10.1145\/2594538.2594557"},{"key":"51_CR17","doi-asserted-by":"crossref","unstructured":"Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. In: Proceedings of the 13th Annual ACM Symposium on Theory of Computing, 11\u201313 May 1981, Milwaukee, Wisconsin, USA, pp. 114\u2013122 (1981)","DOI":"10.1145\/800076.802464"},{"key":"51_CR18","doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear pattern matching algorithms. In: SWAT, pp. 1\u201311 (1973)","DOI":"10.1109\/SWAT.1973.13"},{"issue":"2","key":"51_CR19","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0020-0190(83)90075-3","volume":"17","author":"DE Willard","year":"1983","unstructured":"Willard, D.E.: Log-logarithmic worst-case range queries are possible in space theta(n). Inf. Process. Lett. 17(2), 81\u201384 (1983)","journal-title":"Inf. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-94776-1_51","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,5]],"date-time":"2025-07-05T12:12:17Z","timestamp":1751717537000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-94776-1_51"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319947754","9783319947761"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-94776-1_51","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"29 June 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOON","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computing and Combinatorics Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Qing Dao","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 July 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 July 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/cocoon2018.sdu.edu.cn\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}