{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,14]],"date-time":"2025-03-14T01:10:09Z","timestamp":1741914609699,"version":"3.38.0"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2011,11,12]],"date-time":"2011-11-12T00:00:00Z","timestamp":1321056000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2013,2]]},"DOI":"10.1007\/s00453-011-9592-4","type":"journal-article","created":{"date-parts":[[2011,11,11]],"date-time":"2011-11-11T17:11:45Z","timestamp":1321031505000},"page":"354-370","source":"Crossref","is-referenced-by-count":3,"title":["A Fully Compressed Algorithm for Computing the Edit Distance of Run-Length Encoded Strings"],"prefix":"10.1007","volume":"65","author":[{"given":"Kuan-Yu","family":"Chen","sequence":"first","affiliation":[]},{"given":"Kun-Mao","family":"Chao","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,11,12]]},"reference":[{"key":"9592_CR1","doi-asserted-by":"crossref","unstructured":"Aggarwal, A., Park, J.K.: Notes on searching in multidimensional monotone arrays. FOCS, pp.\u00a0497\u2013512 (1988)","DOI":"10.1109\/SFCS.1988.21966"},{"key":"9592_CR2","doi-asserted-by":"crossref","unstructured":"Amir, A., Benson, G.: Efficient two-dimensional compressed matching. DCC, pp.\u00a0279\u2013288 (1992)","DOI":"10.1109\/DCC.1992.227453"},{"issue":"3","key":"9592_CR3","doi-asserted-by":"crossref","first-page":"1361","DOI":"10.1016\/S0304-3975(02)00041-5","volume":"290","author":"A. Amir","year":"2003","unstructured":"Amir, A., Landau, G.M., Sokol, D.: Inplace run-length 2d compressed search. Theor. Comput. Sci. 290(3), 1361\u20131383 (2003)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9592_CR4","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1006\/jcss.1996.0023","volume":"52","author":"A. Amir","year":"1996","unstructured":"Amir, A., Benson, G., Farach, M.: Let sleeping files lie: pattern-matching in Z-compressed files. J. Comput. Syst. Sci. 52(2), 299\u2013307 (1996)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"9592_CR5","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1006\/jcom.1998.0493","volume":"15","author":"A. Apostolico","year":"1999","unstructured":"Apostolico, A., Landau, G.M., Skiena, S.: Matching for run-length encoded strings. J. Complex. 15(1), 4\u201316 (1999)","journal-title":"J. Complex."},{"issue":"6","key":"9592_CR6","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1016\/S0020-0190(02)00215-6","volume":"83","author":"O. Arbell","year":"2002","unstructured":"Arbell, O., Landau, G.M., Mitchell, J.S.B.: Edit distance of run-length encoded strings. Inf. Process. Lett. 83(6), 307\u2013314 (2002)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"9592_CR7","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/0020-0190(95)00005-W","volume":"54","author":"H. Bunke","year":"1995","unstructured":"Bunke, H., Csirik, J.: An improved algorithm for computing the edit distance of run-length coded strings. Inf. Process. Lett. 54(2), 93\u201396 (1995)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"9592_CR8","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1016\/j.jco.2010.03.003","volume":"26","author":"K.-Y. Chen","year":"2010","unstructured":"Chen, K.-Y., Hsu, P.-H., Chao, K.-M.: Hardness of comparing two run-length encoded strings. J. Complex. 26(4), 364\u2013374 (2010)","journal-title":"J. Complex."},{"issue":"6","key":"9592_CR9","doi-asserted-by":"crossref","first-page":"1654","DOI":"10.1137\/S0097539702402007","volume":"32","author":"M. Crochemore","year":"2003","unstructured":"Crochemore, M., Landau, G.M., Ziv-Ukelson, M.: A subquadratic sequence alignment algorithm for unrestricted scoring matrices. SIAM J. Comput. 32(6), 1654\u20131673 (2003)","journal-title":"SIAM J. Comput."},{"key":"9592_CR10","doi-asserted-by":"crossref","unstructured":"Gasieniec, L., Rytter, W.: Almost optimal fully LZW-compressed pattern matching. DCC, pp.\u00a0316\u2013325 (1999)","DOI":"10.1109\/DCC.1999.755681"},{"issue":"4","key":"9592_CR11","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/0020-0190(86)90028-1","volume":"22","author":"H. Gajewska","year":"1986","unstructured":"Gajewska, H., Tarjan, R.E.: Deques with heap order. Inf. Process. Lett. 22(4), 197\u2013200 (1986)","journal-title":"Inf. Process. Lett."},{"key":"9592_CR12","unstructured":"Hermelin, D., Landau, G.M., Landau, S., Weimann, O.: A unified algorithm for accelerating edit-distance computation via text-compression. STACS, pp.\u00a0529\u2013540 (2009)"},{"issue":"6","key":"9592_CR13","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1145\/360825.360861","volume":"18","author":"D.S. Hirschberg","year":"1975","unstructured":"Hirschberg, D.S.: A linear space algorithm for computing maximal common subsequences. Commun. ACM 18(6), 341\u2013343 (1975)","journal-title":"Commun. ACM"},{"key":"9592_CR14","doi-asserted-by":"crossref","unstructured":"Huang, G.-S., Liu, J.J., Wang, Y.-L.: Sequence alignment algorithms for run-length-encoded strings. COCOON, pp.\u00a0319\u2013330 (2008)","DOI":"10.1007\/978-3-540-69733-6_32"},{"key":"9592_CR15","doi-asserted-by":"crossref","unstructured":"Hirao, M., Shinohara, A., Takeda, M., Arikawa, S.: Fully compressed pattern matching algorithm for balanced straight-line programs. SPIRE, pp.\u00a0132\u2013138 (2000)","DOI":"10.1109\/SPIRE.2000.878188"},{"issue":"2","key":"9592_CR16","first-page":"172","volume":"4","author":"M. Karpinski","year":"1997","unstructured":"Karpinski, M., Rytter, W., Shinohara, A.: An efficient pattern-matching algorithm for strings with short descriptions. Nord. J. Comput. 4(2), 172\u2013186 (1997)","journal-title":"Nord. J. Comput."},{"key":"9592_CR17","doi-asserted-by":"crossref","unstructured":"Kim, J.W., Amir, A., Landau, G.M., Park, K.: Similarity between compressed strings. Encyclopedia of Algorithms, pp.\u00a0843\u2013845 (2008)","DOI":"10.1007\/978-0-387-30162-4_375"},{"issue":"1","key":"9592_CR18","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/j.ipl.2007.07.006","volume":"105","author":"J.J. Liu","year":"2007","unstructured":"Liu, J.J., Huang, G.-S., Wang, Y.-L., Lee, R.C.-T.: Edit distance for a run-length-encoded string and an uncompressed string. Inf. Process. Lett. 105(1), 12\u201316 (2007)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"9592_CR19","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1016\/0022-0000(80)90002-1","volume":"20","author":"W.J. Masek","year":"1980","unstructured":"Masek, W.J., Paterson, M.: A faster algorithm computing string edit distances. J. Comput. Syst. Sci. 20(1), 18\u201331 (1980)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"9592_CR20","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1007\/s00453-002-1005-2","volume":"35","author":"V. M\u00e4kinen","year":"2003","unstructured":"M\u00e4kinen, V., Ukkonen, E., Navarro, G.: Approximate matching of run-length compressed strings. Algorithmica 35(4), 347\u2013369 (2003)","journal-title":"Algorithmica"},{"key":"9592_CR21","unstructured":"Mitchell, J.S.B.: A geometric shortest path problem, with application to computing a longest common subsequence in run-length encoded strings. Technical Report, SUNY Stony Brook (1997)"},{"issue":"4","key":"9592_CR22","doi-asserted-by":"crossref","first-page":"972","DOI":"10.1137\/S0097539795288489","volume":"27","author":"J.P. Schmidt","year":"1998","unstructured":"Schmidt, J.P.: All highest scoring paths in weighted grid graphs and their application to finding all approximate repeats in strings. SIAM J. Comput. 27(4), 972\u2013992 (1998)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9592_CR23","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1016\/0196-6774(85)90023-9","volume":"6","author":"E. Ukkonen","year":"1985","unstructured":"Ukkonen, E.: Finding approximate patterns in strings. J. Algorithms 6(1), 132\u2013137 (1985)","journal-title":"J. Algorithms"},{"issue":"1","key":"9592_CR24","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1145\/321796.321811","volume":"21","author":"R.A. Wagner","year":"1974","unstructured":"Wagner, R.A., Fischer, M.J.: The string-to-string correction problem. J. ACM 21(1), 168\u2013173 (1974)","journal-title":"J. ACM"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9592-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-011-9592-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9592-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,14]],"date-time":"2025-03-14T00:28:20Z","timestamp":1741912100000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-011-9592-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,11,12]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,2]]}},"alternative-id":["9592"],"URL":"https:\/\/doi.org\/10.1007\/s00453-011-9592-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2011,11,12]]}}}