{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T00:10:12Z","timestamp":1742602212501,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540632207"},{"type":"electronic","value":"9783540692140"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-63220-4_48","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T23:19:28Z","timestamp":1330298368000},"page":"40-51","source":"Crossref","is-referenced-by-count":15,"title":["On the complexity of pattern matching for highly compressed two-dimensional texts"],"prefix":"10.1007","author":[{"given":"Piotr","family":"Berman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marek","family":"Karpinski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lawrence L.","family":"Larmore","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wojciech","family":"Plandowski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wojciech","family":"Rytter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,8]]},"reference":[{"key":"4_CR1","volume-title":"The design and analysis of computer algorithms","author":"A.V. Aho","year":"1974","unstructured":"A.V. Aho, J.E. Hopcroft, and J.D. Ullman, The design and analysis of computer algorithms, Addison-Wesley, Reading, Mass., 1974."},{"key":"4_CR2","unstructured":"A. Amir, G. Benson and M. Farach, Let sleeping files lie: pattern-matching in Z-compressed files, in SODA '94."},{"key":"4_CR3","doi-asserted-by":"crossref","unstructured":"A. Amir, G. Benson, Efficient two dimensional compressed matching, Proc. of the 2nd IEEE Data Compression Conference 279\u2013288 (1992).","DOI":"10.1109\/DCC.1992.227453"},{"key":"4_CR4","doi-asserted-by":"crossref","unstructured":"A. Amir, G. Benson and M. Farach, Optimal two-dimensional compressed matching, in ICALP'94 pp. 215\u2013225.","DOI":"10.1007\/3-540-58201-0_70"},{"key":"4_CR5","volume-title":"Text Algorithms","author":"M. Crochemore","year":"1994","unstructured":"M. Crochemore and W. Rytter, Text Algorithms, Oxford University Press, New York (1994)."},{"key":"4_CR6","doi-asserted-by":"crossref","unstructured":"M. Farach and M. Thorup, String matching in Lempel-Ziv compressed strings, in STOC'95, pp. 703\u2013712.","DOI":"10.1145\/225058.225288"},{"key":"4_CR7","unstructured":"M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman (1979)."},{"key":"4_CR8","doi-asserted-by":"crossref","unstructured":"L. Gasieniec, M. Karpi\u0144ski, W. Plandowski and W. Rytter, Efficient Algorithms for Compressed Strings. in proceedings of the SWAT'96 (1996).","DOI":"10.1007\/3-540-61422-2_148"},{"key":"4_CR9","doi-asserted-by":"crossref","unstructured":"M. Karpinski, W. Rytter and A. Shinohara, Pattern-matching for strings with short description, in Combinatorial Pattern Matching, 1995.","DOI":"10.1007\/3-540-60044-2_44"},{"key":"4_CR10","unstructured":"D. Knuth, The Art of Computing, Vol. II: Seminumerical Algorithms. Second edition. Addison-Wesley, 1981."},{"key":"4_CR11","doi-asserted-by":"crossref","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 Trans. on Inf. Theory 22, 75\u201381 (1976).","journal-title":"IEEE Trans. on Inf. Theory"},{"key":"4_CR12","doi-asserted-by":"crossref","unstructured":"A. Lempel and J. Ziv, Compression of two-dimensional images sequences, Combinatorial algorithms on words (ed. A. Apostolico, Z. Galil) Springer Verlag (1985) 141\u2013156.","DOI":"10.1007\/978-3-642-82456-2_10"},{"key":"4_CR13","doi-asserted-by":"crossref","unstructured":"R. Motwani, P. Raghavan, Randomized algorithms, Cambridge University Press 1995.","DOI":"10.1017\/CBO9780511814075"},{"key":"4_CR14","volume-title":"Computational complexity","author":"C. H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, Ch. H., Computational complexity, Addison Wesley, Reading, Massachusetts, 1994."},{"key":"4_CR15","doi-asserted-by":"crossref","unstructured":"W. Plandowski, Testing equivalence of morphisms on context-free languages, ESA'94, Lecture Notes in Computer Science 855, Springer-Verlag, 460\u2013470 (1994).","DOI":"10.1007\/BFb0049431"},{"key":"4_CR16","volume-title":"Data compression: methods and theory","author":"J. Storer","year":"1988","unstructured":"J. Storer, Data compression: methods and theory, Computer Science Press, Rockville, Maryland, 1988."},{"key":"4_CR17","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1007\/3-540-09519-5_73","volume":"72","author":"R.E. Zippel","year":"1979","unstructured":"R.E. Zippel, Probabilistic algorithms for sparse polynomials, in EUROSAM 79, Lecture Notes in Comp. Science 72, 216\u2013226 (1979).","journal-title":"Lecture Notes in Comp. Science"},{"issue":"3","key":"4_CR18","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 Inf. Theory vo. IT-23(3), 337\u2013343, 1977.","journal-title":"IEEE Trans. on 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-63220-4_48.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:40:24Z","timestamp":1742600424000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63220-4_48"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540632207","9783540692140"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-63220-4_48","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}