{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,8]],"date-time":"2025-02-08T05:19:44Z","timestamp":1738991984400,"version":"3.37.0"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540422716"},{"type":"electronic","value":"9783540481942"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-48194-x_3","type":"book-chapter","created":{"date-parts":[[2009,2,3]],"date-time":"2009-02-03T19:24:31Z","timestamp":1233689071000},"page":"31-49","source":"Crossref","is-referenced-by-count":4,"title":["Approximate Matching of Run-Length Compressed Strings"],"prefix":"10.1007","author":[{"given":"Veli","family":"M\u00e4kinen","sequence":"first","affiliation":[]},{"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[]},{"given":"Esko","family":"Ukkonen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,6,13]]},"reference":[{"key":"3_CR1","doi-asserted-by":"crossref","unstructured":"A. Amir and G. Benson. Efficient two-dimensional compressed matching. In Proc. DCC\u201992, pages 279\u2013288, 1992.","DOI":"10.1109\/DCC.1992.227453"},{"issue":"2","key":"3_CR2","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. J. of Comp. and Sys. Sciences, 52(2):299\u2013307, 1996.","journal-title":"J. of Comp. and Sys. Sciences"},{"key":"3_CR3","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1006\/jcom.1998.0493","volume":"15","author":"A. Apostolico","year":"1999","unstructured":"A. Apostolico, G. Landau, and S. Skiena. Matching for run-length encoded strings. J. of Complexity, 15:4\u201316, 1999. (Also at Sequences\u201997, Positano Italy, June 11-13, 1997.","journal-title":"J. of Complexity"},{"key":"3_CR4","unstructured":"O. Arbell, G. Landau, and J. Mitchell. Edit distance of run-length encoded strings. Submitted for publication, August 2000."},{"key":"3_CR5","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1007\/BFb0054334","volume-title":"Proc. LATIN\u201998","author":"R. Baeza-Yates","year":"1998","unstructured":"R. Baeza-Yates and G. Navarro. Fast two-dimensional approximate pattern matching. In Proc. LATIN\u201998, LNCS 1380, pages 341\u2013351, 1998."},{"key":"3_CR6","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1007\/BF02243873","volume":"50","author":"H. Bunke","year":"1993","unstructured":"H. Bunke and J. Csirik. An algorithm for matching run-length coded strings. Computing, 50:297\u2013314, 1993.","journal-title":"Computing"},{"issue":"2","key":"3_CR7","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/0020-0190(95)00005-W","volume":"54","author":"H. Bunke","year":"1995","unstructured":"H. Bunke and J. Csirik. An improved algorithm for computing the edit distance of run-length coded strings. Information Processing Letters, 54(2):93\u201396, 1995.","journal-title":"Information Processing Letters"},{"key":"3_CR8","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1007\/PL00009202","volume":"20","author":"M. Farach","year":"1998","unstructured":"M. Farach and M. Thorup. String matching in Lempel-Ziv compressed texts. Algorithmica, 20:388\u2013404, 1998.","journal-title":"Algorithmica"},{"key":"3_CR9","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. SPIRE\u201999, pages 89\u201396. IEEE CS Press, 1999.","DOI":"10.1109\/SPIRE.1999.796582"},{"key":"3_CR10","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. DCC\u201998, pages 103\u2013112, 1998.","DOI":"10.1109\/DCC.1998.672136"},{"key":"3_CR11","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/3-540-45123-4_18","volume-title":"Proc. CPM\u20192000","author":"J. K\u00e4rkk\u00e4inen","year":"2000","unstructured":"J. K\u00e4rkk\u00e4inen, G. Navarro, and E. Ukkonen. Approximate string matching over Ziv-Lempel compressed text. In Proc. CPM\u20192000, LNCS 1848, pages 195\u2013209, 2000."},{"key":"3_CR12","first-page":"707","volume":"6","author":"V. Levenshtein","year":"1966","unstructured":"V. Levenshtein. Binary codes capable of correcting deletions, insertions and reversals. Soviet Physics Doklady 6:707\u2013710, 1966.","journal-title":"Soviet Physics Doklady"},{"key":"3_CR13","doi-asserted-by":"crossref","unstructured":"T. Matsumoto, T. Kida, M. Takeda, A. Shinohara, and S. Arikawa. Bit-parallel approach to approximate string matching. In Proc. SPIRE\u20192000, IEEE CS Press, pages 221\u2013228, 2000.","DOI":"10.1109\/SPIRE.2000.878198"},{"key":"3_CR14","unstructured":"J. Mitchell. A geometric shortest path problem, with application to computing a longest common subsequence in run-length encoded strings. In Technical Report, Dept. of Applied Mathematics, SUNY Stony Brook, 1997."},{"key":"3_CR15","doi-asserted-by":"crossref","unstructured":"G. Navarro, T. Kida, M. Takeda, A. Shinohara, and S. Arikawa. Faster Approximate String Matching over Compressed Text. In Proc. 11th IEEE Data Compression Conference (DCC\u201901), 2001, To appear.","DOI":"10.1109\/DCC.2001.917177"},{"issue":"4","key":"3_CR16","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1016\/0196-6774(80)90016-4","volume":"1","author":"P. Sellers","year":"1980","unstructured":"P. Sellers. The theory and computation of evolutionary distances: Pattern recognition. J. of Algorithms, 1(4):359\u2013373, 1980.","journal-title":"J. of Algorithms"},{"issue":"1-3","key":"3_CR17","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1016\/S0019-9958(85)80046-2","volume":"64","author":"E. Ukkonen","year":"1985","unstructured":"E. Ukkonen. Algorithms for approximate string matching. Information and Control 64(1-3):100\u2013118, 1985.","journal-title":"Information and Control"},{"issue":"1-3","key":"3_CR18","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1016\/0196-6774(85)90023-9","volume":"6","author":"E. Ukkonen","year":"1985","unstructured":"E. Ukkonen. Finding approximate patterns in strings. J. of Algorithms 6(1-3): 132\u2013137, 1985.","journal-title":"J. of Algorithms"},{"issue":"1","key":"3_CR19","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1145\/321796.321811","volume":"21","author":"R. Wagner","year":"1974","unstructured":"R. Wagner and M. Fisher. The string-to-string correction problem. J. of the ACM 21(1):168\u2013173, 1974.","journal-title":"J. of the ACM"},{"key":"3_CR20","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","volume":"23","author":"J. Ziv","year":"1977","unstructured":"J. Ziv and A. Lempel. A universal algorithm for sequential data compression. IEEE Trans. Inf. Theory, 23:337\u2013343, 1977.","journal-title":"IEEE Trans. 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-48194-X_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,7]],"date-time":"2025-02-07T10:55:54Z","timestamp":1738925754000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48194-X_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540422716","9783540481942"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-48194-x_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2001]]}}}