{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,11]],"date-time":"2026-11-11T00:33:13Z","timestamp":1794357193562,"version":"4.9.0"},"publisher-location":"Boston, MA","reference-count":14,"publisher":"Springer US","isbn-type":[{"value":"9780387307701","type":"print"},{"value":"9780387301624","type":"electronic"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-0-387-30162-4_122","type":"book-chapter","created":{"date-parts":[[2008,6,26]],"date-time":"2008-06-26T14:36:25Z","timestamp":1214490985000},"page":"265-267","source":"Crossref","is-referenced-by-count":4,"title":["Edit Distance Under Block Operations"],"prefix":"10.1007","author":[{"given":"S. Cenk","family":"Sahinalp","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"2","key":"122_CR1_122","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1137\/S089548019528280X","volume":"11","author":"V. Bafna","year":"1998","unstructured":"Bafna, V., Pevzner, P.A.: Sorting by Transpositions. SIAM J.\u00a0Discret. Math. 11(2), 224\u2013240 (1998)","journal-title":"SIAM J. Discret. Math."},{"key":"122_CR2_122","doi-asserted-by":"crossref","unstructured":"Batu, T., Erg\u00fcn, F., Sahinalp, S.C.: Oblivious string embeddings and edit distance approximations. Proc. ACM-SIAM SODA 792\u2013801 (2006)","DOI":"10.1145\/1109557.1109644"},{"issue":"1\u20132","key":"122_CR3_122","first-page":"7","volume":"76","author":"S. Besmaphyatnikh","year":"2000","unstructured":"Besmaphyatnikh, S., Segal, M.: Enumerating longest increasing subsequences and patience sorting. Inform. Proc. Lett. 76(1\u20132), 7\u201311 (2000)","journal-title":"Inform. Proc. Lett."},{"key":"122_CR4_122","unstructured":"Cormode, G., Muthukrishnan, S.: The string edit distance matching problem with moves. Proc. ACM-SIAM SODA 667\u2013676 (2002)"},{"key":"122_CR5_122","unstructured":"Cormode, G., Paterson, M., Sahinalp, S.C., Vishkin, U.: Communication complexity of document exchange. Proc. ACM-SIAM SODA 197\u2013206 (2000)"},{"key":"122_CR6_122","doi-asserted-by":"crossref","unstructured":"Indyk, P., Motwani, R.: Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. Proc. ACM STOC 604\u2013613 (1998)","DOI":"10.1145\/276698.276876"},{"issue":"1","key":"122_CR7_122","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.ipl.2004.09.012","volume":"93","author":"H. Kaplan","year":"2005","unstructured":"Kaplan, H., Shafrir, N.: The greedy algorithm for shortest superstrings. Inform. Proc. Lett. 93(1), 13\u201317 (2005)","journal-title":"Inform. Proc. Lett."},{"key":"122_CR8_122","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0196-6774(89)90010-2","volume":"10","author":"G. Landau","year":"1989","unstructured":"Landau, G., Vishkin, U.: Fast parallel and serial approximate string matching. J.\u00a0Algorithms 10, 157\u2013169 (1989)","journal-title":"J. Algorithms"},{"key":"122_CR9_122","unstructured":"Levenshtein, V.I.: Binary codes capable of correcting deletions, insertions, and reversals. Doklady Akademii Nauk SSSR 163(4):845\u2013848 (1965) (Russian). Soviet Physics Doklady 10(8), 707\u2013710 (1966) (English translation)"},{"issue":"1","key":"122_CR10_122","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0304-3975(96)00268-X","volume":"181","author":"D.P. Lopresti","year":"1997","unstructured":"Lopresti, D.P., Tomkins, A.: Block Edit Models for Approximate String Matching. Theoretical. Comput. Sci. 181(1), 159\u2013179 (1997)","journal-title":"Theoretical. Comput. Sci."},{"key":"122_CR11_122","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/0022-0000(80)90002-1","volume":"20","author":"W. Masek","year":"1980","unstructured":"Masek, W., Paterson, M.: A faster algorithm for computing string edit distances. J.\u00a0Comput. Syst. Sci. 20, 18\u201331 (1980)","journal-title":"J. Comput. Syst. Sci."},{"key":"122_CR12_122","doi-asserted-by":"crossref","unstructured":"Muthukrishnan, S., Sahinalp, S.C.: Approximate nearest neighbors and sequence comparison with block operations. Proc. ACM STOC 416\u2013424 (2000)","DOI":"10.1145\/335305.335353"},{"key":"122_CR13_122","doi-asserted-by":"crossref","unstructured":"Sahinalp, S.C., Vishkin, U.: Symmetry breaking for suffix tree construction. ACM STOC 300\u2013309 (1994)","DOI":"10.1145\/195058.195164"},{"key":"122_CR14_122","doi-asserted-by":"crossref","unstructured":"Sahinalp, S.C., Vishkin, U.: Efficient Approximate and Dynamic Matching of Patterns Using a Labeling Paradigm. Proc. IEEE FOCS 320\u2013328 (1996)","DOI":"10.1109\/SFCS.1996.548491"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-0-387-30162-4_122","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,30]],"date-time":"2025-01-30T16:32:32Z","timestamp":1738254752000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-0-387-30162-4_122"}},"subtitle":["2000; Cormode, Paterson, Sahinalp, Vishkin 2000; Muthukrishnan, Sahinalp"],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9780387307701","9780387301624"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-0-387-30162-4_122","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/978-0-387-30162-4","asserted-by":"object"}]},"subject":[],"published":{"date-parts":[[2008]]}}}