{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,21]],"date-time":"2025-06-21T04:29:18Z","timestamp":1750480158201},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642237188"},{"type":"electronic","value":"9783642237195"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-23719-5_36","type":"book-chapter","created":{"date-parts":[[2011,8,30]],"date-time":"2011-08-30T09:14:33Z","timestamp":1314695673000},"page":"421-432","source":"Crossref","is-referenced-by-count":17,"title":["Pattern Matching in Lempel-Ziv Compressed Strings: Fast, Simple, and Deterministic"],"prefix":"10.1007","author":[{"given":"Pawe\u0142","family":"Gawrychowski","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"36_CR1","first-page":"705","volume-title":"SODA 1994: Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"A. Amir","year":"1994","unstructured":"Amir, A., Benson, G., Farach, M.: Let sleeping files lie: pattern matching in z-compressed files. In: SODA 1994: Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 705\u2013714. SIAM, Philadelphia (1994)"},{"key":"36_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/10719839_9","volume-title":"LATIN 2000: Theoretical Informatics","author":"M.A. Bender","year":"2000","unstructured":"Bender, M.A., Farach-Colton, M.: The lca problem revisited. In: Gonnet, G.H., Viola, A. (eds.) LATIN 2000. LNCS, vol.\u00a01776, pp. 88\u201394. Springer, Heidelberg (2000)"},{"key":"36_CR3","doi-asserted-by":"publisher","first-page":"792","DOI":"10.1145\/509907.510021","volume-title":"STOC 2002: Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing","author":"M. Charikar","year":"2002","unstructured":"Charikar, M., Lehman, E., Liu, D., Panigrahy, R., Prabhakaran, M., Rasala, A., Sahai, A., Shelat, A.: Approximating the smallest grammar: Kolmogorov complexity in natural models. In: STOC 2002: Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing, pp. 792\u2013801. ACM, New York (2002)"},{"key":"36_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1007\/3-540-61258-0_11","volume-title":"Combinatorial Pattern Matching","author":"M. Farach","year":"1996","unstructured":"Farach, M., Muthukrishnan, S.: Perfect hashing for strings: Formalization and algorithms. In: Hirschberg, D.S., Meyers, G. (eds.) CPM 1996. LNCS, vol.\u00a01075, pp. 130\u2013140. Springer, Heidelberg (1996)"},{"key":"36_CR5","doi-asserted-by":"publisher","first-page":"703","DOI":"10.1145\/225058.225288","volume-title":"STOC 1995: Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing","author":"M. Farach","year":"1995","unstructured":"Farach, M., Thorup, M.: String matching in Lempel-Ziv compressed strings. In: STOC 1995: Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, pp. 703\u2013712. ACM, New York (1995)"},{"key":"36_CR6","doi-asserted-by":"crossref","unstructured":"Gawrychowski, P.: Optimal pattern matching in LZW compressed strings. In: SODA 2011: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (2011)","DOI":"10.1137\/1.9781611973082.29"},{"key":"36_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1007\/978-3-642-14165-2_15","volume-title":"Automata, Languages and Programming","author":"J. Iacono","year":"2010","unstructured":"Iacono, J., \u00d6zkan, \u00d6.: Mergeable dictionaries. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol.\u00a06198, pp. 164\u2013175. Springer, Heidelberg (2010)"},{"issue":"6","key":"36_CR8","doi-asserted-by":"publisher","first-page":"918","DOI":"10.1145\/1217856.1217858","volume":"53","author":"J. K\u00e4rkk\u00e4inen","year":"2006","unstructured":"K\u00e4rkk\u00e4inen, J., Sanders, P., Burkhardt, S.: Linear work suffix array construction. J. ACM\u00a053(6), 918\u2013936 (2006)","journal-title":"J. ACM"},{"issue":"2","key":"36_CR9","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":"36_CR10","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/S0304-3975(02)00426-7","volume":"298","author":"T. Kida","year":"2003","unstructured":"Kida, T., Matsumoto, T., Shibata, Y., Takeda, M., Shinohara, A., Arikawa, S.: Collage system: a unifying framework for compressed pattern matching. Theor. Comput. Sci.\u00a0298, 253\u2013272 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"36_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/3-540-60692-0_60","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"S.R. Kosaraju","year":"1995","unstructured":"Kosaraju, S.R.: Pattern matching in compressed texts. In: Thiagarajan, P.S. (ed.) FSTTCS 1995. LNCS, vol.\u00a01026, pp. 349\u2013362. Springer, Heidelberg (1995)"},{"issue":"1-3","key":"36_CR12","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. Comput. Sci.\u00a0302(1-3), 211\u2013222 (2003)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"36_CR13","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/BF01206331","volume":"14","author":"E. Ukkonen","year":"1995","unstructured":"Ukkonen, E.: On-line construction of suffix trees. Algorithmica\u00a014(3), 249\u2013260 (1995)","journal-title":"Algorithmica"},{"key":"36_CR14","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1109\/SFCS.1989.63495","volume-title":"Proceedings of the 30th Annual Symposium on Foundations of Computer Science","author":"A.C.C. Yao","year":"1989","unstructured":"Yao, A.C.C.: Lower bounds for algebraic computation trees with integer inputs. In: Proceedings of the 30th Annual Symposium on Foundations of Computer Science, pp. 308\u2013313. IEEE Computer Society, Washington, DC, USA (1989)"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2011"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-23719-5_36","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,1]],"date-time":"2019-04-01T11:26:18Z","timestamp":1554117978000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-23719-5_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642237188","9783642237195"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-23719-5_36","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}