{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,16]],"date-time":"2026-10-16T00:44:05Z","timestamp":1792111445562,"version":"4.4.0"},"publisher-location":"New York, NY","reference-count":14,"publisher":"Springer New York","isbn-type":[{"value":"9781493928637","type":"print"},{"value":"9781493928644","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[[2016]]},"DOI":"10.1007\/978-1-4939-2864-4_122","type":"book-chapter","created":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T16:48:01Z","timestamp":1553100481000},"page":"611-614","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"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","published-online":{"date-parts":[[2016,4,22]]},"reference":[{"issue":"2","key":"122_CR51","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1137\/S089548019528280X","volume":"11","author":"V Bafna","year":"1998","unstructured":"Bafna V, Pevzner PA (1998) Sorting by transpositions. SIAM J Discret Math 11(2):224\u2013240","journal-title":"SIAM J Discret Math"},{"key":"122_CR52","doi-asserted-by":"crossref","unstructured":"Batu T, Erg\u00fcn F, Sahinalp SC (2006) Oblivious string embeddings and edit distance approximations. In: Proceedings of the ACM-SIAM SODA, pp 792\u2013801","DOI":"10.1145\/1109557.1109644"},{"issue":"1\u20132","key":"122_CR53","first-page":"7","volume":"76","author":"S Besmaphyatnikh","year":"2000","unstructured":"Besmaphyatnikh S, Segal M (2000) Enumerating longest increasing subsequences and patience sorting. Inf Process Lett 76(1\u20132):7\u201311","journal-title":"Inf Process Lett"},{"key":"122_CR54","unstructured":"Cormode G, Muthukrishnan S (2002) The string edit distance matching problem with moves. In: Proceedings of the ACM-SIAM SODA, pp 667\u2013676"},{"key":"122_CR55","unstructured":"Cormode G, Paterson M, Sahinalp SC, Vishkin U (2000) Communication complexity of document exchange. In: Proceedings of the ACM-SIAM SODA, pp 197\u2013206"},{"key":"122_CR56","doi-asserted-by":"crossref","unstructured":"Indyk P, Motwani R (1998) Approximate nearest neighbors: towards removing the curse of fimensionality. In: Proceedings of the ACM STOC, pp 604\u2013613","DOI":"10.1145\/276698.276876"},{"issue":"1","key":"122_CR57","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 (2005) The greedy algorithm for shortest superstrings. Info Process Lett 93(1):13\u201317","journal-title":"Info Process Lett"},{"key":"122_CR58","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 (1989) Fast parallel and serial approximate string matching. J Algorithms 10:157\u2013169","journal-title":"J Algorithms"},{"key":"122_CR59","unstructured":"Levenshtein VI (1965) Binary codes capable of correcting deletions, insertions, and reversals. Dokl Akad Nauk SSSR 163(4):845\u2013848 (Russian). (1966) Sov Phys Dokl 10(8):707\u2013710 (English translation)"},{"issue":"1","key":"122_CR510","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0304-3975(96)00268-X","volume":"181","author":"DP Lopresti","year":"1997","unstructured":"Lopresti DP, Tomkins A (1997) Block edit models for approximate string matching. Theor Comput Sci 181(1):159\u2013179","journal-title":"Theor Comput Sci"},{"key":"122_CR511","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 (1980) A faster algorithm for computing string edit distances. J Comput Syst Sci 20:18\u201331","journal-title":"J Comput Syst Sci"},{"key":"122_CR512","doi-asserted-by":"crossref","unstructured":"Muthukrishnan S, Sahinalp SC (2000) Approximate nearest neighbors and sequence comparison with block operations. In: Proceedings of the ACM STOC, pp 416\u2013424","DOI":"10.1145\/335305.335353"},{"key":"122_CR513","doi-asserted-by":"crossref","unstructured":"Sahinalp SC, Vishkin U (1994) Symmetry breaking for suffix tree construction. In: ACM STOC, pp 300\u2013309","DOI":"10.1145\/195058.195164"},{"key":"122_CR514","doi-asserted-by":"crossref","unstructured":"Sahinalp SC, Vishkin U (1996) Efficient approximate and dynamic matching of patterns using a labeling paradigm. In: Proceeding of the IEEE FOCS, pp 320\u2013328","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-1-4939-2864-4_122","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,15]],"date-time":"2026-10-15T23:47:06Z","timestamp":1792108026000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/chapter\/10.1007\/978-1-4939-2864-4_122"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9781493928637","9781493928644"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_122","relation":{},"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}