{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T14:59:30Z","timestamp":1787497170573,"version":"build-2736575974"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319238258","type":"print"},{"value":"9783319238265","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-23826-5_33","type":"book-chapter","created":{"date-parts":[[2015,9,4]],"date-time":"2015-09-04T04:20:20Z","timestamp":1441340420000},"page":"350-361","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Range LCP Queries Revisited"],"prefix":"10.1007","author":[{"given":"Amihood","family":"Amir","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Moshe","family":"Lewenstein","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sharma V.","family":"Thankachan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2015,9,5]]},"reference":[{"issue":"7","key":"33_CR1","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. Comp. and Sys. Sci. 80(7), 1245\u20131253 (2014)","journal-title":"J. Comp. and Sys. Sci."},{"key":"33_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/978-3-642-33090-2_20","volume-title":"Algorithms \u2013 ESA 2012","author":"GS Brodal","year":"2012","unstructured":"Brodal, G.S., Davoodi, P., Lewenstein, M., Raman, R., Srinivasa Rao, S.: Two Dimensional Range Minimum Queries and Fibonacci Lattices. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol. 7501, pp. 217\u2013228. Springer, Heidelberg (2012)"},{"key":"33_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/978-3-642-15781-3_15","volume-title":"Algorithms \u2013 ESA 2010","author":"GS Brodal","year":"2010","unstructured":"Brodal, G.S., Davoodi, P., Rao, S.S.: On Space Efficient Two Dimensional Range Minimum Data Structures. In: de Berg, M., Meyer, U. (eds.) ESA 2010, Part II. LNCS, vol. 6347, pp. 171\u2013182. Springer, Heidelberg (2010)"},{"issue":"40\u201342","key":"33_CR4","doi-asserted-by":"publisher","first-page":"3795","DOI":"10.1016\/j.tcs.2010.06.002","volume":"411","author":"H Cohen","year":"2010","unstructured":"Cohen, H., Porat, E.: Fast set intersection and two-patterns matching. Theor. Comput. Sci. 411(40\u201342), 3795\u20133800 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"33_CR5","doi-asserted-by":"crossref","unstructured":"Cole, R., Gottlieb, L., Lewenstein, M.: Dictionary matching and indexing with errors and don\u2019t cares. In: Proc. 36th Annual ACM Symposium on the Theory of Computing (STOC), pp. 91\u2013100. ACM Press (2004)","DOI":"10.1145\/1007352.1007374"},{"key":"33_CR6","unstructured":"Cormode, G., Muthukrishnan, S.: Substring compression problems. In: Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 321\u2013330 (2005)"},{"issue":"2","key":"33_CR7","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1007\/BF01293666","volume":"14","author":"P Dietz","year":"1995","unstructured":"Dietz, P., Mehlhorn, K., Raman, R., Uhrig, C.: Lower bounds for set intersection queries. Algorithmica 14(2), 154\u2013168 (1995)","journal-title":"Algorithmica"},{"issue":"4","key":"33_CR8","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1145\/8307.8309","volume":"17","author":"Z Galil","year":"1986","unstructured":"Galil, Z., Giancarlo, R.: Improved string matching with $$k$$ mismatches. SIGACT News 17(4), 52\u201354 (1986)","journal-title":"SIGACT News"},{"key":"33_CR9","first-page":"338","volume":"13","author":"D Harel","year":"1984","unstructured":"Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestor. Computer and System Science 13, 338\u2013355 (1984)","journal-title":"Computer and System Science"},{"key":"33_CR10","doi-asserted-by":"crossref","unstructured":"K\u00e4rkk\u00e4inen, J., Sanders, P.: Simple linear work suffix array construction. In: Baeten, J.C.M. et al., (eds.): ICALP 2003. LNCS, vol. 2719, pp. 943\u2013955. Springer, Heidelberg (2003)","DOI":"10.1007\/3-540-45061-0_73"},{"key":"33_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/3-540-48194-X_17","volume-title":"Combinatorial Pattern Matching","author":"T Kasai","year":"2001","unstructured":"Kasai, T., Lee, G.H., Arimura, H., Arikawa, S., Park, K.: Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications. In: Amir, A., Landau, G.M. (eds.) CPM 2001. LNCS, vol. 2089, pp. 181\u2013192. Springer, Heidelberg (2001)"},{"key":"33_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.: Shir Landau Feibish, and Moshe Lewenstein, Generalized substring compression. Theor. Comput. Sci. 525, 42\u201354 (2014)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"33_CR13","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0196-6774(89)90010-2","volume":"10","author":"GM Landau","year":"1989","unstructured":"Landau, G.M., Vishkin, U.: Fast parallel and serial approximate string matching. Journal of Algorithms 10(2), 157\u2013169 (1989)","journal-title":"Journal of Algorithms"},{"key":"33_CR14","doi-asserted-by":"crossref","unstructured":"Landau, G.M., Vishkin, U.: Efficient string matching in the presence of errors. In: Proc. 26th IEEE FOCS, pp. 126\u2013126 (1985)","DOI":"10.1109\/SFCS.1985.22"},{"key":"33_CR15","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1109\/TIT.1976.1055501","volume":"22","author":"A Lempel","year":"1976","unstructured":"Lempel, A., Ziv, J.: On the complexity of finite sequences. IEEE Transactions on Information Theory 22, 75\u201381 (1976)","journal-title":"IEEE Transactions on Information Theory"},{"key":"33_CR16","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.) Ianfest-66. LNCS, vol. 8066, pp. 267\u2013302. Springer, Heidelberg (2013)"},{"key":"33_CR17","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/978-1-61779-582-4_12","volume":"855","author":"W Makalowski","year":"2012","unstructured":"Makalowski, W., Pande, A., Gotea, V., Makalowska, I.: Transposable elements and their identification. Methods Mol. Biol. 855, 337\u2013359 (2012)","journal-title":"Methods Mol. Biol."},{"issue":"6","key":"33_CR18","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1073\/pnas.36.6.344","volume":"36","author":"B McClintock","year":"1950","unstructured":"McClintock, B.: The origin and behavior of multiple loci in maize. Proc. Natl. Acad. Sci. 36(6), 344\u2013355 (1950)","journal-title":"Proc. Natl. Acad. Sci."},{"key":"33_CR19","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, Heidelberg (2013)"},{"key":"33_CR20","doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear pattern matching algorithm. In: Proc. 14 IEEE Symposium on Switching and Automata Theory, 1\u201311 (1973)","DOI":"10.1109\/SWAT.1973.13"},{"key":"33_CR21","unstructured":"Yellin, D.: Data structures for set equality-testing. In: Proc. 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 386\u2013392 (1992)"},{"key":"33_CR22","doi-asserted-by":"crossref","unstructured":"Yuan, H., Atallah, M.J.: Data structures for range minimum queries in multidimensional arrays. In: Proc. 21st ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 150\u2013160 (2010)","DOI":"10.1137\/1.9781611973075.14"}],"container-title":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-23826-5_33","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,20]],"date-time":"2023-01-20T15:00:41Z","timestamp":1674226841000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-23826-5_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319238258","9783319238265"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-23826-5_33","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"5 September 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}