{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T20:15:26Z","timestamp":1776802526587,"version":"3.51.2"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319199283","type":"print"},{"value":"9783319199290","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":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-19929-0_3","type":"book-chapter","created":{"date-parts":[[2015,6,15]],"date-time":"2015-06-15T13:09:49Z","timestamp":1434373789000},"page":"26-39","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":39,"title":["Composite Repetition-Aware Data Structures"],"prefix":"10.1007","author":[{"given":"Djamal","family":"Belazzougui","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fabio","family":"Cunial","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Travis","family":"Gagie","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicola","family":"Prezza","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mathieu","family":"Raffinot","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,16]]},"reference":[{"issue":"1\u20132","key":"3_CR1","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1007\/s00453-010-9443-8","volume":"62","author":"D Arroyuelo","year":"2012","unstructured":"Arroyuelo, D., Navarro, G., Sadakane, K.: Stronger Lempel-Ziv based compressed text indexing. Algorithmica 62(1\u20132), 54\u2013101 (2012)","journal-title":"Algorithmica"},{"key":"3_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/978-3-642-40450-4_12","volume-title":"Algorithms \u2013 ESA 2013","author":"D Belazzougui","year":"2013","unstructured":"Belazzougui, D., Cunial, F., K\u00e4rkk\u00e4inen, J., M\u00e4kinen, V.: Versatile succinct representations of the bidirectional burrows-wheeler transform. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol. 8125, pp. 133\u2013144. Springer, Heidelberg (2013)"},{"issue":"3","key":"3_CR3","doi-asserted-by":"publisher","first-page":"578","DOI":"10.1145\/28869.28873","volume":"34","author":"A Blumer","year":"1987","unstructured":"Blumer, A., Blumer, J., Haussler, D., McConnell, R., Ehrenfeucht, A.: Complete inverted files for efficient text retrieval and analysis. J. ACM 34(3), 578\u2013595 (1987)","journal-title":"J. ACM"},{"key":"3_CR4","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Larsen, K.G., P\u0103tra\u015fcu, M.: Orthogonal range searching on the RAM, revisited. In: Proceedings of SoCG, pp. 1\u201310 (2011)","DOI":"10.1145\/1998196.1998198"},{"key":"3_CR5","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/978-3-662-07675-0_9","volume-title":"Handbook of Formal Languages","author":"M Crochemore","year":"1997","unstructured":"Crochemore, M., Hancart, C.: Automata for matching patterns. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 2, pp. 399\u2013462. Springer, Heidelberg (1997)"},{"key":"3_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1007\/3-540-63220-4_55","volume-title":"Combinatorial Pattern Matching","author":"M Crochemore","year":"1997","unstructured":"Crochemore, M., V\u00e9rin, R.: Direct construction of compact directed acyclic word graphs. In: Apostolico, A., Hein, J. (eds.) Proceedings of CPM. LNCS, vol. 1264, pp. 116\u2013129. Springer, Heidelberg (1997)"},{"issue":"4","key":"3_CR7","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 text. J. ACM 52(4), 552\u2013581 (2005)","journal-title":"J. ACM"},{"key":"3_CR8","unstructured":"P. Ferragina and G. Navarro. Pizza&Chili repetitive corpus. http:\/\/pizzachili.dcc.uchile.cl\/repcorpus.html. Accessed on 25 January 2015"},{"key":"3_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"731","DOI":"10.1007\/978-3-642-54423-1_63","volume-title":"LATIN 2014: Theoretical Informatics","author":"T Gagie","year":"2014","unstructured":"Gagie, T., Gawrychowski, P., K\u00e4rkk\u00e4inen, J., Nekrich, Y., Puglisi, S.J.: LZ77-based self-indexing with faster pattern matching. In: Pardo, A., Viola, A. (eds.) LATIN 2014. LNCS, vol. 8392, pp. 731\u2013742. Springer, Heidelberg (2014)"},{"key":"3_CR10","unstructured":"K\u00e4rkk\u00e4inen, J., Ukkonen, E.: Lempel-Ziv parsing and sublinear-size index structures for string matching. In: Proceedings of WSP, pp. 141\u2013155 (1996)"},{"key":"3_CR11","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.tcs.2012.02.006","volume":"483","author":"S Kreft","year":"2013","unstructured":"Kreft, S., Navarro, G.: On compressing and indexing repetitive sequences. Theor. Comput. Sci. 483, 115\u2013133 (2013)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"3_CR12","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 Trans. Info. Theory 22(1), 75\u201381 (1976)","journal-title":"IEEE Trans. Info. Theory"},{"key":"3_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/11496656_5","volume-title":"Combinatorial Pattern Matching","author":"V M\u00e4kinen","year":"2005","unstructured":"M\u00e4kinen, V., Navarro, G.: Succinct suffix arrays based on run-length encoding. In: Apostolico, A., Crochemore, M., Park, K. (eds.) CPM 2005. LNCS, vol. 3537, pp. 45\u201356. Springer, Heidelberg (2005)"},{"issue":"3","key":"3_CR14","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1089\/cmb.2009.0169","volume":"17","author":"V M\u00e4kinen","year":"2010","unstructured":"M\u00e4kinen, V., Navarro, G., Sir\u00e9n, J., V\u00e4lim\u00e4ki, N.: Storage and retrieval of highly repetitive sequence collections. J. Comput. Biol. 17(3), 281\u2013308 (2010)","journal-title":"J. Comput. Biol."},{"key":"3_CR15","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.jda.2011.01.001","volume":"11","author":"J Radoszewski","year":"2012","unstructured":"Radoszewski, J., Rytter, W.: On the structure of compacted subword graphs of ThueMorse words and their applications. J. Discret. Algorithms 11, 15\u201324 (2012)","journal-title":"J. Discret. Algorithms"},{"issue":"3","key":"3_CR16","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/S0020-0190(01)00152-1","volume":"80","author":"M Raffinot","year":"2001","unstructured":"Raffinot, M.: On maximal repeats in strings. Inform. Process. Lett. 80(3), 165\u2013169 (2001)","journal-title":"Inform. Process. Lett."},{"issue":"2","key":"3_CR17","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/j.tcs.2006.07.025","volume":"363","author":"W Rytter","year":"2006","unstructured":"Rytter, W.: The structure of subword graphs and suffix trees of Fibonacci words. Theoret. Comput. Sci. 363(2), 211\u2013223 (2006)","journal-title":"Theoret. Comput. Sci."},{"key":"3_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1007\/978-3-540-89097-3_17","volume-title":"String Processing and Information Retrieval","author":"J Sir\u00e9n","year":"2008","unstructured":"Sir\u00e9n, J., V\u00e4lim\u00e4ki, N., M\u00e4kinen, V., Navarro, G.: Run-length compressed indexes are superior for highly repetitive sequence collections. In: Amir, A., Turpin, A., Moffat, A. (eds.) SPIRE 2008. LNCS, vol. 5280, pp. 164\u2013175. Springer, Heidelberg (2008)"},{"issue":"2","key":"3_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)$$. Inform. Process. Lett. 17(2), 81\u201384 (1983)","journal-title":"Inform. Process. Lett."},{"issue":"3","key":"3_CR20","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","volume":"23","author":"J Ziv","year":"1977","unstructured":"Ziv, J., Lempel, A.: A universal algorithm for sequential data compression. IEEE Trans. Info. Theory 23(3), 337\u2013343 (1977)","journal-title":"IEEE Trans. Info. Theory"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-19929-0_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,1]],"date-time":"2023-02-01T17:21:30Z","timestamp":1675272090000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-19929-0_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319199283","9783319199290"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-19929-0_3","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":"16 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}