{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T16:22:40Z","timestamp":1780330960503,"version":"3.54.1"},"reference-count":37,"publisher":"Oxford University Press (OUP)","issue":"6","license":[{"start":{"date-parts":[[2021,2,23]],"date-time":"2021-02-23T00:00:00Z","timestamp":1614038400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,6,16]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>We consider the $k$ mismatches version of approximate string matching for a single pattern and multiple patterns. For these problems, we present new algorithms utilizing the single instruction multiple data (SIMD) instruction set extensions for patterns of up to 32 characters. We apply SIMD computation in three ways: in counting of mismatches, in comparison of substrings and in calculation of fingerprints. We show the competitiveness of the new algorithms by practical experiments.<\/jats:p>","DOI":"10.1093\/comjnl\/bxaa193","type":"journal-article","created":{"date-parts":[[2020,12,19]],"date-time":"2020-12-19T07:52:54Z","timestamp":1608364374000},"page":"1472-1488","source":"Crossref","is-referenced-by-count":8,"title":["Approximate String Matching with SIMD"],"prefix":"10.1093","volume":"65","author":[{"given":"Fernando J","family":"Fiori","sequence":"first","affiliation":[{"name":"Departamento de Ciencias de la Computaci\u00f3n , Facultad de Ciencias Exactas, Ingenier\u00eda y Agrimensura, Universidad Nacional de Rosario, Pellegrini 250, S2000BTP Rosario, Argentina"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Waltteri","family":"Pakal\u00e9n","sequence":"additional","affiliation":[{"name":"Department of Computer Science , Aalto University, P.O.B. 15400, FI-00076 Aalto, Finland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jorma","family":"Tarhio","sequence":"additional","affiliation":[{"name":"Department of Computer Science , Aalto University, P.O.B. 15400, FI-00076 Aalto, Finland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2021,2,23]]},"reference":[{"key":"2022061614515459400_ref1","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1145\/375360.375365","article-title":"A guided tour to approximate string matching","volume":"33","author":"Navarro","year":"2001","journal-title":"ACM Comput. Surv."},{"key":"2022061614515459400_ref2","author":"Intel. Intel (R) 64 and IA-32 Architectures Software Developer\u2019s Manual"},{"issue":"1","key":"2022061614515459400_ref3","first-page":"4","article-title":"Average-optimal single and multiple approximate string matching","volume":"9","author":"Fredriksson","year":"2005","journal-title":"ACM J. Exp. Algorithmics"},{"key":"2022061614515459400_ref4","first-page":"11","article-title":"A pattern-matching model for intrusion detection","volume-title":"Proc. 17th National Computer Security Conference","author":"Kumar","year":"1994"},{"key":"2022061614515459400_ref5","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1145\/146370.146380","article-title":"Techniques for automatically correcting words in text","volume":"24","author":"Kukich","year":"1992","journal-title":"ACM Comput. Surv."},{"key":"2022061614515459400_ref6","volume-title":"Automatic Speech and Speaker Recognition","author":"Dixon","year":"1979"},{"key":"2022061614515459400_ref7","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/0031-3203(90)90021-C","article-title":"A review of segmentation and contextual analysis techniques for text recognition","volume":"23","author":"Elliman","year":"1990","journal-title":"Pattern Recognit."},{"key":"2022061614515459400_ref8","volume-title":"Modern Information Retrieval","author":"Baeza-Yates","year":"1999"},{"key":"2022061614515459400_ref9","first-page":"370","article-title":"Ant-CSP: An ant colony optimization algorithm for the closest string problem","volume-title":"SOFSEM 2010: Theory and Practice of Computer Science, 36th Conference on Current Trends in Theory and Practice of Computer Science, Spindleruv Ml\u00fdn, Czech Republic, January 23\u201329, 2010. Proceedings","author":"Faro","year":"2010"},{"key":"2022061614515459400_ref10","first-page":"384","article-title":"Multi-pattern matching with bidirectional indexes","volume-title":"Computing and Combinatorics - 18th Annual International Conference, COCOON 2012, Sydney, Australia, August 20\u201322, 2012. Proceedings, Lecture Notes in Computer Science","author":"Gog","year":"2012"},{"key":"2022061614515459400_ref11","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/0020-0190(96)00083-X","article-title":"Fast and practical approximate string matching","volume":"59","author":"Baeza-Yates","year":"1996","journal-title":"Inf. Process. Lett."},{"key":"2022061614515459400_ref12","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1145\/135239.135243","article-title":"A new approach to text searching","volume":"35","author":"Baeza-Yates","year":"1992","journal-title":"Commun. ACM"},{"key":"2022061614515459400_ref13","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1016\/j.ipl.2007.08.021","article-title":"Bit-parallel string matching under Hamming distance in O(n[m\/w]) worst case time","volume":"105","author":"Grabowski","year":"2008","journal-title":"Inf. Process. Lett."},{"key":"2022061614515459400_ref14","first-page":"71","article-title":"Improved two-way bit-parallel search","volume-title":"Proceedings of the Prague Stringology Conference 2014, Prague, Czech Republic, September 1\u20133, 2014","author":"Durian","year":"2014"},{"key":"2022061614515459400_ref15","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1137\/0222018","article-title":"Approximate Boyer-Moore string matching","volume":"22","author":"Tarhio","year":"1993","journal-title":"SIAM J. Comput."},{"key":"2022061614515459400_ref16","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1002\/spe.4380100608","article-title":"Practical fast searching in strings","volume":"10","author":"Horspool","year":"1980","journal-title":"Softw. Pract. Exp."},{"key":"2022061614515459400_ref17","first-page":"79","article-title":"A fast algorithm for approximate string matching on gene sequences","volume-title":"Proceedings of Combinatorial Pattern Matching, 16th Annual Symposium, CPM 2005, Jeju Island, Korea, June 19\u201322, 2005, Lecture Notes in Computer Science","author":"Liu","year":"2005"},{"key":"2022061614515459400_ref18","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1007\/s00453-009-9286-3","article-title":"Approximate Boyer-Moore string matching for small alphabets","volume":"58","author":"Salmela","year":"2010","journal-title":"Algorithmica"},{"key":"2022061614515459400_ref19","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1145\/351827.384246","article-title":"Fast and flexible string matching by combining bit-parallelism and suffix automata","volume":"5","author":"Navarro","year":"2000","journal-title":"ACM J. Exp. Algorithmics"},{"key":"2022061614515459400_ref20","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1016\/0196-6774(85)90023-9","article-title":"Finding approximate patterns in strings","volume":"6","author":"Ukkonen","year":"1985","journal-title":"J. Algorithms"},{"key":"2022061614515459400_ref21","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1145\/8307.8309","article-title":"Improved string matching with k mismatches","volume":"17","author":"Galil","year":"1986","journal-title":"SIGACT News"},{"key":"2022061614515459400_ref22","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/0304-3975(86)90178-7","article-title":"Efficient string matching with k mismatches","volume":"43","author":"Landau","year":"1986","journal-title":"Theor. Comput. Sci."},{"key":"2022061614515459400_ref23","doi-asserted-by":"crossref","first-page":"1039","DOI":"10.1137\/0216067","article-title":"Generalized string matching","volume":"16","author":"Abrahamson","year":"1987","journal-title":"SIAM J. Comput."},{"key":"2022061614515459400_ref24","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/S0196-6774(03)00097-X","article-title":"Faster algorithms for string matching with k mismatches","volume":"50","author":"Amir","year":"2004","journal-title":"J. Algorithms"},{"key":"2022061614515459400_ref25","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1016\/j.ejc.2012.07.013","article-title":"Exploiting word-level parallelism for fast convolutions and their applications in approximate string matching","volume":"34","author":"Fredriksson","year":"2013","journal-title":"Eur. J. Comb."},{"key":"2022061614515459400_ref26","first-page":"2039","article-title":"The k-mismatch problem revisited","volume-title":"Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10\u201312, 2016","author":"Clifford","year":"2016"},{"key":"2022061614515459400_ref27","first-page":"75","article-title":"Approximate multiple strings search","volume-title":"Proceedings of Combinatorial Pattern Matching, 7th Annual Symposium, CPM 96, Laguna Beach, California, USA, June 10\u201312, 1996, Lecture Notes in Computer Science","author":"Muth","year":"1996"},{"key":"2022061614515459400_ref28","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1002\/rsa.10014","article-title":"New and faster filters for multiple approximate string matching","volume":"20","author":"Baeza-Yates","year":"2002","journal-title":"Random Struct Algorithms"},{"key":"2022061614515459400_ref29","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1145\/79173.79184","article-title":"A very fast substring search algorithm","volume":"33","author":"Sunday","year":"1990","journal-title":"Commun. ACM"},{"key":"2022061614515459400_ref30","doi-asserted-by":"crossref","first-page":"731","DOI":"10.1002\/spe.2433","article-title":"Engineering order-preserving pattern matching with SIMD parallelism","volume":"47","author":"Chhabra","year":"2017","journal-title":"Softw. Pract. Exp."},{"key":"2022061614515459400_ref31","first-page":"113","article-title":"Fast packed string matching for short patterns","volume-title":"Proceedings of the 15th Meeting on Algorithm Engineering and Experiments, ALENEX 2013, New Orleans, Louisiana, USA, January 7, 2013","author":"Faro","year":"2013"},{"key":"2022061614515459400_ref32","first-page":"118","article-title":"Filter based fast matching of long patterns by using SIMD instructions","volume-title":"Proceedings of the Prague Stringology Conference 2009, Prague, Czech Republic, August 31 \u2013 September 2, 2009","author":"K\u00fclekci","year":"2009"},{"key":"2022061614515459400_ref33","first-page":"254","article-title":"Exploiting SIMD instructions in current processors to improve classical string algorithms","volume-title":"Advances in Databases and Information Systems \u2013 16th East European Conference, ADBIS 2012, Pozna\u0144, Poland, September 18\u201321, 2012. Proceedings, Lecture Notes in Computer Science","author":"Ladra","year":"2012"},{"key":"2022061614515459400_ref34","doi-asserted-by":"crossref","first-page":"1877","DOI":"10.1002\/spe.2511","article-title":"Technology beats algorithms (in exact string matching)","volume":"47","author":"Tarhio","year":"2017","journal-title":"Softw. Pract. Exp."},{"key":"2022061614515459400_ref35","first-page":"78","article-title":"Towards a very fast multiple string matching algorithm for short patterns","volume-title":"Proceedings of the Prague Stringology Conference 2013, Prague, Czech Republic, September 2\u20134, 2013","author":"Faro","year":"2013"},{"key":"2022061614515459400_ref36","article-title":"Bit-parallel approximate string matching under Hamming distance","author":"Hirvola","year":"2016"},{"key":"2022061614515459400_ref37","doi-asserted-by":"crossref","first-page":"1221","DOI":"10.1002\/spe.4380211105","article-title":"Fast string searching","volume":"21","author":"Hume","year":"1991","journal-title":"Softw. Pract. Exp."}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/65\/6\/1472\/44080942\/bxaa193.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/65\/6\/1472\/44080942\/bxaa193.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,16]],"date-time":"2022-06-16T14:53:59Z","timestamp":1655391239000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/65\/6\/1472\/6134013"}},"subtitle":[],"editor":[{"given":"Prudence","family":"Wong","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]}],"short-title":[],"issued":{"date-parts":[[2021,2,23]]},"references-count":37,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2021,2,23]]},"published-print":{"date-parts":[[2022,6,16]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxaa193","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"value":"0010-4620","type":"print"},{"value":"1460-2067","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2022,6]]},"published":{"date-parts":[[2021,2,23]]}}}