{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:38:16Z","timestamp":1725489496513},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540414131"},{"type":"electronic","value":"9783540444503"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44450-5_24","type":"book-chapter","created":{"date-parts":[[2007,8,16]],"date-time":"2007-08-16T08:26:08Z","timestamp":1187252768000},"page":"302-311","source":"Crossref","is-referenced-by-count":1,"title":["Approximate Swapped Matching"],"prefix":"10.1007","author":[{"given":"Amihood","family":"Amir","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Moshe","family":"Lewenstein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ely","family":"Porat","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2000,11,24]]},"reference":[{"issue":"6","key":"24_CR1","doi-asserted-by":"publisher","first-page":"1039","DOI":"10.1137\/0216067","volume":"16","author":"K. Abrahamson","year":"1987","unstructured":"K. Abrahamson. Generalized string matching. SIAM J. Comp., 16(6):1039\u20131051, 1987.","journal-title":"SIAM J. Comp."},{"key":"24_CR2","unstructured":"A. Amir, Y. Aumann, G. Landau, M. Lewenstein, and N. Lewenstein. Pattern matching with swaps. Submitted for publication."},{"key":"24_CR3","doi-asserted-by":"crossref","unstructured":"A. Amir, Y. Aumann, G. Landau, M. Lewenstein, and N. Lewenstein. Pattern matching with swaps. Proc. 38th IEEE FOCS, 144\u2013153, 1997.","DOI":"10.1109\/SFCS.1997.646103"},{"issue":"1","key":"24_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1995.1047","volume":"118","author":"A. Amir","year":"1995","unstructured":"A. Amir and M. Farach. Efficient 2-dimensional approximate matching of halfrectangular figures. Information and Computation, 118(1):1\u201311, April 1995.","journal-title":"Information and Computation"},{"issue":"3","key":"24_CR5","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/S0020-0190(98)00151-3","volume":"68","author":"A. Amir","year":"1998","unstructured":"A. Amir, G. M. Landau, M. Lewenstein, and N. Lewenstein. Efficient special cases of pattern matching with swaps. Information Processing Letters, 68(3):125\u2013132, 1998.","journal-title":"Information Processing Letters"},{"key":"24_CR6","unstructured":"R. Cole and R. Harihan. Randomized swap matching in o(m log m log \u2223\u03c3\u2223) time. Technical Report TR1999\u2013789, New York University, Courant Institute, September 1999."},{"key":"24_CR7","unstructured":"R. Cole and R. Hariharan. Approximate string matching: A faster simpler algorithm. In Proc. 9th ACM-SIAM Symposium on Discrete Algorithms (SODA), 463\u2013472, 1998."},{"key":"24_CR8","unstructured":"M. J. Fischer and M. S. Paterson. String matching and other products. Complexity of Computation, R. M. Karp (editor), SIAM-AMS Proceedings, 7:113\u2013125, 1"},{"issue":"6","key":"24_CR9","doi-asserted-by":"publisher","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. Comp., 19(6):989\u2013999, 1990.","journal-title":"SIAM J. Comp."},{"key":"24_CR10","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"D. E. Knuth","year":"1977","unstructured":"D. E. Knuth, J. H. Morris, and V. R. Pratt. Fast pattern matching in strings. SIAM J. Comp., 6:323\u2013350, 1977.","journal-title":"SIAM J. Comp."},{"issue":"2","key":"24_CR11","doi-asserted-by":"publisher","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. Journal of Algorithms, 10(2):157\u2013169, 1989.","journal-title":"Journal of Algorithms"},{"issue":"2","key":"24_CR12","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1137\/S0097539794264810","volume":"27","author":"G. M. Landau","year":"1998","unstructured":"G. M. Landau, E. W. Myers, and J. P. Schmidt. Incremental string comparison. SIAM J. Comp., 27(2):557\u2013582, 1998.","journal-title":"SIAM J. Comp."},{"key":"24_CR13","first-page":"707","volume":"10","author":"V. I. Levenshtein","year":"1966","unstructured":"V. I. Levenshtein. Binary codes capable of correcting, deletions, insertions and reversals. Soviet Phys. Dokl., 10:707\u2013710, 1966.","journal-title":"Soviet Phys. Dokl."},{"key":"24_CR14","doi-asserted-by":"crossref","unstructured":"R. Lowrance and R. A. Wagner. An extension of the string-to-string correction problem. J. of the ACM, 177\u2013183, 1975.","DOI":"10.1145\/321879.321880"},{"issue":"1","key":"24_CR15","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1006\/inco.1995.1144","volume":"122","author":"S. Muthukrishnan","year":"1995","unstructured":"S. Muthukrishnan and H. Ramesh. String matching under a general matching relation. Information and Computation, 122(1):140\u2013148, 1995.","journal-title":"Information and Computation"},{"key":"24_CR16","doi-asserted-by":"crossref","unstructured":"J. Naor and M. Naor. Small-bias probability spaces: Efficient constructions and applications. SIAM J. Comp., 838\u2013856, 1993.","DOI":"10.1137\/0222053"},{"key":"24_CR17","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1126\/science.270.5235.394","volume":"270","author":"M. V. Olson","year":"1995","unstructured":"M. V. Olson. A time to sequence. Science, 270:394\u2013396, 1995.","journal-title":"Science"},{"key":"24_CR18","unstructured":"A. Pentland. Invited talk. NSF Institutional Infrastructure Workshop, 1992."},{"key":"24_CR19","doi-asserted-by":"crossref","unstructured":"R. A. Wagner. On the complexity of the extended string-to-string correction problem. In Proc. 7th ACM STOC, 218\u2013223, 1975.","DOI":"10.1145\/800116.803771"}],"container-title":["Lecture Notes in Computer Science","FST TCS 2000: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44450-5_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T04:17:20Z","timestamp":1556770640000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44450-5_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540414131","9783540444503"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-44450-5_24","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}