{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T03:27:39Z","timestamp":1725593259489},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642214578"},{"type":"electronic","value":"9783642214585"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-21458-5_26","type":"book-chapter","created":{"date-parts":[[2011,6,27]],"date-time":"2011-06-27T21:11:27Z","timestamp":1309209087000},"page":"299-308","source":"Crossref","is-referenced-by-count":11,"title":["Substring Range Reporting"],"prefix":"10.1007","author":[{"given":"Philip","family":"Bille","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Inge Li","family":"G\u00f8rtz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"26_CR1","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Brodal, G., Rauhe, T.: Optimal static range reporting in one dimension. In: Proc. 33rd STOC, pp. 476\u2013482 (2001)","DOI":"10.1145\/380752.380842"},{"key":"26_CR2","doi-asserted-by":"crossref","unstructured":"Alstrup, S.,St\u00f8lting Brodal, G., Rauhe, T.: New data structures for orthogonal range searching. In: Proc. 41st FOCS, pp. 198\u2013207 (2000)","DOI":"10.1109\/SFCS.2000.892088"},{"issue":"2-3","key":"26_CR3","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1016\/j.tcs.2008.01.006","volume":"395","author":"A. Amir","year":"2008","unstructured":"Amir, A., Chencinski, E., Iliopoulos, C.S., Kopelowitz, T., Zhang, H.: Property matching and weighted matching. Theoret. Comput. Sci.\u00a0395(2-3), 298\u2013310 (2008)","journal-title":"Theoret. Comput. Sci."},{"key":"26_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1007\/978-3-642-03367-4_9","volume-title":"Algorithms and Data Structures","author":"P. Bose","year":"2009","unstructured":"Bose, P., He, M., Maheshwari, A., Morin, P.: Succinct orthogonal range search structures on a grid with applications to text indexing. In: Dehne, F., Gavrilova, M., Sack, J.-R., T\u00f3th, C.D. (eds.) WADS 2009. LNCS, vol.\u00a05664, pp. 98\u2013109. Springer, Heidelberg (2009)"},{"issue":"3","key":"26_CR5","doi-asserted-by":"publisher","first-page":"703","DOI":"10.1137\/0215051","volume":"15","author":"B. Chazelle","year":"1986","unstructured":"Chazelle, B.: Filtering search: A new approach to query-answering. SIAM J. Comput.\u00a015(3), 703\u2013724 (1986)","journal-title":"SIAM J. Comput."},{"key":"26_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1044","DOI":"10.1007\/978-3-642-10631-6_105","volume-title":"Algorithms and Computation","author":"H. Cohen","year":"2009","unstructured":"Cohen, H., Porat, E.: Range non-overlapping indexing. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol.\u00a05878, pp. 1044\u20131053. Springer, Heidelberg (2009)"},{"key":"26_CR7","unstructured":"Crochemore, M., Iliopoulos, C.S., Kubica, M., Rahman, M.S., Walen, T.: Improved algorithms for the range next value problem and applications. In: Proc. 25th STACS, pp. 205\u2013216 (2008)"},{"issue":"3","key":"26_CR8","doi-asserted-by":"crossref","first-page":"173","DOI":"10.3233\/FI-2010-283","volume":"101","author":"M. Crochemore","year":"2010","unstructured":"Crochemore, M., Iliopoulos, C.S., Kubica, M., Rahman, M.S., Walen, T.: Finding patterns in given intervals. Fundam. Inform.\u00a0101(3), 173\u2013186 (2010)","journal-title":"Fundam. Inform."},{"issue":"5","key":"26_CR9","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1016\/j.ipl.2008.05.027","volume":"108","author":"M. Crochemore","year":"2008","unstructured":"Crochemore, M., Iliopoulos, C.S., Rahman, M.S.: Optimal prefix and suffix queries on texts. Inf. Process. Lett.\u00a0108(5), 320\u2013325 (2008)","journal-title":"Inf. Process. Lett."},{"key":"26_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/978-3-642-16321-0_37","volume-title":"String Processing and Information Retrieval","author":"M. Crochemore","year":"2010","unstructured":"Crochemore, M., Tischler, G.: The gapped suffix array: A new index structure for fast approximate matching. In: Chavez, E., Lonardi, S. (eds.) SPIRE 2010. LNCS, vol.\u00a06393, pp. 359\u2013364. Springer, Heidelberg (2010)"},{"issue":"6","key":"26_CR11","doi-asserted-by":"publisher","first-page":"987","DOI":"10.1145\/355541.355547","volume":"47","author":"M. Farach-Colton","year":"2000","unstructured":"Farach-Colton, M., Ferragina, P., Muthukrishnan, S.: On the sorting-complexity of suffix tree construction. J. ACM\u00a047(6), 987\u20131011 (2000)","journal-title":"J. ACM"},{"key":"26_CR12","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1145\/828.1884","volume":"31","author":"M.L. Fredman","year":"1984","unstructured":"Fredman, M.L., Koml\u00f3s, J., Szemer\u00e9di, E.: Storing a sparse table with O(1) worst case access time. J. ACM\u00a031, 538\u2013544 (1984)","journal-title":"J. ACM"},{"key":"26_CR13","doi-asserted-by":"crossref","unstructured":"Gusfield, D.: Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge (1997)","DOI":"10.1017\/CBO9780511574931"},{"issue":"6","key":"26_CR14","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/j.ipl.2007.09.004","volume":"105","author":"C.S. Iliopoulos","year":"2008","unstructured":"Iliopoulos, C.S., Rahman, M.S.: Faster index for property matching. Inf. Process. Lett.\u00a0105(6), 218\u2013223 (2008)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"26_CR15","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/s00453-007-9141-3","volume":"55","author":"C.S. Iliopoulos","year":"2009","unstructured":"Iliopoulos, C.S., Rahman, M.S.: Indexing factors with gaps. Algorithmica\u00a055(1), 60\u201370 (2009)","journal-title":"Algorithmica"},{"issue":"18","key":"26_CR16","doi-asserted-by":"publisher","first-page":"1027","DOI":"10.1016\/j.ipl.2009.06.009","volume":"109","author":"M. Juan","year":"2009","unstructured":"Juan, M., Liu, J., Wang, Y.: Errata for \u201dFaster index for property matching\u201d. Inf. Process. Lett.\u00a0109(18), 1027\u20131029 (2009)","journal-title":"Inf. Process. Lett."},{"key":"26_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"703","DOI":"10.1007\/11682462_64","volume-title":"LATIN 2006: Theoretical Informatics","author":"V. M\u00e4kinen","year":"2006","unstructured":"M\u00e4kinen, V., Navarro, G.: Position-restricted substring searching. In: Correa, J.R., Hevia, A., Kiwi, M. (eds.) LATIN 2006. LNCS, vol.\u00a03887, pp. 703\u2013714. Springer, Heidelberg (2006)"},{"issue":"3","key":"26_CR18","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. Theoret. Comput. Sci.\u00a0387(3), 332\u2013347 (2007)","journal-title":"Theoret. Comput. Sci."},{"key":"26_CR19","doi-asserted-by":"crossref","unstructured":"Mortensen, C.W., Pagh, R., P\u01cetra\u00e7cu, M.: On dynamic range reporting in one dimension. In: Proc. 37th STOC, pp. 104\u2013111 (2005)","DOI":"10.1145\/1060590.1060606"},{"key":"26_CR20","doi-asserted-by":"crossref","unstructured":"P\u01cetra\u015fcu, M., Thorup, M.: Time-space trade-offs for predecessor search. In: Proc. 38th STOC, pp. 232\u2013240 (2006)","DOI":"10.1145\/1132516.1132551"},{"key":"26_CR21","unstructured":"Porat, E.: Personal communication (2011)"},{"issue":"3","key":"26_CR22","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1016\/j.comgeo.2010.09.001","volume":"44","author":"C.-C. Yu","year":"2011","unstructured":"Yu, C.-C., Hon, W.-K., Wang, B.-F.: Improved data structures for the orthogonal range successor problem. Comput. Geometry\u00a044(3), 148\u2013159 (2011)","journal-title":"Comput. Geometry"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-21458-5_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,20]],"date-time":"2020-06-20T21:50:49Z","timestamp":1592689849000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-21458-5_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642214578","9783642214585"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-21458-5_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}