{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:22:57Z","timestamp":1725488577769},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424871"},{"type":"electronic","value":"9783540446699"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44669-9_15","type":"book-chapter","created":{"date-parts":[[2007,8,10]],"date-time":"2007-08-10T06:32:26Z","timestamp":1186727546000},"page":"138-149","source":"Crossref","is-referenced-by-count":1,"title":["Time\/Space Efficient Compressed Pattern Matching"],"prefix":"10.1007","author":[{"given":"Leszek","family":"Gasieniec","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Igor","family":"Potapov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,8,2]]},"reference":[{"key":"15_CR1","unstructured":"A. Amir, G. Benson, and M. Farach, Let sleeping files lie: Pattern matching in Z-compressed files, Proc. of 5th Annual ACM-SIAM Symposium on Discrete Algorithms, January 1994."},{"key":"15_CR2","unstructured":"A. Amir, G.M. Landau, and D. Sokol, Inplace Run-Length 2d Compressed Search, In Proceedings of 11th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA\u20192000, San Francisco, pp. 817\u2013818."},{"issue":"1\u20132","key":"15_CR3","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/0304-3975(95)00068-2","volume":"158","author":"D. Breslauer","year":"1996","unstructured":"D. Breslauer. Saving comparisons in the Crochemore-Perrin string matching algorithm. Theoretical Computer Science, 158(1\u20132):177\u2013192, May 1996.","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"15_CR4","doi-asserted-by":"crossref","first-page":"651","DOI":"10.1145\/116825.116845","volume":"38","author":"M. Crochemore","year":"1991","unstructured":"M. Crochemore and D. Perrin. Two-way string-matching. Journal of the ACM, 38(3):651\u2013675, July 1991.","journal-title":"Journal of the ACM"},{"key":"15_CR5","unstructured":"M. Crochemore, W. Rytter, Text algorithms, Oxford University Press, 1994."},{"key":"15_CR6","doi-asserted-by":"crossref","unstructured":"M. Farach and M. Thorup, String Matching in Lempel-Ziv Compressed Strings, Proc. 27th ACM Symposium on Theory of Computing, pp. 703\u2013713, 1994.","DOI":"10.1145\/225058.225288"},{"key":"15_CR7","doi-asserted-by":"crossref","unstructured":"P. Ferragina and G. Manzini, Opportunistic Data Structures with Applications. Proc. 41st IEEE Symposium on Foundations of Computer Science, (FOCS\u201900). Redondo Beach (CA), 2000, pp. 390\u2013398.","DOI":"10.1109\/SFCS.2000.892127"},{"issue":"3","key":"15_CR8","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1016\/0022-0000(83)90002-8","volume":"26","author":"Z. Galil","year":"1983","unstructured":"Z. Galil and J. Seiferas. Time-space-optimal string matching. Journal of Computer and System Sciences, 26(3):280\u2013294, June 1983.","journal-title":"Journal of Computer and System Sciences"},{"key":"15_CR9","doi-asserted-by":"crossref","unstructured":"L. Gcasieniec, W. Plandowski, and W. Rytter. The zooming method: a recursive approach to time-space efficient string-matching. Theoretical Computer Science, 147(1\u20132):19\u201330, August 1995","DOI":"10.1016\/0304-3975(94)00249-I"},{"key":"15_CR10","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1007\/3-540-60044-2_36","volume-title":"Proc. of 6th Combinatorial Pattern Matching","author":"L. Gcasieniec","year":"1995","unstructured":"L. Gcasieniec, W. Plandowski, and W. Rytter. Constant-space string matching with smaller number of comparisons: Sequential sampling. In Proc. of 6th Combinatorial Pattern Matching, LNCS 937, pages 78\u201389, Espoo, Finland, July 5\u20137, 1995."},{"key":"15_CR11","doi-asserted-by":"crossref","unstructured":"L. Gcasieniec and W. Rytter. Almost optimal fully compressed pattern matching. In Proceedings of Data Compression Conference (DCC\u201999), Snowbird, March 1999.","DOI":"10.1109\/DCC.1999.755681"},{"key":"15_CR12","unstructured":"J.C. Kieffer, A Survey of Advances in Hierarchical Data Compression, Technical Report, Department of Electrical & Computer Engineering, University of Minnesota, 2000."},{"key":"15_CR13","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"D. Knuth","year":"1977","unstructured":"D. Knuth, J. Morris, and V. Pratt, Fast pattern matching in strings, SIAM J. on Computing, 6 (1977), pp. 323\u2013360.","journal-title":"SIAM J. on Computing"},{"key":"15_CR14","volume-title":"Ph.D. Dissertation","author":"N.J. Larsson","year":"1999","unstructured":"N.J. Larsson, Structures of String Matching and Data Compression. Ph.D. Dissertation, Dept. of Computer Science, Lund University, Sweden, 1999."},{"key":"15_CR15","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1109\/TIT.1976.1055501","volume":"22","author":"A. Lempel","year":"1976","unstructured":"A. Lempel and J. Ziv On the complexity of finite sequences, IEEE Transactions on Information Theory, pp. 22:75\u201381, 1976.","journal-title":"IEEE Transactions on Information Theory"},{"issue":"1","key":"15_CR16","first-page":"187","volume":"1","author":"M. Miyazaki","year":"2000","unstructured":"M. Miyazaki, A. Shinohara, and M. Takeda, An Improved Pattern Matching for Strings in Terms of Straight-Line Programs, Journal of Discrete Algorithms, Vol. 1(1), pp. 187\u2013204, 2000.","journal-title":"Journal of Discrete Algorithms"},{"key":"15_CR17","unstructured":"L. Mouchard, Presentation at London Algorithms Workshop, LAW\u20192000, King\u2019s College London."},{"key":"15_CR18","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1613\/jair.374","volume":"7","author":"C. Nevill-Manning","year":"1997","unstructured":"C. Nevill-Manning and I. Witten, Identifying Hierarchical Structure in Sequences: A Linear-Time Algorithm, Journal of Artificial Intelligence, Vol. 7, pp. 67\u201382, 1997.","journal-title":"Journal of Artificial Intelligence"},{"key":"15_CR19","doi-asserted-by":"crossref","unstructured":"H. Schorr and W.M. Waite, An Efficient Machine-Independent Procedure for Garbage Collection in Various List Structure, In CACM 8(10), August 1967.","DOI":"10.1145\/363534.363554"},{"key":"15_CR20","doi-asserted-by":"crossref","unstructured":"Y. Shibata, T. Kida, S. Fukamachi, M. Takeda, A. Shinohara, T. Shinohara, Speeding up pattern matching by text compression, In Proceedings of 4th Italian Conference on Algorithms and Complexity, CIAC 2000, March 1\u20133, 2000 Rome, Italy.","DOI":"10.1007\/3-540-46521-9_25"},{"issue":"3","key":"15_CR21","doi-asserted-by":"publisher","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 Transactions on Information Theory, pp. IT-23(3):337\u2013343, 1977.","journal-title":"IEEE Transactions on Information Theory"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44669-9_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T18:12:58Z","timestamp":1556734378000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44669-9_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424871","9783540446699"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-44669-9_15","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}