{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T07:54:47Z","timestamp":1776930887731,"version":"3.51.2"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2007,2,9]],"date-time":"2007-02-09T00:00:00Z","timestamp":1170979200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2007,2,9]]},"abstract":"<jats:p>\n            We present three algorithms for exact string matching of multiple patterns. Our algorithms are filtering methods, which apply\n            <jats:italic>q<\/jats:italic>\n            -grams and bit parallelism. We ran extensive experiments with them and compared them with various versions of earlier algorithms, e.g., different trie implementations of the Aho--Corasick algorithm. All of our algorithms appeared to be substantially faster than earlier solutions for sets of 1,000--10,000 patterns and the good performance of two of them continues to 100,000 patterns. The gain is because of the improved filtering efficiency caused by\n            <jats:italic>q<\/jats:italic>\n            -grams.\n          <\/jats:p>","DOI":"10.1145\/1187436.1187438","type":"journal-article","created":{"date-parts":[[2007,1,16]],"date-time":"2007-01-16T19:38:29Z","timestamp":1168976309000},"source":"Crossref","is-referenced-by-count":20,"title":["Multipattern string matching with\n            <i>q<\/i>\n            -grams"],"prefix":"10.1145","volume":"11","author":[{"given":"Leena","family":"Salmela","sequence":"first","affiliation":[{"name":"Helsinki University of Technology, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jorma","family":"Tarhio","sequence":"additional","affiliation":[{"name":"Helsinki University of Technology, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jari","family":"Kyt\u00f6joki","sequence":"additional","affiliation":[{"name":"Helsinki University of Technology, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2007,2,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216067"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/360825.360855"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380190305"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/135239.135243"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/359842.359859"},{"key":"e_1_2_1_6_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 6th International Colloquium on Automata, Languages and Programming","author":"Commentz-Walter B."},{"key":"e_1_2_1_7_1","unstructured":"Crochemore M. and Rytter W. 1994. Text Algorithms. Oxford University Press New York.   Crochemore M. and Rytter W. 1994. Text Algorithms. Oxford University Press New York."},{"key":"e_1_2_1_8_1","volume-title":"Tech. Rep. CS2001-0670","author":"Fisk M."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of 9th Symposium on String Processing and Information Retrieval (SPIRE'02)","volume":"2476","author":"Fredriksson K.","year":"2002"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of 12th Symposium on String Processing and Information Retrieval (SPIRE'05)","volume":"3772","author":"Fredriksson K."},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 1st SIAM International Conference on Data Mining.","author":"Gum B."},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1002\/spe.4380100608","article-title":"Practical fast searching in strings","volume":"10","author":"Horspool N.","year":"1980","journal-title":"Softw. Pract. Exper."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.312.0249"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of 17th AoM\/IAoM Conference on Computer Science.","author":"Kim S."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the IASTED International Conference on Communications and Computer Networks (CCN). ACTA Press. Calgary, AB, Canada, 146--152","author":"Markatos E. P."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of 7th Combinatorial Pattern Matching (CPM'96)","volume":"1075","author":"Muth R."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/351827.384246"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Navarro G. and Raffinot M. 2002. Flexible pattern matching in strings. Cambridge University Press Cambrige UK.   Navarro G. and Raffinot M. 2002. Flexible pattern matching in strings. Cambridge University Press Cambrige UK.","DOI":"10.1017\/CBO9781316135228"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of 10th Symposium on String Processing and Information Retrieval (SPIRE'03)","volume":"2857","author":"Peltola H."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of 12th Symposium on String Processing and Information Retrieval (SPIRE'05)","volume":"3772","author":"Ping L."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the IEEE Infocom Conference.","author":"Tuck N."},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the Usenix","author":"Wu S.","year":"1992"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/135239.135244"},{"key":"e_1_2_1_24_1","volume-title":"Tech. Rep. TR-94-17, Department of Computer Science","author":"Wu S.","year":"1994"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/66451.66459"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1187436.1187438","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1187436.1187438","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:08:11Z","timestamp":1750262891000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1187436.1187438"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,2,9]]},"references-count":25,"alternative-id":["10.1145\/1187436.1187438"],"URL":"https:\/\/doi.org\/10.1145\/1187436.1187438","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,2,9]]}}}