{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T05:40:21Z","timestamp":1775281221204,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"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_17","type":"book-chapter","created":{"date-parts":[[2007,11,13]],"date-time":"2007-11-13T19:59:14Z","timestamp":1194983954000},"page":"181-194","source":"Crossref","is-referenced-by-count":30,"title":["A Boyer\u2014Moore Type Algorithm for Compressed Pattern Matching"],"prefix":"10.1007","author":[{"given":"Yusuke","family":"Shibata","sequence":"first","affiliation":[]},{"given":"Tetsuya","family":"Matsumoto","sequence":"additional","affiliation":[]},{"given":"Masayuki","family":"Takeda","sequence":"additional","affiliation":[]},{"given":"Ayumi","family":"Shinohara","sequence":"additional","affiliation":[]},{"given":"Setsuo","family":"Arikawa","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,11,7]]},"reference":[{"issue":"6","key":"17_CR1","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1145\/360825.360855","volume":"18","author":"A. V. Aho","year":"1975","unstructured":"A. V. Aho and M. Corasick. Efficient string matching: An aid to bibliographic search. Comm. ACM, 18(6):333\u2013340, 1975.","journal-title":"Comm. ACM"},{"key":"17_CR2","unstructured":"C. Allauzen, M. Crochemore, and M. Raffinot. Factor oracle, suffix oracle. Technical Report IGM-99-08, Institut Gaspard-Monge, 1999."},{"key":"17_CR3","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. Journal of Computer and System Sciences, 52:299\u2013307, 1996.","journal-title":"Journal of Computer and System Sciences"},{"issue":"10","key":"17_CR4","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1145\/135239.135243","volume":"35","author":"R. Baeza-Yates","year":"1992","unstructured":"R. Baeza-Yates and G. H. Gonnet. A new approach to text searching. Comm. ACM, 35(10):74\u201382, 1992.","journal-title":"Comm. ACM"},{"issue":"10","key":"17_CR5","doi-asserted-by":"publisher","first-page":"62","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. Comm. ACM, 20(10):62\u201372, 1977.","journal-title":"Comm. ACM"},{"key":"17_CR6","doi-asserted-by":"crossref","unstructured":"M. Crochemore, F. Mignosi, A. Restivo, and S. Salemi. Text compression using antidictionaries. In Proc. 26th Internationial Colloquim on Automata, Languages and Programming, pages 261\u2013270. Springer-Verlag, 1999.","DOI":"10.1007\/3-540-48523-6_23"},{"key":"17_CR7","volume-title":"Text Algorithms","author":"M. Crochemore","year":"1994","unstructured":"M. Crochemore and W. Rytter. Text Algorithms. Oxford University Press, New York, 1994."},{"key":"17_CR8","doi-asserted-by":"crossref","unstructured":"E. S. de Moura, G. Navarro, N. Ziviani, and R. Baeza-Yates. Direct pattern matching on compressed text. In Proc. 5th International Symp. on String Processing and Information Retrieval, pages 90\u201395. IEEE Computer Society, 1998.","DOI":"10.1109\/SPIRE.1998.712987"},{"key":"17_CR9","unstructured":"P. Gage. A new algorithm for data compression. The C Users Journal, 12(2), 1994."},{"key":"17_CR10","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 International Symp. on String Processing and Information Retrieval, pages 89\u201396. IEEE Computer Society, 1999.","DOI":"10.1109\/SPIRE.1999.796582"},{"key":"17_CR11","doi-asserted-by":"crossref","unstructured":"T. Kida, M. Takeda, A. Shinohara, and S. Arikawa. Shift-And approach to pattern matching in LZW compressed text. In Proc. 10th Ann. Symp. on Combinatorial Pattern Matching, pages 1\u201313. Springer-Verlag, 1999.","DOI":"10.1007\/3-540-48452-3_1"},{"key":"17_CR12","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. Data Compression Conference (DCC\u201998), pages 103\u2013112. IEEE Computer Society, 1998.","DOI":"10.1109\/DCC.1998.672136"},{"issue":"2","key":"17_CR13","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"D. E. Knuth","year":"1977","unstructured":"D. E. Knuth, J. H. Morris, and V. R. Pratt. Fast pattern matching in strings. SIAM J. Comput, 6(2):323\u2013350, 1977.","journal-title":"SIAM J. Comput"},{"key":"17_CR14","doi-asserted-by":"crossref","unstructured":"U. Manber. A text compression scheme that allows fast searching directly in the compressed file. In Proc. 5th Ann. Symp. on Combinatorial Pattern Matching, pages 113\u2013124. Springer-Verlag, 1994.","DOI":"10.1007\/3-540-58094-8_10"},{"issue":"9","key":"17_CR15","first-page":"2638","volume":"39","author":"M. Miyazaki","year":"1998","unstructured":"M. Miyazaki, S. Fukamachi, M. Takeda, and T. Shinohara. Speeding up the pattern matching machine for compressed texts. Transactions of Information Processing Society of Japan, 39(9):2638\u20132648, 1998. (in Japanese).","journal-title":"Transactions of Information Processing Society of Japan"},{"key":"17_CR16","doi-asserted-by":"crossref","unstructured":"G. Navarro and M. Raffinot. A general practical approach to pattern matching over Ziv-Lempel compressed text. In Proc. 10th Ann. Symp. on Combinatorial Pattern Matching, pages 14\u201336. Springer-Verlag, 1999.","DOI":"10.1007\/3-540-48452-3_2"},{"key":"17_CR17","doi-asserted-by":"crossref","unstructured":"G. Navarro and J. Tarhio. Boyer-Moore string matching over Ziv-Lempel compressed text. In Proc. 11th Ann. Symp. on Combinatorial Pattern Matching. Springer-Verlag, 2000. to appear.","DOI":"10.1007\/3-540-45123-4_16"},{"key":"17_CR18","doi-asserted-by":"crossref","unstructured":"W. Rytter. Algorithms on compressed strings and arrays. In Proc. 26th Ann. Conf. on Current Trends in Theory and Practice of Infomatics. Springer-Verlag, 1999.","DOI":"10.1007\/3-540-47849-3_3"},{"key":"17_CR19","doi-asserted-by":"crossref","unstructured":"Y. Shibata, T. Kida, S. Fukamachi, M. Takeda, A. Shinohara, T. Shinohara, and S. Arikawa. Speeding up pattern matching by text compression. In Proc. 4th Italian Conference on Algorithms and Complexity, pages 306\u2013315. Springer-Verlag, 2000.","DOI":"10.1007\/3-540-46521-9_25"},{"key":"17_CR20","doi-asserted-by":"crossref","unstructured":"Y. Shibata, M. Takeda, A. Shinohara, and S. Arikawa. Pattern matching in text compressed by using antidictionaries. In Proc. 10th Ann. Symp. on Combinatorial Pattern Matching, pages 37\u201349. Springer-Verlag, 1999.","DOI":"10.1007\/3-540-48452-3_3"},{"issue":"6","key":"17_CR21","doi-asserted-by":"publisher","first-page":"775","DOI":"10.1016\/0306-4573(93)90106-N","volume":"29","author":"N. Uratani","year":"1993","unstructured":"N. Uratani and M. Takeda. A fast string-searching algorithm for multiple patterns. Information Processing & Management, 29(6):775\u2013791, 1993.","journal-title":"Information Processing & Management"},{"key":"17_CR22","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 Comput., 17:8\u201319, June 1984.","journal-title":"IEEE Comput."},{"key":"17_CR23","unstructured":"S. Wu and U. Manber. Agrep-a fast approximate pattern-matching tool. In Usenix Winter 1992 Technical Conference, pages 153\u2013162, 1992."},{"key":"17_CR24","doi-asserted-by":"crossref","unstructured":"S. Wu and U. Manber. Fast text searching allowing errors. Comm. ACM, 35(10):83\u201391, October 1992.","DOI":"10.1145\/135239.135244"},{"issue":"3","key":"17_CR25","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","volume":"IT-23","author":"J. Ziv","year":"1977","unstructured":"J. Ziv and A. Lempel. A universal algorithm for sequential data compression. IEEE Trans. on Inform. Theory, IT-23(3):337\u2013349, May 1977.","journal-title":"IEEE Trans. on Inform. 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_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,4]],"date-time":"2019-05-04T10:38:43Z","timestamp":1556966323000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45123-4_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540676331","9783540451235"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/3-540-45123-4_17","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2000]]}}}