{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T05:40:19Z","timestamp":1775281219317,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540632207","type":"print"},{"value":"9783540692140","type":"electronic"}],"license":[{"start":{"date-parts":[[1997,1,1]],"date-time":"1997-01-01T00:00:00Z","timestamp":852076800000},"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":[[1997]]},"DOI":"10.1007\/3-540-63220-4_47","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T23:19:31Z","timestamp":1330298371000},"page":"28-39","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Efficient algorithms for approximate string matching with swaps"],"prefix":"10.1007","author":[{"given":"Jee-Soo","family":"Lee","sequence":"first","affiliation":[]},{"given":"Dong Kyue","family":"Kim","sequence":"additional","affiliation":[]},{"given":"Kunsoo","family":"Park","sequence":"additional","affiliation":[]},{"given":"Yookun","family":"Cho","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,8]]},"reference":[{"key":"3_CR1","doi-asserted-by":"crossref","unstructured":"R. Baeza-Yates and G. Navarro, A faster algorithm for approximate string matching, In Proc. of the 7th Symp. on Combinatorial Pattern Matching, Springer-Verlag Lecture Note in Comp. Sci. 1075 (1996), 1\u201323.","DOI":"10.1007\/3-540-61258-0_1"},{"key":"3_CR2","doi-asserted-by":"crossref","first-page":"519","DOI":"10.1145\/146637.146650","volume":"39","author":"D. Eppstein","year":"1992","unstructured":"D. Eppstein, Z. Galil, R. Giancarlo, and G. Italiano, Sparse dynamic programming I: linear cost functions, J. Assoc. Comput. Mach. 39 (1992), 519\u2013545.","journal-title":"J. Assoc. Comput. Mach."},{"key":"3_CR3","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/0885-064X(88)90008-8","volume":"4","author":"Z. Galil","year":"1988","unstructured":"Z. Galil and R. Giancarlo, Data structures and algorithms for approximate string matching, J. Complexity 4 (1988), 33\u201372.","journal-title":"J. Complexity"},{"key":"3_CR4","doi-asserted-by":"crossref","first-page":"989","DOI":"10.1137\/0219067","volume":"19","author":"Z. Galil","year":"1990","unstructured":"Z. Galil and K. Park, An improved algorithm for approximate string matching, SIAM J. Comput. 19 (1990), 989\u2013999.","journal-title":"SIAM J. Comput."},{"key":"3_CR5","doi-asserted-by":"crossref","unstructured":"S. Hannenhalli and P.A. Pevzner, Transforming men into mice (polynomial algorithm for genomic distance problem), IEEE Symp. Found. Computer Science (1995), 581\u2013592.","DOI":"10.1109\/SFCS.1995.492588"},{"key":"3_CR6","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/0196-6774(89)90010-2","volume":"10","author":"G.M. Landau","year":"1989","unstructured":"G.M. Landau and U. Vishkin, Fast parallel and serial approximate string matching, J. Algorithms 10 (1989), 157\u2013169.","journal-title":"J. Algorithms"},{"key":"3_CR7","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1145\/321879.321880","volume":"22","author":"R. Lowrance","year":"1975","unstructured":"R. Lowrance and R.A. Wagner, An extension of the string-to-string correction problem, J. Assoc. Comput. Mach. 22 (1975), 177\u2013183.","journal-title":"J. Assoc. Comput. Mach."},{"key":"3_CR8","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/BF01840446","volume":"1","author":"E.W. Myers","year":"1986","unstructured":"E.W. Myers, An O(ND) difference algorithm and its variations, Algorithmica 1 (1986), 251\u2013266.","journal-title":"Algorithmica"},{"key":"3_CR9","volume-title":"Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison","author":"D. Sankoff","year":"1983","unstructured":"D. Sankoff and J.B. Kruskal, Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison, New York, Addison-Wesley (1983)."},{"key":"3_CR10","doi-asserted-by":"crossref","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, Inform. and Control 64 (1985), 100\u2013118.","journal-title":"Inform. and Control"},{"key":"3_CR11","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1007\/BF01769703","volume":"10","author":"E. Ukkonen","year":"1993","unstructured":"E. Ukkonen and D. Wood, Approximate string matching with suffix automata, Algorithmica 10 (1993), 353\u2013364.","journal-title":"Algorithmica"},{"key":"3_CR12","doi-asserted-by":"crossref","unstructured":"R.A. Wagner, On the complexity of the extended string-to-string correction problem, ACM Symp. Theory of Computing (1975), 218\u2013223.","DOI":"10.1145\/800116.803771"},{"key":"3_CR13","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1145\/321796.321811","volume":"21","author":"R.A. Wagner","year":"1974","unstructured":"R.A. Wagner and M.J. Fischer, The string-to-string correction problem, J. Assoc. Comput. Mach. 21 (1974), 168\u2013173.","journal-title":"J. Assoc. Comput. Mach."},{"key":"3_CR14","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1145\/135239.135244","volume":"35","author":"S. Wu","year":"1992","unstructured":"S. Wu and U. Manber, Fast text searching allowing errors, Comm. ACM 35 (1992), 83\u201391.","journal-title":"Comm. ACM"}],"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-63220-4_47","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:40:11Z","timestamp":1742600411000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63220-4_47"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540632207","9783540692140"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-63220-4_47","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997]]},"assertion":[{"value":"8 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}