{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T04:02:29Z","timestamp":1746244949459,"version":"3.40.4"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642544224"},{"type":"electronic","value":"9783642544231"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-642-54423-1_63","type":"book-chapter","created":{"date-parts":[[2014,3,25]],"date-time":"2014-03-25T03:02:27Z","timestamp":1395716547000},"page":"731-742","source":"Crossref","is-referenced-by-count":38,"title":["LZ77-Based Self-indexing with Faster Pattern Matching"],"prefix":"10.1007","author":[{"given":"Travis","family":"Gagie","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pawe\u0142","family":"Gawrychowski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Juha","family":"K\u00e4rkk\u00e4inen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yakov","family":"Nekrich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Simon J.","family":"Puglisi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"63_CR1","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Brodal, G., Rauhe, T.: Optimal static range reporting in one dimension. In: Proc. STOC, pp. 476\u2013482 (2001)","DOI":"10.1145\/380752.380842"},{"key":"63_CR2","unstructured":"Alstrup, S., Brodal, G.S., Rauhe, T.: Pattern matching in dynamic texts. In: Proc. SODA, pp. 819\u2013828 (2000)"},{"issue":"1-2","key":"63_CR3","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\u00a062(1-2), 54\u2013101 (2012)","journal-title":"Algorithmica"},{"key":"63_CR4","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., Boldi, P., Pagh, R., Vigna, S.: Monotone minimal perfect hashing: searching a sorted table with $\\mathcal{O}({1})$ accesses. In: Proc. SODA, pp. 785\u2013794 (2009)","DOI":"10.1137\/1.9781611973068.86"},{"key":"63_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/978-3-642-21458-5_26","volume-title":"Combinatorial Pattern Matching","author":"P. Bille","year":"2011","unstructured":"Bille, P., G\u00f8rtz, I.L.: Substring range reporting. In: Giancarlo, R., Manzini, G. (eds.) CPM 2011. LNCS, vol.\u00a06661, pp. 299\u2013308. Springer, Heidelberg (2011)"},{"key":"63_CR6","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Larsen, K.G., P\u01cetra\u015fcu, M.: Orthogonal range searching on the RAM, revisited. In: Proc. SoCG, pp. 1\u201310 (2011)","DOI":"10.1145\/1998196.1998198"},{"issue":"3","key":"63_CR7","first-page":"313","volume":"111","author":"F. Claude","year":"2011","unstructured":"Claude, F., Navarro, G.: Self-indexed grammar-based compression. Fund. Inf.\u00a0111(3), 313\u2013337 (2011)","journal-title":"Fund. Inf."},{"key":"63_CR8","unstructured":"Do, H.H., Jansson, J., Sadakane, K., Sung, W.-K.: Fast relative Lempel-Ziv self-index for similar sequences. Theor. Comp. Sci. (to appear)"},{"issue":"7","key":"63_CR9","doi-asserted-by":"publisher","first-page":"2554","DOI":"10.1109\/TIT.2005.850116","volume":"51","author":"M. Charikar","year":"2005","unstructured":"Charikar, M., et al.: The smallest grammar problem. IEEE Trans. Inf. Theory\u00a051(7), 2554\u20132576 (2005)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"63_CR10","doi-asserted-by":"crossref","unstructured":"Bille, P., et al.: Random access to grammar-compressed strings. In: Proc. SODA, pp. 373\u2013389 (2011)","DOI":"10.1137\/1.9781611973082.30"},{"key":"63_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1007\/978-3-642-40104-6_13","volume-title":"Algorithms and Data Structures","author":"P. Bille","year":"2013","unstructured":"Bille, P., Cording, P.H., G\u00f8rtz, I.L., Sach, B., Vildh\u00f8j, H.W., Vind, S.: Fingerprints in compressed strings. In: Dehne, F., Solis-Oba, R., Sack, J.-R. (eds.) WADS 2013. LNCS, vol.\u00a08037, pp. 146\u2013157. Springer, Heidelberg (2013)"},{"key":"63_CR12","doi-asserted-by":"crossref","unstructured":"Farach, M., Thorup, M.: String matching in Lempel-Ziv compressed strings. In: Proc. STOC, pp. 703\u2013712 (1995)","DOI":"10.1145\/225058.225288"},{"key":"63_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1007\/978-3-642-28332-1_21","volume-title":"Language and Automata Theory and Applications","author":"T. Gagie","year":"2012","unstructured":"Gagie, T., Gawrychowski, P., K\u00e4rkk\u00e4inen, J., Nekrich, Y., Puglisi, S.J.: A faster grammar-based self-index. In: Dediu, A.-H., Mart\u00edn-Vide, C. (eds.) LATA 2012. LNCS, vol.\u00a07183, pp. 240\u2013251. Springer, Heidelberg (2012)"},{"key":"63_CR14","doi-asserted-by":"crossref","unstructured":"Gagie, T., Gawrychowski, P., K\u00e4rkk\u00e4inen, J., Nekrich, Y., Puglisi, S.J.: A faster grammar-based self-index. Technical Report 1109.3954v6, arxiv.org (2012)","DOI":"10.1007\/978-3-642-28332-1_21"},{"key":"63_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/978-3-642-14355-7_19","volume-title":"Algorithmic Aspects in Information and Management","author":"S. Huang","year":"2010","unstructured":"Huang, S., Lam, T.W., Sung, W.K., Tam, S.L., Yiu, S.M.: Indexing similar DNA sequences. In: Chen, B. (ed.) AAIM 2010. LNCS, vol.\u00a06124, pp. 180\u2013190. Springer, Heidelberg (2010)"},{"key":"63_CR16","unstructured":"K\u00e4rkk\u00e4inen, J., Ukkonen, E.: Lempel-Ziv parsing and sublinear-size index structures for string matching. In: Proc. WSP, pp. 141\u2013155 (1996)"},{"key":"63_CR17","doi-asserted-by":"crossref","unstructured":"Karp, R.M., Miller, R.E., Rosenberg, A.L.: Rapid identification of repeated patters in strings, trees and arrays. In: Proc. STOC, pp. 125\u2013136 (1972)","DOI":"10.1145\/800152.804905"},{"issue":"2","key":"63_CR18","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1147\/rd.312.0249","volume":"31","author":"R.M. Karp","year":"1987","unstructured":"Karp, R.M., Rabin, M.O.: Efficient randomized pattern-matching algorithms. IBM J. Res. Dev.\u00a031(2), 249\u2013260 (1987)","journal-title":"IBM J. Res. Dev."},{"key":"63_CR19","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. Comp. Sci.\u00a0483, 115\u2013133 (2013)","journal-title":"Theor. Comp. Sci."},{"issue":"3","key":"63_CR20","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. Comp. Bio.\u00a017(3), 281\u2013308 (2010)","journal-title":"J. Comp. Bio."},{"key":"63_CR21","first-page":"100","volume":"18","author":"S. Maruyama","year":"2013","unstructured":"Maruyama, S., Nakahara, M., Kishiue, N., Sakamoto, H.: ESP-index: A compressed index based on edit-sensitive parsing. J. Dis. Alg.\u00a018, 100\u2013112 (2013)","journal-title":"J. Dis. Alg."},{"issue":"4","key":"63_CR22","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1145\/321479.321481","volume":"15","author":"D.R. Morrison","year":"1968","unstructured":"Morrison, D.R.: PATRICIA - Practical algorithm to retrieve information coded in alphanumeric. J. ACM\u00a015(4), 514\u2013534 (1968)","journal-title":"J. ACM"},{"key":"63_CR23","doi-asserted-by":"crossref","unstructured":"Mortensen, C.W., Pagh, R., P\u01cetra\u015fcu, M.: On dynamic range reporting in one dimension. In: Proc. STOC, pp. 104\u2013111 (2005)","DOI":"10.1145\/1060590.1060606"},{"key":"63_CR24","doi-asserted-by":"crossref","unstructured":"Navarro, G., M\u00e4kinen, V.: Compressed full-text indexes. ACM Comp. Surv.\u00a039(1) (2007)","DOI":"10.1145\/1216370.1216372"},{"issue":"4","key":"63_CR25","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/s10791-008-9050-3","volume":"11","author":"L.M.S. Russo","year":"2008","unstructured":"Russo, L.M.S., Oliveira, A.L.: A compressed self-index using a Ziv-Lempel dictionary. Inf. Retr.\u00a011(4), 359\u2013388 (2008)","journal-title":"Inf. Retr."},{"issue":"1-3","key":"63_CR26","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/S0304-3975(02)00777-6","volume":"302","author":"W. Rytter","year":"2003","unstructured":"Rytter, W.: Application of Lempel-Ziv factorization to the approximation of grammar-based compression. Theor. Comp. Sci.\u00a0302(1-3), 211\u2013222 (2003)","journal-title":"Theor. Comp. Sci."},{"key":"63_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/978-3-642-38905-4_24","volume-title":"Combinatorial Pattern Matching","author":"E. Verbin","year":"2013","unstructured":"Verbin, E., Yu, W.: Data structure lower bounds on random access to grammar-compressed strings. In: Fischer, J., Sanders, P. (eds.) CPM 2013. LNCS, vol.\u00a07922, pp. 247\u2013258. Springer, Heidelberg (2013)"},{"key":"63_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1007\/978-3-642-40683-6_20","volume-title":"Advances in Databases and Information Systems","author":"S. Wandelt","year":"2013","unstructured":"Wandelt, S., Leser, U.: QGramProjector: Q-gram projection for indexing highly-similar strings. In: Catania, B., Guerrini, G., Pokorn\u00fd, J. (eds.) ADBIS 2013. LNCS, vol.\u00a08133, pp. 260\u2013273. Springer, Heidelberg (2013)"},{"key":"63_CR29","doi-asserted-by":"crossref","unstructured":"Yang, X., Wang, B., Li, C., Wang, J., Xie, X.: Efficient direct search on genomic data. In: Proc. ICDE, pp. 961\u2013972 (2013)","DOI":"10.1109\/ICDE.2013.6544889"},{"issue":"3","key":"63_CR30","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. Inf. Theory\u00a023(3), 337\u2013343 (1977)","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Lecture Notes in Computer Science","LATIN 2014: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-54423-1_63","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,2]],"date-time":"2025-05-02T04:23:08Z","timestamp":1746159788000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-54423-1_63"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783642544224","9783642544231"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-54423-1_63","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}