{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T02:32:35Z","timestamp":1771036355778,"version":"3.50.1"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2024,4,6]],"date-time":"2024-04-06T00:00:00Z","timestamp":1712361600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,4,6]],"date-time":"2024-04-06T00:00:00Z","timestamp":1712361600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["168\/23"],"award-info":[{"award-number":["168\/23"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2018141"],"award-info":[{"award-number":["2018141"]}],"id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002744","name":"Bar-Ilan University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100002744","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["SN COMPUT. SCI."],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Many papers in the intersection of theoretical and applied algorithms show that the simple, asymptotically less efficient algorithm, performs better than the bestcomplex theoretical algorithms on random data or in specialized \u201creal world\u201d applications. This paper considers the Knuth\u2013Morris\u2013Pratt automaton, and shows a counter-intuitive practical result. The classical pattern matching paradigm is that of seeking occurrences of one string\u2014the pattern, in another\u2014the text, where both strings are drawn from an alphabet set <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\Sigma$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03a3<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Assuming the text length is <jats:italic>n<\/jats:italic> and the pattern length is <jats:italic>m<\/jats:italic>, this problem can naively be solved in time <jats:italic>O<\/jats:italic>(<jats:italic>nm<\/jats:italic>). In Knuth, Morris and Pratt\u2019s seminal paper of 1977, an automaton, was developed that allows solving this problem in time <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic>) for any alphabet. This automaton, which we will refer to as the <jats:italic>KMP-automaton<\/jats:italic>, has proven useful in solving many other problems. A notable example is the <jats:italic>parameterized pattern matching<\/jats:italic> model. In this model, a consistent renaming of symbols from <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\Sigma$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03a3<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is allowed in a match. The parameterized matching paradigm has proven useful in problems in software engineering, computer vision, and other applications. It has long been believed that for texts where the symbols are uniformly random, the naive algorithm will perform as well as the KMP algorithm. In this paper, we examine the practical efficiency of the KMP algorithm versus the naive algorithm on a randomly generated text. We analyze the time under various parameters, such as alphabet size, pattern length, and the distribution of pattern occurrences in the text. We do this for both the original exact matching problem and parameterized matching. While the folklore wisdom is vindicated by these findings for the <jats:italic>exact matching case<\/jats:italic>, surprisingly, the KMP algorithm <jats:italic>always<\/jats:italic> works significantly faster than the naive in the parameterized matching case. We check this hypothesis for DNA texts and image data and observe a similar behavior as in the random text. We also show a very structured exact matching case where the automaton is much more efficient.<\/jats:p>","DOI":"10.1007\/s42979-024-02679-7","type":"journal-article","created":{"date-parts":[[2024,4,6]],"date-time":"2024-04-06T13:01:47Z","timestamp":1712408507000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["On the Practical Power of Automata in Pattern Matching"],"prefix":"10.1007","volume":"5","author":[{"given":"Ora","family":"Amir","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3939-337X","authenticated-orcid":false,"given":"Amihood","family":"Amir","sequence":"additional","affiliation":[]},{"given":"Aviezri","family":"Fraenkel","sequence":"additional","affiliation":[]},{"given":"David","family":"Sarne","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,4,6]]},"reference":[{"issue":"5","key":"2679_CR1","doi-asserted-by":"publisher","first-page":"1007","DOI":"10.1137\/S0097539702424496","volume":"35","author":"A Amir","year":"2006","unstructured":"Amir A, Aumann A, Lewenstein M, Porat E. Function matching. SIAM J Comput. 2006;35(5):1007\u201322.","journal-title":"SIAM J Comput"},{"issue":"2","key":"2679_CR2","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1137\/S0097539792226321","volume":"23","author":"A Amir","year":"1994","unstructured":"Amir A, Benson G, Farach M. An alphabet independent approach to two dimensional pattern matching. SIAM J Comp. 1994;23(2):313\u201323.","journal-title":"SIAM J Comp"},{"key":"2679_CR3","unstructured":"Amir A, Church KW, Dar E. Separable attributes: a technique for solving the submatrices character count problem. In: Proceedings of 13th ACM-SIAM symposium on discrete algorithms (SODA); 2002. pp. 400\u2013401."},{"issue":"1","key":"2679_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1995.1047","volume":"118","author":"A Amir","year":"1995","unstructured":"Amir A, Farach M. Efficient 2-dimensional approximate matching of half-rectangular figures. Inf Comput. 1995;118(1):1\u201311.","journal-title":"Inf Comput"},{"key":"2679_CR5","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0020-0190(94)90086-8","volume":"49","author":"A Amir","year":"1994","unstructured":"Amir A, Farach M, Muthukrishnan S. Alphabet dependence in parameterized matching. Inf Process Lett. 1994;49:111\u20135.","journal-title":"Inf Process Lett"},{"issue":"1","key":"2679_CR6","first-page":"1","volume":"84","author":"A Amir","year":"2008","unstructured":"Amir A, Levy A, Reuveni L. The practical efficiency of convolutions in pattern matching algorithms. Fundam Inform. 2008;84(1):1\u201315.","journal-title":"Fundam Inform"},{"issue":"3","key":"2679_CR7","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1016\/j.jda.2006.10.001","volume":"5","author":"A Amir","year":"2007","unstructured":"Amir A, Nor I. Generalized function matching. J Discret Algorithm. 2007;5(3):514\u201323.","journal-title":"J Discret Algorithm"},{"key":"2679_CR8","doi-asserted-by":"crossref","unstructured":"Apostolico A, Galil Z (editors). Pattern Matching Algorithms. Oxford University Press; 1997.","DOI":"10.1093\/oso\/9780195113679.001.0001"},{"issue":"1","key":"2679_CR9","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/j.jda.2006.03.014","volume":"5","author":"A Apostolico","year":"2007","unstructured":"Apostolico A, Lewenstein M, Erd\u00f6s P. Parameterized matching with mismatches. J Discret Algorithm. 2007;5(1):135\u201340.","journal-title":"J Discret Algorithm"},{"issue":"4","key":"2679_CR10","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/BF01215882","volume":"1","author":"GP Babu","year":"1995","unstructured":"Babu GP, Mehtre BM, Kankanhalli MS. Color indexing for efficient image retrieval. Multimed Tools Appl. 1995;1(4):327\u201348.","journal-title":"Multimed Tools Appl"},{"issue":"1","key":"2679_CR11","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1006\/jcss.1996.0003","volume":"52","author":"BS Baker","year":"1996","unstructured":"Baker BS. Parameterized pattern matching: algorithms and applications. J Comput Syst Sci. 1996;52(1):28\u201342.","journal-title":"J Comput Syst Sci"},{"issue":"5","key":"2679_CR12","doi-asserted-by":"publisher","first-page":"1343","DOI":"10.1137\/S0097539793246707","volume":"26","author":"BS Baker","year":"1997","unstructured":"Baker BS. Parameterized duplication in strings: algorithms and an application to software maintenance. SIAM J Comput. 1997;26(5):1343\u201362.","journal-title":"SIAM J Comput"},{"key":"2679_CR13","unstructured":"Baker Brenda\u00a0S. Parameterized pattern matching by Boyer\u2013Moore-type algorithms. In: Proceedings 6th annual ACM-SIAM symposium on discrete algorithms (SODA), ACM\/SIAM; 1995, pp. 541\u2013550."},{"key":"2679_CR14","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1186\/1748-7188-9-9","volume":"9","author":"C Barton","year":"2014","unstructured":"Barton C, Iliopoulos CS, Pissis SP. Fast algorithms for approximate circular string matching. Algorithm Mol Biol. 2014;9:9.","journal-title":"Algorithm Mol Biol"},{"key":"2679_CR15","unstructured":"Baumstark N, Gog S, Heuer T, Labeit J. Practical range minimum queries revisited. In: 16th Int\u2019l symposium on experimental algorithms, (SEA), vol. 75 ,LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik; 2017, pp. 12:1\u201312:16."},{"key":"2679_CR16","doi-asserted-by":"crossref","unstructured":"Cho S, Na JC, Park K, Sim JS. Fast order-preserving pattern matching. In: Proceedings 7th conference combinatorial optimization and applications COCOA, vol. 8287, Lecture Notes in Computer Science, Springer; 2013, pp. 295\u2013305.","DOI":"10.1007\/978-3-319-03780-6_26"},{"key":"2679_CR17","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546853","volume-title":"Algorithms on strings","author":"M Crochemore","year":"2007","unstructured":"Crochemore M, Hancart C, Lecroq T. Algorithms on strings. Cambridge University Press; 2007."},{"key":"2679_CR18","doi-asserted-by":"crossref","unstructured":"Crochemore M, Iliopoulos C.S, Kociumaka T, Kubica M, Langiu A, Pissis SP, Radoszewski J, Rytter W, Walen T. Order-preserving incomplete suffix trees and order-preserving indexes. In: Proceedings 20th international symposium on string processing and information retrieval (SPIRE), vol. 8214, LNCS, Springer; 2013, pp. 84\u201395.","DOI":"10.1007\/978-3-319-02432-5_13"},{"key":"2679_CR19","volume-title":"Text algorithms","author":"M Crochemore","year":"1994","unstructured":"Crochemore M, Rytter W. Text algorithms. Oxford University Press; 1994."},{"issue":"1","key":"2679_CR20","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1287\/opre.50.1.42.17798","volume":"50","author":"GB Dantzig","year":"2002","unstructured":"Dantzig GB. Linear programming. Oper Res. 2002;50(1):42\u20137.","journal-title":"Oper Res"},{"key":"2679_CR21","unstructured":"Dinklage P, Fischer J, Herlez A. Engineering predecessor data structures for dynamic integer sets. In: 19th Int\u2019l symposium on experimental algorithms, (SEA), vol. 190, LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik; 2021, pp. 7:1\u20137:19."},{"key":"2679_CR22","unstructured":"Dinklage P, Fischer J, Herlez A, Kociumaka T, Kurpicz F. Practical performance of space efficient data structures for longest common extensions. In: 28th annual European symposium on algorithms, (ESA), vol. 173, LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik; 2020, pp. 39:1\u201339:20."},{"key":"2679_CR23","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/j.jda.2016.09.002","volume":"43","author":"H Ferrada","year":"2017","unstructured":"Ferrada H, Navarro G. Improved range minimum queries. J Discr Algorithm. 2017;43:72\u201380.","journal-title":"J Discr Algorithm"},{"key":"2679_CR24","unstructured":"Fischer M.J, Paterson M.S. String matching and other products. In: Karp RM, editor. Complexity of computation, SIAM-AMS Proceedings; 1974, vol. 7, pp. 113-125."},{"key":"2679_CR25","unstructured":"Franek F, Islam ASMS, Rahman MS, Smyth WF. Algorithms to compute the lyndon array. In: Holub J, Zd\u00e1rek J, editors, Proceedings of prague stringology Conference;2016, pp. 172\u2013184"},{"issue":"3","key":"2679_CR26","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/j.ipl.2006.06.009","volume":"100","author":"K Fredriksson","year":"2006","unstructured":"Fredriksson K, Mozgovoy M. Efficient parameterized string matching. Inf Process Lett. 2006;100(3):91\u20136.","journal-title":"Inf Process Lett"},{"key":"2679_CR27","doi-asserted-by":"crossref","unstructured":"Hazay C, Lewenstein M, Sokol D. Approximate parameterized matching. In: Proceedings of 12th annual European symposium on algorithms (ESA 2004); 2004. pp. 414\u2013425.","DOI":"10.1007\/978-3-540-30140-0_38"},{"issue":"1","key":"2679_CR28","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/j.jda.2006.10.003","volume":"6","author":"J Holub","year":"2008","unstructured":"Holub J, Smyth WF, Wang S. Fast pattern-matching on indeterminate strings. J Discr Algorithm. 2008;6(1):37\u201350.","journal-title":"J Discr Algorithm"},{"key":"2679_CR29","doi-asserted-by":"crossref","unstructured":"Idury R.M, Sch\u00e4ffer AA. Multiple matching of parameterized patterns. In: Proceedings of 5th combinatorial pattern matching (CPM), vol. 807, LNCS, Springer-Verlag; 1994, pp. 226\u2013239.","DOI":"10.1007\/3-540-58094-8_20"},{"issue":"4","key":"2679_CR30","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1016\/j.jda.2010.08.004","volume":"8","author":"L Ilie","year":"2010","unstructured":"Ilie L, Navarro G, Tinta L. The longest common extension problem revisited and applications to approximate string searching. J Discr Algorithm. 2010;8(4):418\u201328.","journal-title":"J Discr Algorithm"},{"key":"2679_CR31","unstructured":"Kim J, Amir A, Na J.C, Park K., Sim J.S. On representations of ternary order relations in numeric strings. In: Proceedings of 2nd international conference on algorithms for big data (ICABD), vol. 1146, CEUR Workshop Proceedings; 2014. pp. 46\u201352."},{"key":"2679_CR32","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"DE Knuth","year":"1977","unstructured":"Knuth DE, Morris JH, Pratt VR. Fast pattern matching in strings. SIAM J Comp. 1977;6:323\u201350.","journal-title":"SIAM J Comp"},{"key":"2679_CR33","unstructured":"Loukides G, Pissis SP. Bidirectional string anchors: a new string sampling mechanism. In: 29th annual European symposium on algorithms, (ESA), vol. 204, LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik; 2021, pp. 64:1\u201364:21."},{"key":"2679_CR34","unstructured":"Park SG, Amir A, Landau GM, Park K. Cartesian Tree Matching and Indexing. In: Nadia P and Pissis SP, editors, Proceedings 30th symposium on combinatorial pattern matching (CPM), vol. 128, leibniz international proceedings in informatics (LIPIcs); 2019, pp. 16:1\u201316:14."},{"key":"2679_CR35","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/j.tcs.2020.09.014","volume":"845","author":"SG Park","year":"2020","unstructured":"Park SG, Bataa M, Amir A, Landau GM, Park K. Finding patterns and periods in cartesian tree matching. Theor Comput Sci. 2020;845:181\u201397.","journal-title":"Theor Comput Sci"},{"key":"2679_CR36","doi-asserted-by":"crossref","unstructured":"Puglisi SJ, Smyth WF, Turpin A. Inverted files versus suffix arrays for locating patterns in primary memory. In: Proceedings of 13th international symposium on string processing and information retrieval (SPIRE), vol. 4209, LNCS, Springer; 2006, pp. 122\u2013133.","DOI":"10.1007\/11880561_11"},{"key":"2679_CR37","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/j.tcs.2020.10.009","volume":"849","author":"S Song","year":"2021","unstructured":"Song S, Gu G, Ryu C, Faro S, Lecroq T, Park K. Fast algorithms for single and multiple pattern cartesian tree matching. Theor Comput Sci. 2021;849:47\u201363.","journal-title":"Theor Comput Sci"},{"issue":"1","key":"2679_CR38","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/BF00130487","volume":"7","author":"M Swain","year":"1991","unstructured":"Swain M, Ballard D. Color indexing. Int J Comput Vis. 1991;7(1):11\u201332.","journal-title":"Int J Comput Vis"}],"container-title":["SN Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-024-02679-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s42979-024-02679-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-024-02679-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,6]],"date-time":"2024-04-06T13:32:41Z","timestamp":1712410361000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s42979-024-02679-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,6]]},"references-count":38,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2024,4]]}},"alternative-id":["2679"],"URL":"https:\/\/doi.org\/10.1007\/s42979-024-02679-7","relation":{},"ISSN":["2661-8907"],"issn-type":[{"value":"2661-8907","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,6]]},"assertion":[{"value":"12 July 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 February 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 April 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"On behalf of all authors, the corresponding author states that there is no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"400"}}