{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,8]],"date-time":"2025-10-08T16:00:53Z","timestamp":1759939253867,"version":"3.41.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2012,7,1]],"date-time":"2012-07-01T00:00:00Z","timestamp":1341100800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-BLAN-2009-0011","ANR-BLAN-2010-0204"],"award-info":[{"award-number":["ANR-BLAN-2009-0011","ANR-BLAN-2010-0204"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2012,7]]},"abstract":"<jats:p>In this article, we provide the multivariate generating function counting texts according to their length and to the number of occurrences of words from a finite set. The application of the inclusion-exclusion principle to word counting due to Goulden and Jackson [1979, 1983] is used to derive the result. Unlike some other techniques which suppose that the set of words is<jats:italic>reduced<\/jats:italic>(i.e., where no two words are factor of one another), the finite set can be chosen arbitrarily. Noonan and Zeilberger [1999] already provided a Maple package treating the nonreduced case, without giving an expression of the generating function or a detailed proof. We provide a complete proof validating the use of the inclusion-exclusion principle. Some formul\u00e6 for expected values, variance, and covariance for number of occurrences when considering two arbitrary sets of finite words are given as an application of our methodology.<\/jats:p>","DOI":"10.1145\/2229163.2229175","type":"journal-article","created":{"date-parts":[[2012,7,26]],"date-time":"2012-07-26T14:41:09Z","timestamp":1343313669000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Counting occurrences for a finite set of words"],"prefix":"10.1145","volume":"8","author":[{"given":"Fr\u00e9d\u00e9rique","family":"Bassino","sequence":"first","affiliation":[{"name":"Universit\u00e9 de Paris 13, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Julien","family":"Cl\u00e9ment","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Caen, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pierre","family":"Nicod\u00e8me","sequence":"additional","affiliation":[{"name":"\u00c9cole Polytechnique, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,7,24]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/360825.360855"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(73)90038-1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/eujc.1993.1030"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(83)90062-6"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(83)90012-2"},{"volume-title":"Proceedings of the Colloquium on Mathematics and Computer Science: Algorithms, Trees, Combinatorics and Probabilities. Trends in Mathematics. Birkhauser, 249--265","author":"Bourdon J.","key":"e_1_2_1_6_1","unstructured":"Bourdon , J. and Vall\u00e9e , B . 2002. Generalized pattern matching statistics . In Proceedings of the Colloquium on Mathematics and Computer Science: Algorithms, Trees, Combinatorics and Probabilities. Trends in Mathematics. Birkhauser, 249--265 . Bourdon, J. and Vall\u00e9e, B. 2002. Generalized pattern matching statistics. In Proceedings of the Colloquium on Mathematics and Computer Science: Algorithms, Trees, Combinatorics and Probabilities. Trends in Mathematics. Birkhauser, 249--265."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/11682462_24"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Chomsky N. and Sch\u00fctzenberger M. 1963. The algebraic theory of context-free languages. In Computer in Programming and Formal Languages P. Braffort and D. Hirschberg Eds North Holland 118--161. Chomsky N. and Sch\u00fctzenberger M. 1963. The algebraic theory of context-free languages. In Computer in Programming and Formal Languages P. Braffort and D. Hirschberg Eds North Holland 118--161.","DOI":"10.1016\/S0049-237X(08)72023-8"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Crochemore M. Hancart C. and Lecroq T. 2007. Algorithms on Strings. Cambridge University Press. Crochemore M. Hancart C. and Lecroq T. 2007. Algorithms on Strings. Cambridge University Press.","DOI":"10.1017\/CBO9780511546853"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Crochemore M. and Rytter W. 2002. Jewels of Stringology. World Scientific Publishing Hong-Kong. Crochemore M. and Rytter W. 2002. Jewels of Stringology. World Scientific Publishing Hong-Kong.","DOI":"10.1142\/4838"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1006\/aama.2000.0696"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Flajolet P. and Sedgewick R. 2009. Analytic Combinatorics. Cambridge University Press. Flajolet P. and Sedgewick R. 2009. Analytic Combinatorics. Cambridge University Press.","DOI":"10.1017\/CBO9780511801655"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2-20.3.567"},{"key":"e_1_2_1_14_1","unstructured":"Goulden I. and Jackson D. 1983. Combinatorial Enumeration. John Wiley New York. Goulden I. and Jackson D. 1983. Combinatorial Enumeration. John Wiley New York."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(81)90038-8"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(81)90005-4"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(94)90065-5"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1080\/10236190500376326"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1080\/10236190902841976"},{"volume-title":"Applied Combinatorics on Words. Encyclopedia of Mathematics","author":"Lothaire M.","key":"e_1_2_1_20_1","unstructured":"Lothaire , M. 2005. Applied Combinatorics on Words. Encyclopedia of Mathematics , Cambridge University Press . Lothaire, M. 2005. Applied Combinatorics on Words. Encyclopedia of Mathematics, Cambridge University Press."},{"key":"e_1_2_1_21_1","first-page":"1","article-title":"Regexpcount, a symbolic package for counting problems on regular expressions and words","volume":"56","author":"Nicod\u00e8me P.","year":"2003","unstructured":"Nicod\u00e8me , P. 2003 . Regexpcount, a symbolic package for counting problems on regular expressions and words . Fundam. Inf. 56 , 1 - 2 , 71--88. Nicod\u00e8me, P. 2003. Regexpcount, a symbolic package for counting problems on regular expressions and words. Fundam. Inf. 56, 1-2, 71--88.","journal-title":"Fundam. Inf."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00264-X"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1023023831510"},{"key":"e_1_2_1_24_1","first-page":"4","article-title":"The Goulden-Jackson Method: Extensions, Applications and Implementations","volume":"5","author":"Noonan J.","year":"1999","unstructured":"Noonan , J. and Zeilberger , D. 1999 . The Goulden-Jackson Method: Extensions, Applications and Implementations . J. Diff. Equat. Appl. 5 , 4 - 5 , 355--377. Noonan, J. and Zeilberger, D. 1999. The Goulden-Jackson Method: Extensions, Applications and Implementations. J. Diff. Equat. Appl. 5, 4-5, 355--377.","journal-title":"J. Diff. Equat. Appl."},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1111\/j.2517-6161.1995.tb02025.x","article-title":"Finding words with unexpected frequencies in deoxyribonucleic acid sequences","volume":"57","author":"Prum B.","year":"1995","unstructured":"Prum , B. , Rodolphe , F. , and de Turckheim , E. 1995 . Finding words with unexpected frequencies in deoxyribonucleic acid sequences . J. Royal Statist. Soc. B 57 , 1, 205 -- 220 . Prum, B., Rodolphe, F., and de Turckheim, E. 1995. Finding words with unexpected frequencies in deoxyribonucleic acid sequences. J. Royal Statist. Soc. B 57, 1, 205--220.","journal-title":"J. Royal Statist. Soc. B"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(00)00195-5"},{"volume-title":"Proceedings of the Compression and Complexity of Sequences (SEQUENCES'97)","author":"R\u00e9gnier M.","key":"e_1_2_1_27_1","unstructured":"R\u00e9gnier , M. and Szpankowski , W . 1997. On the approximate pattern occurrences in a text . In Proceedings of the Compression and Complexity of Sequences (SEQUENCES'97) Conference. IEEE Computer Society, LOS Alamitos, CA, 253. R\u00e9gnier, M. and Szpankowski, W. 1997. On the approximate pattern occurrences in a text. In Proceedings of the Compression and Complexity of Sequences (SEQUENCES'97) Conference. IEEE Computer Society, LOS Alamitos, CA, 253."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009244"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.1998.5.223"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1089\/10665270050081360"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1239\/aap\/1175266472"},{"key":"e_1_2_1_32_1","unstructured":"Sedgewick R. and Flajolet P. 1996. An Introduction to the Analysis of Algorithms. Addison-Wesley. Sedgewick R. and Flajolet P. 1996. An Introduction to the Analysis of Algorithms. Addison-Wesley."},{"key":"e_1_2_1_33_1","series-title":"Series in Discrete Mathematics and Optimization","volume-title":"Average Case Analysis of Algorithms on Sequences","author":"Szpankowski W.","unstructured":"Szpankowski , W. 2001. Average Case Analysis of Algorithms on Sequences . Series in Discrete Mathematics and Optimization , John Wiley & amp; Sons. Szpankowski, W. 2001. Average Case Analysis of Algorithms on Sequences. Series in Discrete Mathematics and Optimization, John Wiley &amp; Sons."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02679622"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1080\/10236190512331329432"},{"key":"e_1_2_1_36_1","first-page":"05","article-title":"The umbral transfer-matrix method. V. The Goulden-Jackson cluster method for infinitely many mistakes","volume":"2","author":"Zeilberger D.","year":"2002","unstructured":"Zeilberger , D. 2002 . The umbral transfer-matrix method. V. The Goulden-Jackson cluster method for infinitely many mistakes . Integ. Electron. J. Combin. Number Theory 2 , 05 . Zeilberger, D. 2002. The umbral transfer-matrix method. V. The Goulden-Jackson cluster method for infinitely many mistakes. Integ. Electron. J. Combin. Number Theory 2, 05.","journal-title":"Integ. Electron. J. Combin. Number Theory"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2229163.2229175","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2229163.2229175","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:48:52Z","timestamp":1750236532000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2229163.2229175"}},"subtitle":["Combinatorial methods"],"short-title":[],"issued":{"date-parts":[[2012,7]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,7]]}},"alternative-id":["10.1145\/2229163.2229175"],"URL":"https:\/\/doi.org\/10.1145\/2229163.2229175","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2012,7]]},"assertion":[{"value":"2009-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-07-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}