{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,23]],"date-time":"2025-09-23T14:14:04Z","timestamp":1758636844923,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540619949"},{"type":"electronic","value":"9783540495888"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/bfb0037393","type":"book-chapter","created":{"date-parts":[[2006,1,25]],"date-time":"2006-01-25T15:15:55Z","timestamp":1138202155000},"page":"1-15","source":"Crossref","is-referenced-by-count":11,"title":["A unified view to string matching algorithms"],"prefix":"10.1007","author":[{"given":"Ricardo","family":"Baeza-Yates","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,26]]},"reference":[{"key":"1_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"},{"key":"1_CR2","doi-asserted-by":"crossref","unstructured":"A. Anderson, T. Hagerup, S. Nilsson, and R. Rajeev. Sorting in linear time? In STOC'95, pages 427\u2013436, Las Vegas, NE, 1995.","DOI":"10.1145\/225058.225173"},{"key":"1_CR3","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1016\/0304-3975(91)90358-9","volume":"78","author":"R. Baeza-Yates","year":"1991","unstructured":"R. Baeza-Yates. Searching subsequences (note). Theoretical Computer Science, 78:363\u2013376, 1991.","journal-title":"Theoretical Computer Science"},{"key":"1_CR4","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1145\/135239.135243","volume":"35","author":"R. Baeza-Yates","year":"1992","unstructured":"R. Baeza-Yates and G.H. Gonnet. A new approach to text searching. Communications of the ACM, 35:74\u201382, Oct 1992.","journal-title":"Communications of the ACM"},{"key":"1_CR5","series-title":"Lecture Notes in Computer Science 644","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1007\/3-540-56024-6_15","volume-title":"Combinatorial Pattern Matching","author":"R.A. Baeza-Yates","year":"1992","unstructured":"R.A. Baeza-Yates and C.H. Perleberg. Fast and practical approximate pattern matching. In A. Apostolico, M. Crochemore, Z. Galil, and U. Manber, editors, Combinatorial Pattern Matching, Lecture Notes in Computer Science 644, pages 185\u2013192, Tucson, AZ, April\/May 1992. Springer Verlag."},{"key":"1_CR6","series-title":"volume Algorithms, Software, Architecture","first-page":"465","volume-title":"12th IFIP World Computer Congress, Volume I","author":"R. Baeza-Yates","year":"1992","unstructured":"R. Baeza-Yates. Text retrieval: Theory and practice. In J. van Leeuwen, editor, 12th IFIP World Computer Congress, Volume I, volume Algorithms, Software, Architecture, pages 465\u2013476, Madrid, Spain, September 1992. Elsevier Science."},{"key":"1_CR7","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1007\/BF01185428","volume":"12","author":"R.A. Baeza-Yates","year":"1994","unstructured":"R.A. Baeza-Yates, C. Choffrut, and G.H. Gonnet. On Boyer-Moore automata. Algorithmica, 12:268\u2013292, 1994.","journal-title":"Algorithmica"},{"key":"1_CR8","doi-asserted-by":"crossref","unstructured":"R. Baeza-Yates. A unified view of pattern matching problems. Technical report, Dept. of Computer Science, Univ. of Chile, 1995.","DOI":"10.1007\/BFb0037393"},{"key":"1_CR9","doi-asserted-by":"crossref","unstructured":"R. Baeza-Yates and G. Navarro. A faster algorithm for approximate string matching. In Combinatorial Pattern Matching (CPM'96), Irvine, CA, Jun 1996. ftp\/\/sunsite.dcc.uchile.cl\/pub\/users\/gnavarro\/cpm96.ps.gz.","DOI":"10.1007\/3-540-61258-0_1"},{"key":"1_CR10","unstructured":"R. Baeza-Yates and G. Navarro. A fast heuristic for approximate string matching. In Third South American Workshop on String Processing, pages 47\u201363, Recife, Brazil, August 1996. ftp\/\/sunsite.dcc.uchile.cl\/pub\/users\/gnavarro\/wsp96.2.ps.gz."},{"key":"1_CR11","doi-asserted-by":"crossref","first-page":"762","DOI":"10.1145\/359842.359859","volume":"20","author":"R. Boyer","year":"1977","unstructured":"R. Boyer and S. Moore. A fast string searching algorithm. C.ACM, 20:762\u2013772, 1977.","journal-title":"C.ACM"},{"key":"1_CR12","unstructured":"V. Bruyere, R. Baeza-Yates, O. Delgrange, and R. Scheihing. On the size of Boyer-Moore automata. In Third South American Workshop on String Processing, pages 31\u201346, Recife, Brazil, August 1996."},{"issue":"1","key":"1_CR13","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0020-0190(95)00043-C","volume":"55","author":"A Dermouche","year":"1995","unstructured":"A Dermouche. A fast algorithm for string matching with mismatches. Information Processing Letters, 55(1):105\u2013110, July 1995.","journal-title":"Information Processing Letters"},{"key":"1_CR14","first-page":"113","volume-title":"Complexity of Computation (SIAM-AMS Proceedings 7), volume 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":"1_CR15","doi-asserted-by":"crossref","first-page":"424","DOI":"10.1016\/0022-0000(93)90040-4","volume":"47","author":"M. Fredman","year":"1993","unstructured":"M. Fredman and D. Willard. Surpassing the information theoretic bound with fusion trees. J. Comput. System Sci., 47:424\u2013436, 1993.","journal-title":"J. Comput. System Sci."},{"key":"1_CR16","volume-title":"Handbook of Algorithms and Data Structures \u2014 In Pascal and C.","author":"G.H. Gonnet","year":"1991","unstructured":"G.H. Gonnet and R. Baeza-Yates. Handbook of Algorithms and Data Structures \u2014 In Pascal and C. Addison-Wesley, Wokingham, UK, 1991. (second edition).","edition":"second edition"},{"issue":"6","key":"1_CR17","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. on Computing, 19(6):989\u2013999, 1990.","journal-title":"SIAM J. on Computing"},{"key":"1_CR18","volume-title":"PhD thesis","author":"C Hancart","year":"1993","unstructured":"C Hancart. Analyse Exacte et en Moyenne d'Algorithmes de Recherche d'un Mot dans un Texte. PhD thesis, Universite Paris 7, Paris, France, 1993."},{"key":"1_CR19","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0020-0190(93)90177-B","volume":"48","author":"H. Karloff","year":"1993","unstructured":"H. Karloff. Fast algorithms for approximately counting mismatches. Information Processing Letters, 48:53\u201360, 1993.","journal-title":"Information Processing Letters"},{"key":"1_CR20","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":"1_CR21","unstructured":"S.R. Kosaraju. Efficient string matching. Manuscript, Johns Hopkins University, 1987."},{"key":"1_CR22","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":"1_CR23","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0020-0190(91)90032-D","volume":"37","author":"U. Manber","year":"1991","unstructured":"U. Manber and R. Baeza-Yates. An algorithm for string matching with a sequence of don't cares. Information Processing Letters, 37:133\u2013136, February 1991.","journal-title":"Information Processing Letters"},{"key":"1_CR24","series-title":"number 970 in LNCS","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1007\/3-540-60268-2_315","volume-title":"Conf. on Analysis of Images and Patterns","author":"B. Melichar","year":"1995","unstructured":"B. Melichar. Approximate string matching by finite automata. In Conf. on Analysis of Images and Patterns, number 970 in LNCS, pages 342\u2013349, Prague, Check Republic, 1995. Springer-Verlag."},{"issue":"1","key":"1_CR25","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/BF02458834","volume":"51","author":"E. Myers","year":"1989","unstructured":"E. Myers and W. Miller. Approximate matching of regular expressions. Bulletin of Mathematical Biology, 51(1):5\u201337, 1989.","journal-title":"Bulletin of Mathematical Biology"},{"issue":"2","key":"1_CR26","doi-asserted-by":"crossref","first-page":"430","DOI":"10.1145\/128749.128755","volume":"39","author":"E. Myers","year":"1992","unstructured":"E. Myers. A four-russians algorithm for regular expression pattern matching. JACM, 39(2):430\u2013448, 1992.","journal-title":"JACM"},{"issue":"4\/5","key":"1_CR27","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1007\/BF01185432","volume":"12","author":"E. Myers","year":"1994","unstructured":"E. Myers. A sublinear algorithm for approximate keyword searching. Algorithmica, 12(4\/5):345\u2013374, Oct\/Nov 1994.","journal-title":"Algorithmica"},{"key":"1_CR28","doi-asserted-by":"crossref","unstructured":"R. Pinter. Efficient string matching with don't-care patterns. In A. Apostolico and Z. Galil, editors, Combinatorial Algorithms on Words, volume F12 of NATO ASI Series, pages 11\u201329. Springer-Verlag, 1985.","DOI":"10.1007\/978-3-642-82456-2_2"},{"key":"1_CR29","unstructured":"I. Simon. String matching algorithms and automata. In First South American Workshop on String Processing, pages 151\u2013157, Belo Horizonte, Brazil. 1993."},{"key":"1_CR30","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1145\/363347.363387","volume":"11","author":"K. Thompson","year":"1968","unstructured":"K. Thompson. Regular expression search algorithm. C.ACM, 11:419\u2013422, 1968.","journal-title":"C.ACM"},{"key":"1_CR31","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. Information and Control, 64:100\u2013118, 1985.","journal-title":"Information and Control"},{"key":"1_CR32","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1016\/0196-6774(85)90023-9","volume":"6","author":"E. Ukkonen","year":"1985","unstructured":"E. Ukkonen. Finding approximate patterns in strings. J. of Algorithms, 6:132\u2013137, 1985.","journal-title":"J. of Algorithms"},{"key":"1_CR33","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. Communications of the ACM, 35:83\u201391, Oct 1992.","journal-title":"Communications of the ACM"},{"key":"1_CR34","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1006\/jagm.1995.1041","volume":"19","author":"S. Wu","year":"1995","unstructured":"S. Wu, U. Manber, and E. Myers. A subquadratic algorithm for approximate regular expression matching. Journal of Algorithms, 19:346\u2013360, 1995.","journal-title":"Journal of Algorithms"},{"issue":"4","key":"1_CR35","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1002\/spe.4380240402","volume":"24","author":"A. Wright","year":"1994","unstructured":"A. Wright. Approximate string matching using within-word parallelism. Software Practice and Experience, 24(4):337\u2013362, April 1994.","journal-title":"Software Practice and Experience"}],"container-title":["Lecture Notes in Computer Science","SOFSEM'96: Theory and Practice of Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0037393","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,7]],"date-time":"2025-01-07T11:47:36Z","timestamp":1736250456000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0037393"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540619949","9783540495888"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/bfb0037393","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}