{"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":1775281220245,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540612582","type":"print"},{"value":"9783540683902","type":"electronic"}],"license":[{"start":{"date-parts":[[1996,1,1]],"date-time":"1996-01-01T00:00:00Z","timestamp":820454400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61258-0_3","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:21:39Z","timestamp":1330291299000},"page":"39-49","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["Randomized efficient algorithms for compressed strings: the finger-print approach"],"prefix":"10.1007","author":[{"given":"Leszek","family":"Gasieniec","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marek","family":"Karpinski","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,1]]},"reference":[{"key":"3_CR1","unstructured":"A.Amir, G. Benson and M. Farach, Let sleeping files lie: pattern-matching in Z-compressed files, in SODA'94."},{"key":"3_CR2","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":"3_CR3","unstructured":"A.Amir, G. Benson and M. Farach, Optimal two-dimensional compressed matching, in ICALP'94"},{"key":"3_CR4","doi-asserted-by":"crossref","unstructured":"A. Apostolico, D. Breslauer, Z. Galil, Optimal parallel algorithms for periods, palindromes and squares, in ICALP'92, 296\u2013307","DOI":"10.1007\/3-540-55719-9_82"},{"key":"3_CR5","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":"3_CR6","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1147\/rd.312.0249","volume":"31","author":"R.M. Karp","year":"1987","unstructured":"R.M. Karp and M. Rabin, Efficient randomized pattern matching algorithms, IBM Journal of Research and Dev. 31, pp.249\u2013260 (1987).","journal-title":"IBM Journal of Research and Dev."},{"key":"3_CR7","unstructured":"M. Karpinski, W. Plandowski and W. Rytter, The fully compressed string matching for Lempel-Ziv encoding. Technical Report, Institute of Informatics, Bonn University (1995)"},{"key":"3_CR8","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":"3_CR9","unstructured":"D. Knuth, The Art of Computing, Vol. II: Seminumerical Algorithms. Second edition. Addison-Wesley (1981)."},{"key":"3_CR10","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":"3_CR11","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":"3_CR12","first-page":"8","volume":"17","author":"J. Ziv","year":"1984","unstructured":"J.Ziv and A.Lempel, A universal algorithm for sequential data compression, IEEE Trans. on Inf. Theory 17, 8\u201319, 1984","journal-title":"IEEE Trans. on Inf. Theory"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61258-0_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:14:59Z","timestamp":1742598899000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61258-0_3"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540612582","9783540683902"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/3-540-61258-0_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996]]},"assertion":[{"value":"1 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}