{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T19:50:26Z","timestamp":1759693826606,"version":"3.41.0"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2019,2,14]],"date-time":"2019-02-14T00:00:00Z","timestamp":1550102400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"G.N.C.S., Istituto Nazionale di Alta Matematica \u201cFrancesco Severi.\u201d"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2019,12,17]]},"abstract":"<jats:p>We present a simple and very efficient algorithm for string matching based on the combination of weak factor recognition and hashing. Despite its quadratic worst-case running time, our algorithm exhibits a sublinear behaviour. We also propose some practical improvements of our algorithm and a variant with a linear worst-case time complexity. Experimental results show that, in most cases, some of the variants of our algorithm obtain the best running times when compared, under various conditions, against the most effective algorithms present in the literature. For instance, in the case of small alphabets and long patterns, the gain in running time is up to 18%. This makes our proposed algorithm one of the most flexible solutions in practical cases.<\/jats:p>","DOI":"10.1145\/3301295","type":"journal-article","created":{"date-parts":[[2019,2,14]],"date-time":"2019-02-14T19:36:17Z","timestamp":1550172977000},"page":"1-20","source":"Crossref","is-referenced-by-count":8,"title":["Linear and Efficient String Matching Algorithms Based on Weak Factor Recognition"],"prefix":"10.1145","volume":"24","author":[{"given":"Domenico","family":"Cantone","sequence":"first","affiliation":[{"name":"University of Catania, Catania, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5937-5796","authenticated-orcid":false,"given":"Simone","family":"Faro","sequence":"additional","affiliation":[{"name":"University of Catania, Catania, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arianna","family":"Pavone","sequence":"additional","affiliation":[{"name":"University of Messina, Messina, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,2,14]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Lecture Notes in Computer Science","volume":"1725","author":"Allauzen C.","unstructured":"C. Allauzen , M. Crochemore , and M. Raffinot . 1999. Factor oracle: A new structure for pattern matching. In SOFSEM\u201999: Theory and Practice of Informatics . Lecture Notes in Computer Science , Vol. 1725 . Springer, 291--306. C. Allauzen, M. Crochemore, and M. Raffinot. 1999. Factor oracle: A new structure for pattern matching. In SOFSEM\u201999: Theory and Practice of Informatics. Lecture Notes in Computer Science, Vol. 1725. Springer, 291--306."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/135239.135243"},{"key":"e_1_2_1_3_1","first-page":"5","article-title":"Fast-search algorithms: New efficient variants of the Boyer-Moore pattern-matching algorithm","volume":"10","author":"Cantone D.","year":"2005","unstructured":"D. Cantone and S. Faro . 2005 . Fast-search algorithms: New efficient variants of the Boyer-Moore pattern-matching algorithm . Journal of Automata, Languages and Combinatorics 10 , 5 -- 6 (2005), 589--608. D. Cantone and S. Faro. 2005. Fast-search algorithms: New efficient variants of the Boyer-Moore pattern-matching algorithm. Journal of Automata, Languages and Combinatorics 10, 5--6 (2005), 589--608.","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2014.07.006"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2011.03.006"},{"volume-title":"Proceedings of the Prague Stringology Conference. 42--50","author":"Cantone D.","key":"e_1_2_1_6_1","unstructured":"D. Cantone , S. Faro , and A. Pavone . 2017. Speeding up string matching by weak factor recognition . In Proceedings of the Prague Stringology Conference. 42--50 . D. Cantone, S. Faro, and A. Pavone. 2017. Speeding up string matching by weak factor recognition. In Proceedings of the Prague Stringology Conference. 42--50."},{"key":"e_1_2_1_7_1","unstructured":"C. Charras and T. Lecroq. 2014. Handbook of Exact String Matching Algorithms. King\u2019s College.   C. Charras and T. Lecroq. 2014. Handbook of Exact String Matching Algorithms. King\u2019s College."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01185427"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13193-6_12"},{"volume-title":"Proceedings of the Stringology Conference. 71--83","author":"Durian B.","key":"e_1_2_1_10_1","unstructured":"B. Durian , T. Chhabra , S. S. Ghuman , T. Hirvola , H. Peltola , and J. Tarhio . 2014. Improved two-way bit-parallel search . In Proceedings of the Stringology Conference. 71--83 . B. Durian, T. Chhabra, S. S. Ghuman, T. Hirvola, H. Peltola, and J. Tarhio. 2014. Improved two-way bit-parallel search. In Proceedings of the Stringology Conference. 71--83."},{"key":"e_1_2_1_11_1","series-title":"Lecture Notes in Computer Science","volume-title":"AlCoB 2016: Algorithms for Computational Biology","author":"Faro S.","unstructured":"S. Faro . 2016. Evaluation and improvement of fast algorithms for exact matching on genome sequences . In AlCoB 2016: Algorithms for Computational Biology . Lecture Notes in Computer Science , Vol. 9702 . Springer , 145--157. S. Faro. 2016. Evaluation and improvement of fast algorithms for exact matching on genome sequences. In AlCoB 2016: Algorithms for Computational Biology. Lecture Notes in Computer Science, Vol. 9702. Springer, 145--157."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2014.07.003"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054109006991"},{"volume-title":"Proceedings of the Stringology Conference. 99--111","author":"Faro S.","key":"e_1_2_1_14_1","unstructured":"S. Faro , T. Lecroq , S. Borz\u00ec , S. Di Mauro , and A. Maggio . 2016. The string matching algorithms research tool . In Proceedings of the Stringology Conference. 99--111 . S. Faro, T. Lecroq, S. Borz\u00ec, S. Di Mauro, and A. Maggio. 2016. The string matching algorithms research tool. In Proceedings of the Stringology Conference. 99--111."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31606-7_13"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30850-5_16"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2431211.2431212"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the","author":"Hume A.","year":"1991","unstructured":"A. Hume and D. Sunday . 1991. Fast string searching . In Proceedings of the Summer 1991 USENIX Conference. 221--234. A. Hume and D. Sunday. 1991. Fast string searching. In Proceedings of the Summer 1991 USENIX Conference. 221--234."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206024"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2007.01.002"},{"key":"e_1_2_1_21_1","volume-title":"CPM 1998: Combinatorial Pattern Matching. Lecture Notes in Computer Science","volume":"1448","author":"Navarro G.","unstructured":"G. Navarro and M. Raffinot . 1998. A bit-parallel approach to suffix automata: Fast extended string matching . In CPM 1998: Combinatorial Pattern Matching. Lecture Notes in Computer Science , Vol. 1448 . Springer, 14--33. G. Navarro and M. Raffinot. 1998. A bit-parallel approach to suffix automata: Fast extended string matching. In CPM 1998: Combinatorial Pattern Matching. Lecture Notes in Computer Science, Vol. 1448. Springer, 14--33."},{"volume-title":"Proceedings of the Stringology Conference. 3--14","author":"Peltola H.","key":"e_1_2_1_22_1","unstructured":"H. Peltola and J. Tarhio . 2011. Variations of Forward-SBNDM . In Proceedings of the Stringology Conference. 3--14 . H. Peltola and J. Tarhio. 2011. Variations of Forward-SBNDM. In Proceedings of the Stringology Conference. 3--14."},{"key":"e_1_2_1_23_1","volume-title":"Report TR-94-17, Department of Computer Science","author":"Wu S.","year":"1994","unstructured":"S. Wu and U. Manber . 1994 . A Fast Algorithm for Multi-Pattern Searching. Report TR-94-17, Department of Computer Science , University of Arizona, Tucson . S. Wu and U. Manber. 1994. A Fast Algorithm for Multi-Pattern Searching. Report TR-94-17, Department of Computer Science, University of Arizona, Tucson."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208029"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3301295","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3301295","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:02:04Z","timestamp":1750208524000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3301295"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2,14]]},"references-count":24,"alternative-id":["10.1145\/3301295"],"URL":"https:\/\/doi.org\/10.1145\/3301295","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2019,2,14]]}}}