{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T05:40:20Z","timestamp":1775281220771,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540676331","type":"print"},{"value":"9783540451235","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-45123-4_16","type":"book-chapter","created":{"date-parts":[[2007,11,13]],"date-time":"2007-11-13T19:59:14Z","timestamp":1194983954000},"page":"166-180","source":"Crossref","is-referenced-by-count":28,"title":["Boyer\u2014Moore String Matching over Ziv-Lempel Compressed Text"],"prefix":"10.1007","author":[{"given":"Gonzalo","family":"Navarro","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jorma","family":"Tarhio","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,11,7]]},"reference":[{"key":"16_CR1","doi-asserted-by":"crossref","unstructured":"A. Amir and G. Benson. Efficient two-dimensional compressed matching. In Proc. DCC\u201992, pages 279\u2013288, 1992.","DOI":"10.1109\/DCC.1992.227453"},{"issue":"2","key":"16_CR2","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1006\/jcss.1996.0023","volume":"52","author":"A. Amir","year":"1996","unstructured":"A. Amir, G. Benson, and M. Farach. Let sleeping files lie: Pattern matching in Z-compressed files. J. of and Sys. Sciences, 52(2):299\u2013307, 1996.","journal-title":"J. of and Sys. Sciences"},{"key":"16_CR3","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780195113679.001.0001","volume-title":"Pattern Matching Algorithms","author":"A. Apostolico","year":"1997","unstructured":"A. Apostolico and Z. Galil. Pattern Matching Algorithms. Oxford University Press, Oxford, UK, 1997."},{"key":"16_CR4","unstructured":"T. Bell, J. Cleary, and I. Witten. Text Compression. Prentice Hall, 1990."},{"issue":"10","key":"16_CR5","doi-asserted-by":"crossref","first-page":"762","DOI":"10.1145\/359842.359859","volume":"20","author":"R. S. Boyer","year":"1977","unstructured":"R. S. Boyer and J. S. Moore. A fast string searching algorithm. CACM, 20(10):762\u2013772, 1977.","journal-title":"CACM"},{"key":"16_CR6","unstructured":"M. Crochemore and W. Rytter. Text Algorithms. Oxford University Press, 1994."},{"key":"16_CR7","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1007\/PL00009202","volume":"20","author":"M. Farach","year":"1998","unstructured":"M. Farach and M. Thorup. String matching in Lempel-Ziv compressed strings. Algorithmica, 20:388\u2013404, 1998.","journal-title":"Algorithmica"},{"key":"16_CR8","doi-asserted-by":"crossref","unstructured":"L. Gasieniec, M. Karpinksi, W. Plandowski, and W. Rytter. Efficient algorithms for Lempel-Ziv encodings. In Proc. SWAT\u201996, 1996.","DOI":"10.1007\/3-540-61422-2_148"},{"key":"16_CR9","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1002\/spe.4380100608","volume":"10","author":"R. N. Horspool","year":"1980","unstructured":"R. N. Horspool. Practical fast searching in strings. Software Practice and Experience, 10:501\u2013506, 1980.","journal-title":"Software Practice and Experience"},{"issue":"9","key":"16_CR10","doi-asserted-by":"crossref","first-page":"1090","DOI":"10.1109\/JRPROC.1952.273898","volume":"40","author":"D. Huffman","year":"1952","unstructured":"D. Huffman. A method for the construction of minimum-redundancy codes. Proc. of the I.R.E., 40(9):1090\u20131101, 1952.","journal-title":"Proc. of the I.R.E."},{"key":"16_CR11","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/3-540-45123-4_18","volume-title":"Proc. CPM\u20192000","author":"J. K\u00e4rkk\u00e4inen","year":"2000","unstructured":"J. K\u00e4rkk\u00e4inen, G. Navarro, and E. Ukkonen. Approximate string matching over ziv-lempel compressed text. In Proc. CPM\u20192000, LNCS1848, 2000, pp. 195\u2013209."},{"key":"16_CR12","doi-asserted-by":"crossref","unstructured":"T. Kida, Y. Shibata, M. Takeda, A. Shinohara, and S. Arikawa. A unifying framework for compressed pattern matching. In Proc. 6th Intl. Symp. on String Processing and Information Retrieval (SPIRE\u201999), pages 89\u201396. IEEE CS Press, 1999.","DOI":"10.1109\/SPIRE.1999.796582"},{"key":"16_CR13","doi-asserted-by":"crossref","unstructured":"T. Kida, M. Takeda, A. Shinohara, M. Miyazaki, and S. Arikawa. Multiple pattern matching in LZW compressed text. In Proc. DCC\u201998, 1998.","DOI":"10.1109\/DCC.1998.672136"},{"key":"16_CR14","series-title":"Lect Notes Comput Sci","first-page":"1","volume-title":"Proc. CPM\u201999","author":"T. Kida","year":"1999","unstructured":"T. Kida, M. Takeda, A. Shinohara, M. Miyazaki, and S. Arikawa. Shift-And approach to pattern matching in LZW compressed text. In Proc. CPM\u201999, LNCS 1645, pages 1\u201313, 1999."},{"issue":"2","key":"16_CR15","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1145\/248625.248639","volume":"15","author":"U. Manber","year":"1997","unstructured":"U. Manber. A text compression scheme that allows fast searching directly in the compressed file. ACM Trans. on Information Systems, 15(2):124\u2013136, 1997.","journal-title":"ACM Trans. on Information Systems"},{"key":"16_CR16","unstructured":"E. Moura, G. Navarro, N. Ziviani, and R. Baeza-Yates. Fast and flexible word searching on compressed text. ACM Trans. on Information Systems, 2000. To appear. Previous versions in SIGIR\u201998 and SPIRE\u201998."},{"key":"16_CR17","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1007\/3-540-48452-3_2","volume-title":"Proc. CPM\u201999","author":"G. Navarro","year":"1999","unstructured":"G. Navarro and M. Raffinot. A general practical approach to pattern matching over Ziv-Lempel compressed text. In Proc. CPM\u201999, LNCS 1645, pages 14\u201336, 1999."},{"issue":"7","key":"16_CR18","doi-asserted-by":"publisher","first-page":"851","DOI":"10.1002\/(SICI)1097-024X(199707)27:7<851::AID-SPE108>3.0.CO;2-D","volume":"27","author":"H. Peltola","year":"1997","unstructured":"H. Peltola and J. Tarhio. String matching in the DNA alphabet. Software Practice and Experience, 27(7):851\u2013861, 1997.","journal-title":"Software Practice and Experience"},{"issue":"8","key":"16_CR19","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1145\/79173.79184","volume":"33","author":"D. Sunday","year":"1990","unstructured":"D. Sunday. A very fast substring search algorithm. CACM, 33(8):132\u2013142, 1990.","journal-title":"CACM"},{"issue":"6","key":"16_CR20","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1109\/MC.1984.1659158","volume":"17","author":"T. A. Welch","year":"1984","unstructured":"T. A. Welch. A technique for high performance data compression. IEEE Computer Magazine, 17(6):8\u201319, June 1984.","journal-title":"IEEE Computer Magazine"},{"key":"16_CR21","doi-asserted-by":"crossref","unstructured":"S. Wu and U. Manber. Fast text searching allowing errors. Comm. of the ACM, 35(10):83\u201391, October 1992.","DOI":"10.1145\/135239.135244"},{"key":"16_CR22","unstructured":"S. Wu and U. Manber. Agrep-a fast approximate pattern-matching tool. In Proc. USENIX Technical Conference, pages 153\u2013162, Berkeley, CA, USA, Winter 1992."},{"key":"16_CR23","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","volume":"23","author":"J. Ziv","year":"1977","unstructured":"J. Ziv and A. Lempel. A universal algorithm for sequential data compression. IEEE Trans. Inf. Theory, 23:337\u2013343, 1977.","journal-title":"IEEE Trans. Inf. Theory"},{"key":"16_CR24","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1109\/TIT.1978.1055934","volume":"24","author":"J. Ziv","year":"1978","unstructured":"J. Ziv and A. Lempel. Compression of individual sequences via variable length coding. IEEE Trans. Inf. Theory, 24:530\u2013536, 1978.","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45123-4_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,27]],"date-time":"2021-08-27T12:50:26Z","timestamp":1630068626000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45123-4_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540676331","9783540451235"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/3-540-45123-4_16","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2000]]}}}