{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,30]],"date-time":"2026-01-30T04:48:00Z","timestamp":1769748480454,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540560241","type":"print"},{"value":"9783540473572","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1992]]},"DOI":"10.1007\/3-540-56024-6_15","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T10:53:36Z","timestamp":1330253616000},"page":"185-192","source":"Crossref","is-referenced-by-count":40,"title":["Fast and practical approximate string matching"],"prefix":"10.1007","author":[{"given":"Ricardo A.","family":"Baeza-Yates","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chris H.","family":"Perleberg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,4]]},"reference":[{"key":"15_CR1","doi-asserted-by":"crossref","first-page":"1039","DOI":"10.1137\/0216067","volume":"16","author":"K. Abrahamson","year":"1987","unstructured":"K. Abrahamson. Generalized string matching. SIAM J on Computing, 16:1039\u20131051, 1987.","journal-title":"SIAM J on Computing"},{"issue":"6","key":"15_CR2","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1145\/360825.360855","volume":"18","author":"A.V. Aho","year":"1975","unstructured":"A.V. Aho and M. Corasick. Efficient string matching: An aid to bibliographic search. C.ACM, 18(6):333\u2013340, June 1975.","journal-title":"C.ACM"},{"key":"15_CR3","doi-asserted-by":"crossref","unstructured":"R. Baeza-Yates and G.H. Gonnet. A new approach to text searching. In Proc. of 12th ACM SIGIR, pages 168\u2013175, Cambridge, Mass., June 1989. (Addendum in ACM SIGIR Forum, V. 23, Numbers 3, 4, 1989, page 7.). To appear in Communications of CACM.","DOI":"10.1145\/75334.75352"},{"key":"15_CR4","unstructured":"R. Baeza-Yates and G.H. Gonnet. Fast string matching with mismatches. Information and Computation, 1992. (to appear). Also as Tech. Report CS-88-36, Dept. of Computer Science, University of Waterloo, 1988."},{"key":"15_CR5","series-title":"Lecture Notes in Computer Science 447","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1007\/3-540-52846-6_102","volume-title":"2nd Scandinavian Workshop in Algorithmic Theory, SWAT'90","author":"R. Baeza-Yates","year":"1990","unstructured":"R. Baeza-Yates and M. R\u00e9gnier. Fast algorithms for two dimensional and multiple pattern matching. In R. Karlsson and J. Gilbert, editors, 2nd Scandinavian Workshop in Algorithmic Theory, SWAT'90, Lecture Notes in Computer Science 447, pages 332\u2013347, Bergen, Norway, July 1990. Springer-Verlag."},{"key":"15_CR6","first-page":"116","volume-title":"Proc. 31st FOCS","author":"W. Chang","year":"1990","unstructured":"W. Chang and E. Lawler. Approximated string matching in sublinear expected time. In Proc. 31st FOCS, pages 116\u2013124, St. Louis, MO, Oct 1990. IEEE."},{"key":"15_CR7","doi-asserted-by":"crossref","unstructured":"B. Commentz-Walter. A string matching algorithm fast on the average. In ICALP, volume 6 of Lecture Notes in Computer Science, pages 118\u2013132. Springer-Verlag, 1979.","DOI":"10.1007\/3-540-09510-1_10"},{"key":"15_CR8","volume-title":"Complexity of Computation (SIAM-AMS Proceedings 7)","author":"M. Fischer","year":"1974","unstructured":"M. Fischer and M. Paterson. String matching and other products. In R. Karp, editor, Complexity of Computation (SIAM-AMS Proceedings 7), volume 7, pages 113\u2013125. American Mathematical Society, Providence, RI, 1974."},{"key":"15_CR9","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1145\/8307.8309","volume":"17","author":"Z. Galil","year":"1986","unstructured":"Z. Galil and R. Giancarlo. Improved string matching with k mismatches. SIGACT News, 17:52\u201354, 1986.","journal-title":"SIGACT News"},{"key":"15_CR10","doi-asserted-by":"crossref","unstructured":"Z. Galil and K. Park. An improved algorithm for approximate string matching. In ICALP'89, pages 394\u2013404, Stressa, Italy, 1989.","DOI":"10.1007\/BFb0035772"},{"key":"15_CR11","volume-title":"Pascal and C","author":"G.H. Gonnet","year":"1991","unstructured":"G.H. Gonnet and R. Baeza-Yates. Handbook of Algorithms and Data Structures-In Pascal and C. Addison-Wesley, Wokingham, UK, 1991. (second edition).","edition":"second edition"},{"issue":"3","key":"15_CR12","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/0020-0190(89)90188-9","volume":"33","author":"R. Grossi","year":"1989","unstructured":"R. Grossi and F. Luccio. Simple and efficient string matching with k mismatches. Inf. Proc. Letters, 33(3):113\u2013120, July 1989.","journal-title":"Inf. Proc. Letters"},{"issue":"11","key":"15_CR13","doi-asserted-by":"crossref","first-page":"1221","DOI":"10.1002\/spe.4380211105","volume":"21","author":"A. Hume","year":"1991","unstructured":"A. Hume and D.M. Sunday. Fast string searching. Software \u2014 Practice and Experience, 21(11):1221\u20131248, Nov 1991.","journal-title":"Software \u2014 Practice and Experience"},{"key":"15_CR14","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"D.E. Knuth","year":"1977","unstructured":"D.E. Knuth, J. Morris, and V. Pratt. Fast pattern matching in strings. SIAM J on Computing, 6:323\u2013350, 1977.","journal-title":"SIAM J on Computing"},{"key":"15_CR15","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/0304-3975(86)90178-7","volume":"43","author":"G. Landau","year":"1986","unstructured":"G. Landau and U. Vishkin. Efficient string matching with k mismatches. Theoretical Computer Science, 43:239\u2013249, 1986.","journal-title":"Theoretical Computer Science"},{"key":"15_CR16","first-page":"63","volume":"37","author":"G. Landau","year":"1988","unstructured":"G. Landau and U. Vishkin. Fast string matching with k differences. JCSS, 37:63\u201378, 1988.","journal-title":"JCSS"},{"key":"15_CR17","volume-title":"Technical Report TR-89-19","author":"U. Manber","year":"1989","unstructured":"U. Manber and S. Wu. An algorithm for approximate string matching with non uniform costs. Technical Report TR-89-19, Department of Computer Science, University of Arizona, Tucson, Arizona, Sept 1989."},{"issue":"10","key":"15_CR18","doi-asserted-by":"crossref","first-page":"1065","DOI":"10.1002\/spe.4380211006","volume":"21","author":"P.D. Smith","year":"1991","unstructured":"P.D. Smith. Experiments with a very fast substring search algorithm. Software \u2014 Practice and Experience, 21(10):1065\u20131074, Oct 1991.","journal-title":"Software \u2014 Practice and Experience"},{"key":"15_CR19","unstructured":"M.A. Sridhar. Efficient algorithms for multiple pattern matching. Technical Report Computer Sciences 661, University of Wisconsin-Madison, 1986."},{"key":"15_CR20","series-title":"Lecture Notes in Computer Science 447","doi-asserted-by":"crossref","first-page":"348","DOI":"10.1007\/3-540-52846-6_103","volume-title":"2nd Scandinavian Workshop in Algorithmic Theory, SWAT'90","author":"J. Tarhio","year":"1990","unstructured":"J. Tarhio and E. Ukkonen. Boyer-moore approach to approximate string matching. In J.R. Gilbert and R.G. Karlsson, editors, 2nd Scandinavian Workshop in Algorithmic Theory, SWAT'90, Lecture Notes in Computer Science 447, pages 348\u2013359, Bergen, Norway, July 1990. Springer-Verlag."},{"key":"15_CR21","unstructured":"S. Wu. personal communication. 1992."},{"key":"15_CR22","volume-title":"Technical Report TR-91-11","author":"S. Wu","year":"1991","unstructured":"S. Wu and U. Manber. Fast text searching with errors. Technical Report TR-91-11, Department of Computer Science, University of Arizona, Tucson, Arizona, June 1991."},{"key":"15_CR23","unstructured":"S. Wu and U. Manber. Agrep \u2014 a fast approximate pattern-matching tool. In Proceedings of USENIX Winter 1992 Technical Conference, pages 153\u2013162, San Francisco, CA, Jan 1992."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56024-6_15.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T00:48:22Z","timestamp":1619570902000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56024-6_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992]]},"ISBN":["9783540560241","9783540473572"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-56024-6_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992]]}}}