{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:28:16Z","timestamp":1759638496025},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2013,1,9]],"date-time":"2013-01-09T00:00:00Z","timestamp":1357689600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2014,6]]},"DOI":"10.1007\/s00453-012-9733-4","type":"journal-article","created":{"date-parts":[[2013,1,9]],"date-time":"2013-01-09T03:51:27Z","timestamp":1357703487000},"page":"384-396","source":"Crossref","is-referenced-by-count":11,"title":["Substring Range Reporting"],"prefix":"10.1007","volume":"69","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","published-online":{"date-parts":[[2013,1,9]]},"reference":[{"key":"9733_CR1","first-page":"476","volume-title":"Proc. of the 33rd Symposium on Theory of Computing","author":"S. Alstrup","year":"2001","unstructured":"Alstrup, S., Brodal, G., Rauhe, T.: Optimal static range reporting in one dimension. In: Proc. of the 33rd Symposium on Theory of Computing, pp. 476\u2013482 (2001)"},{"key":"9733_CR2","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1109\/SFCS.2000.892088","volume-title":"Proc. of the 41st Symposium on Foundations of Computer Science","author":"S. Alstrup","year":"2000","unstructured":"Alstrup, S., St\u00f8lting\u00a0Brodal, G., Rauhe, T.: New data structures for orthogonal range searching. In: Proc. of the 41st Symposium on Foundations of Computer Science, pp. 198\u2013207 (2000)"},{"issue":"2\u20133","key":"9733_CR3","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 395(2\u20133), 298\u2013310 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"9733_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1007\/978-3-642-03367-4_9","volume-title":"Proc. of the 11th Workshop on 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: Proc. of the 11th Workshop on Algorithms and Data Structures. Lecture Notes in Computer Science, vol. 5664, pp. 98\u2013109 (2009)"},{"key":"9733_CR5","first-page":"1","volume-title":"Proc. of the 27th Symposium on Computational Geometry","author":"T.M. Chan","year":"2011","unstructured":"Chan, T.M., Larsen, K., P\u01cetra\u015fcu, M.: Orthogonal range searching on the RAM, revisited. In: Proc. of the 27th Symposium on Computational Geometry, pp. 1\u201310 (2011)"},{"issue":"3","key":"9733_CR6","doi-asserted-by":"crossref","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. 15(3), 703\u2013724 (1986)","journal-title":"SIAM J. Comput."},{"key":"9733_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1044","DOI":"10.1007\/978-3-642-10631-6_105","volume-title":"Proc. of the 20th International Symposium on Algorithms and Computation","author":"H. Cohen","year":"2009","unstructured":"Cohen, H., Porat, E.: Range non-overlapping indexing. In: Proc. of the 20th International Symposium on Algorithms and Computation. Lecture Notes in Computer Science, vol. 5878, pp. 1044\u20131053 (2009)"},{"key":"9733_CR8","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/j.tcs.2012.02.015","volume":"434","author":"M. Crochemore","year":"2012","unstructured":"Crochemore, M., Iliopoulos, C.S., Kubica, M., Rahman, M.S., Tischler, G., Walen, T.: Improved algorithms for the range next value problem and applications. Theor. Comput. Sci. 434, 23\u201334 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"9733_CR9","series-title":"Leibniz International Proceedings in Informatics","first-page":"205","volume-title":"Proc. of the 25th Symposium on Theoretical Aspects of Computer Science","author":"M. Crochemore","year":"2008","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. of the 25th Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics, vol. 1, pp. 205\u2013216 (2008)"},{"issue":"3","key":"9733_CR10","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. 101(3), 173\u2013186 (2010)","journal-title":"Fundam. Inform."},{"issue":"5","key":"9733_CR11","doi-asserted-by":"crossref","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. 108(5), 320\u2013325 (2008)","journal-title":"Inf. Process. Lett."},{"key":"9733_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1007\/978-3-642-16321-0_37","volume-title":"Proc. of the 17th Symposium on String Processing and Information Retrieval","author":"M. Crochemore","year":"2010","unstructured":"Crochemore, M., Tischler, G.: The gapped suffix array: A new index structure. In: Proc. of the 17th Symposium on String Processing and Information Retrieval. Lecture Notes in Computer Science, vol.\u00a06393, pp. 359\u2013364 (2010)"},{"issue":"6","key":"9733_CR13","doi-asserted-by":"crossref","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 47(6), 987\u20131011 (2000)","journal-title":"J. ACM"},{"key":"9733_CR14","doi-asserted-by":"crossref","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 31, 538\u2013544 (1984)","journal-title":"J. ACM"},{"key":"9733_CR15","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on strings, trees, and sequences: computer science and computational biology","author":"D. Gusfield","year":"1997","unstructured":"Gusfield, D.: Algorithms on strings, trees, and sequences: computer science and computational biology. Cambridge University Press, Cambridge (1997)"},{"issue":"1","key":"9733_CR16","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1006\/jagm.2001.1171","volume":"41","author":"T. Hagerup","year":"2001","unstructured":"Hagerup, T., Miltersen, P.B., Pagh, R.: Deterministic dictionaries. J. Algorithms 41(1), 69\u201385 (2001)","journal-title":"J. Algorithms"},{"issue":"1","key":"9733_CR17","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1016\/j.jalgor.2003.09.001","volume":"50","author":"Y. Han","year":"2004","unstructured":"Han, Y.: Deterministic sorting in O(nloglogn) time and linear space. J. Algorithms 50(1), 96\u2013105 (2004)","journal-title":"J. Algorithms"},{"issue":"6","key":"9733_CR18","doi-asserted-by":"crossref","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. 105(6), 218\u2013223 (2008)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"9733_CR19","doi-asserted-by":"crossref","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 55(1), 60\u201370 (2009)","journal-title":"Algorithmica"},{"key":"9733_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"558","DOI":"10.1007\/978-3-540-30551-4_49","volume-title":"Proc. of the 15th International Symposium on Algorithms and Computation","author":"J. J\u00e1J\u00e1","year":"2004","unstructured":"J\u00e1J\u00e1, J., Mortensen, C.W., Shi, Q.: Space-efficient and fast algorithms for multidimensional dominance reporting and counting. In: Proc. of the 15th International Symposium on Algorithms and Computation. Lecture Notes in Computer Science, vol. 3341, pp. 558\u2013568 (2004)"},{"issue":"18","key":"9733_CR21","doi-asserted-by":"crossref","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 \u201cFaster index for property matching\u201d. Inf. Process. Lett. 109(18), 1027\u20131029 (2009)","journal-title":"Inf. Process. Lett."},{"key":"9733_CR22","first-page":"703","volume-title":"Proc. of the 7th Latin American Symposium on Theoretical Informatics","author":"V. M\u00e4kinen","year":"2006","unstructured":"M\u00e4kinen, V., Navarro, G.: Position-restricted substring searching. In: Proc. of the 7th Latin American Symposium on Theoretical Informatics, pp. 703\u2013714 (2006)"},{"issue":"3","key":"9733_CR23","doi-asserted-by":"crossref","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. Comput. Sci. 387(3), 332\u2013347 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"9733_CR24","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/0020-0190(90)90022-P","volume":"35","author":"K. Mehlhorn","year":"1990","unstructured":"Mehlhorn, K., N\u00e4hler, S.: Bounded ordered dictionaries in O(loglogN) time and O(n) space. Inf. Process. Lett. 35(4), 183\u2013189 (1990)","journal-title":"Inf. Process. Lett."},{"key":"9733_CR25","first-page":"104","volume-title":"Proc. of the 37th Symposium on Theory of Computing","author":"C.W. Mortensen","year":"2005","unstructured":"Mortensen, C.W., Pagh, R., P\u01cetra\u00e7cu, M.: On dynamic range reporting in one dimension. In: Proc. of the 37th Symposium on Theory of Computing, pp. 104\u2013111 (2005)"},{"key":"9733_CR26","first-page":"40","volume-title":"Proc. of the 39th Symposium on Theory of Computing","author":"M. P\u01cetra\u015fcu","year":"2007","unstructured":"P\u01cetra\u015fcu, M.: Lower bounds for 2-dimensional range counting. In: Proc. of the 39th Symposium on Theory of Computing, pp. 40\u201346 (2007)"},{"key":"9733_CR27","first-page":"232","volume-title":"Proc. of the 38th Symposium on Theory of Computing","author":"M. P\u01cetra\u015fcu","year":"2006","unstructured":"P\u01cetra\u015fcu, M., Thorup, M.: Time-space trade-offs for predecessor search. In: Proc. of the 38th Symposium on Theory of Computing, pp. 232\u2013240 (2006)"},{"key":"9733_CR28","unstructured":"Porat, E.: Personal communication (2011)"},{"key":"9733_CR29","first-page":"649","volume-title":"Proc. of the 33rd Symposium on Theory of Computing","author":"M. Thorup","year":"2003","unstructured":"Thorup, M.: Space efficient dynamic stabbing with fast queries. In: Proc. of the 33rd Symposium on Theory of Computing, pp. 649\u2013658 (2003)"},{"issue":"3","key":"9733_CR30","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/0020-0190(77)90031-X","volume":"6","author":"P. Emde Boas van","year":"1977","unstructured":"van Emde Boas, P.: Preserving order in a forest in less than logarithmic time and linear space. Inf. Process. Lett. 6(3), 80\u201382 (1977)","journal-title":"Inf. Process. Lett."},{"key":"9733_CR31","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/BF01683268","volume":"10","author":"P. Emde Boas van","year":"1977","unstructured":"van Emde Boas, P., Kaas, R., Zijlstra, E.: Design and implementation of an efficient priority queue. Math. Syst. Theory 10, 99\u2013127 (1977)","journal-title":"Math. Syst. Theory"},{"issue":"3","key":"9733_CR32","doi-asserted-by":"crossref","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. Geom. 44(3), 148\u2013159 (2011)","journal-title":"Comput. Geom."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9733-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9733-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9733-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,20]],"date-time":"2020-07-20T02:21:26Z","timestamp":1595211686000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9733-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1,9]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,6]]}},"alternative-id":["9733"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9733-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1,9]]}}}