{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:23:38Z","timestamp":1760243018673,"version":"build-2065373602"},"reference-count":29,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2015,5,26]],"date-time":"2015-05-26T00:00:00Z","timestamp":1432598400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000930","name":"NSF","doi-asserted-by":"publisher","award":["1447711","0829916"],"award-info":[{"award-number":["1447711","0829916"]}],"id":[{"id":"10.13039\/501100000930","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000002","name":"NIH","doi-asserted-by":"publisher","award":["R01LM010101"],"award-info":[{"award-number":["R01LM010101"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>In this  paper, we consider several variants of the pattern matching with  mismatches problem. In particular, given a text \\(T=t_1 t_2\\cdots  t_n\\) and a pattern \\(P=p_1p_2\\cdots p_m\\), we investigate the following problems: (1) pattern matching with mismatches: for every \\(i, 1\\leq i \\leq  n-m+1\\) output, the distance between \\(P\\) and \\(t_i t_{i+1}\\cdots t_{i+m-1}\\); and (2) pattern matching with \\(k\\) mismatches: output those positions \\(i\\) where  the distance between \\(P\\) and \\(t_i t_{i+1}\\cdots t_{i+m-1}\\) is less than a given  threshold \\(k\\). The distance metric used is the Hamming distance.   We present some novel algorithms and techniques for solving these  problems. We offer deterministic, randomized and approximation algorithms.  We consider variants of these problems where there could be wild cards in  either the text or the pattern or both. We also present an experimental   evaluation of these algorithms. The source code is available at http:\/\/www.engr.uconn.edu\/\\(\\sim\\)man09004\/kmis.zip.<\/jats:p>","DOI":"10.3390\/a8020248","type":"journal-article","created":{"date-parts":[[2015,5,26]],"date-time":"2015-05-26T11:07:05Z","timestamp":1432638425000},"page":"248-270","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["On String Matching with Mismatches"],"prefix":"10.3390","volume":"8","author":[{"given":"Marius","family":"Nicolae","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, University of Connecticut, 371 Fairfield Way Unit 4155, Storrs, CT 06269, USA"}]},{"given":"Sanguthevar","family":"Rajasekaran","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, University of Connecticut, 371 Fairfield Way Unit 4155, Storrs, CT 06269, USA"}]}],"member":"1968","published-online":{"date-parts":[[2015,5,26]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1137\/0206024","article-title":"Fast Pattern Matching in Strings","volume":"6","author":"Knuth","year":"1977","journal-title":"SIAM J. Comput."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1145\/360825.360855","article-title":"Efficient string matching: An aid to bibliographic search","volume":"18","author":"Aho","year":"1975","journal-title":"Commun. ACM"},{"key":"ref_3","unstructured":"Fischer, M.J., and Paterson, M.S. (1974). String-Matching and Other Products, Massachusetts Institute of Technology Cambridge Project MAC. Technical Report MAC-TM-41."},{"key":"ref_4","unstructured":"Indyk, P. (1998, January 8\u201311). Faster Algorithms for String Matching Problems: Matching the Convolution Bound. Proceedings of the 39th Symposium on Foundations of Computer Science, Palo Alto, CA, USA."},{"key":"ref_5","unstructured":"Kalai, A. Efficient pattern-matching with don't cares. Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, SODA \u201902."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/j.ipl.2006.08.002","article-title":"Simple deterministic wildcard matching","volume":"101","author":"Clifford","year":"2007","journal-title":"Inf. Process. Lett."},{"key":"ref_7","unstructured":"Cole, R., Hariharan, R., and Indyk, P. (1999, January 17\u201319). Tree pattern matching and subset matching in deterministic O(n log3 n)-time. Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, MD, USA. SODA '99."},{"key":"ref_8","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":"ref_9","doi-asserted-by":"crossref","unstructured":"Navarro, G., and Raffinot, M. (2002). Flexible Pattern Matching in Strings\u2013Practical on-Line Search Algorithms for Texts and Biological Sequences, Cambridge University Press.","DOI":"10.1017\/CBO9781316135228"},{"key":"ref_10","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":"ref_11","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":"ref_12","doi-asserted-by":"crossref","first-page":"468","DOI":"10.1007\/s004530010062","article-title":"A randomized algorithm for approximate string matching","volume":"29","author":"Atallah","year":"2001","journal-title":"Algorithmica"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0020-0190(93)90177-B","article-title":"Fast algorithms for approximately counting mismatches","volume":"48","author":"Karloff","year":"1993","journal-title":"Inf. Process. Lett."},{"key":"ref_14","unstructured":"Clifford, R., Efremenko, K., Porat, B., and Porat, E. (2008). Combinatorial Pattern Matching, Springer."},{"key":"ref_15","unstructured":"Porat, B., and Porat, E. Exact and Approximate Pattern Matching in the Streaming Model. Proceedings of the (FOCS '09) 50th Annual IEEE Symposium on Foundations of Computer Science."},{"key":"ref_16","unstructured":"Porat, E., and Lipsky, O. (2007). Combinatorial Pattern Matching, Springer."},{"key":"ref_17","unstructured":"Clifford, R., Efremenko, K., Porat, E., and Rothschild, A. (2007). Algorithms\u2013ESA 2007, Springer."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1016\/j.ic.2012.02.007","article-title":"Mismatch Sampling","volume":"214","author":"Clifford","year":"2012","journal-title":"Inf. Comput."},{"key":"ref_19","unstructured":"Landau, G.M., and Vishkin, U. (, January 21\u201323). Efficient string matching in the presence of errors. Proceedings of the 26th Annual Symposium on Foundations of Computer Science, Portland, OR, USA."},{"key":"ref_20","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":"ref_21","doi-asserted-by":"crossref","unstructured":"Clifford, R., Efremenko, K., Porat, E., and Rothschild, A. (2009, January 4\u20136). From coding theory to efficient pattern matching. Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, New York, New York, USA. SODA '09.","DOI":"10.1137\/1.9781611973068.85"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"1021","DOI":"10.1016\/j.ipl.2010.08.012","article-title":"A filtering algorithm for k-mismatch with don't cares","volume":"110","author":"Clifford","year":"2010","journal-title":"Inf. Process. Lett."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Fredriksson, K., and Grabowski, S. (2009). Combinatorial Algorithms, Springer-Verlag. Chapter Fast Convolutions and Their Applications in Approximate String Matching.","DOI":"10.1007\/978-3-642-10217-2_26"},{"key":"ref_24","first-page":"241","article-title":"A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the Sum of Observations","volume":"2","author":"Chernoff","year":"1952","journal-title":"Ann. Math. Stat."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Kasai, T., Lee, G., Arimura, H., Arikawa, S., and Park, K. (2001). Linear-Time Longest-Common-Prefix Computation in Suffix Arrays And Its Applications, Springer-Verlag.","DOI":"10.1007\/3-540-48194-X_17"},{"key":"ref_26","first-page":"88","article-title":"The LCA Problem Revisited","volume":"Volume1776","author":"Gonnet","year":"2000","journal-title":"LATIN 2000: Theoretical Informatics"},{"key":"ref_27","unstructured":"Ferragina, P., and Manzini, G. (, January 12\u201314). Opportunistic data structures with applications. Proceedings of the IEEE 41st Annual Symposium on Foundations of Computer Science, Redondo Beach, CA, USA."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1109\/JPROC.2004.840301","article-title":"The Design and Implementation of FFTW3","volume":"93","author":"Frigo","year":"2005","journal-title":"Proc. IEEE"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/j.jda.2014.03.001","article-title":"An elegant algorithm for the construction of suffix arrays","volume":"27","author":"Rajasekaran","year":"2014","journal-title":"J. Discrete Algorithms"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/8\/2\/248\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T20:46:58Z","timestamp":1760215618000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/8\/2\/248"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,5,26]]},"references-count":29,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2015,6]]}},"alternative-id":["a8020248"],"URL":"https:\/\/doi.org\/10.3390\/a8020248","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2015,5,26]]}}}