{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:20:08Z","timestamp":1740122408867,"version":"3.37.3"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2018,5,21]],"date-time":"2018-05-21T00:00:00Z","timestamp":1526860800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004569","name":"Ministerstwo Nauki i Szkolnictwa Wy\u017cszego","doi-asserted-by":"publisher","award":["DI2012 017942"],"award-info":[{"award-number":["DI2012 017942"]}],"id":[{"id":"10.13039\/501100004569","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2014\/13\/B\/ST6\/00770"],"award-info":[{"award-number":["2014\/13\/B\/ST6\/00770"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2019,2]]},"DOI":"10.1007\/s10878-018-0300-z","type":"journal-article","created":{"date-parts":[[2018,5,21]],"date-time":"2018-05-21T05:48:32Z","timestamp":1526881712000},"page":"501-522","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Efficient enumeration of non-equivalent squares in partial words with few holes"],"prefix":"10.1007","volume":"37","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6024-1557","authenticated-orcid":false,"given":"Panagiotis","family":"Charalampopoulos","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1087-1419","authenticated-orcid":false,"given":"Maxime","family":"Crochemore","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3909-0077","authenticated-orcid":false,"given":"Costas S.","family":"Iliopoulos","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2477-1702","authenticated-orcid":false,"given":"Tomasz","family":"Kociumaka","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1445-1932","authenticated-orcid":false,"given":"Solon P.","family":"Pissis","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0067-6401","authenticated-orcid":false,"given":"Jakub","family":"Radoszewski","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9162-6724","authenticated-orcid":false,"given":"Wojciech","family":"Rytter","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7369-3309","authenticated-orcid":false,"given":"Tomasz","family":"Wale\u0144","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,5,21]]},"reference":[{"key":"300_CR1","doi-asserted-by":"publisher","unstructured":"Bannai H, Inenaga S, K\u00f6ppl D (2017) Computing all distinct squares in linear time for integer alphabets. In: K\u00e4rkk\u00e4inen J, Radoszewski J, Rytter W (eds) 28th Annual symposium on combinatorial pattern matching, CPM 2017, LIPIcs, vol\u00a078. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pp 22:1\u201322:18. \n                    https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2017.22","DOI":"10.4230\/LIPIcs.CPM.2017.22"},{"issue":"4","key":"300_CR2","doi-asserted-by":"publisher","first-page":"767","DOI":"10.1051\/ita\/2009019","volume":"43","author":"F Blanchet-Sadri","year":"2009","unstructured":"Blanchet-Sadri F, Merca\u015f R (2009) A note on the number of squares in a partial word with one hole. Inform Th\u00e9or Appl 43(4):767\u2013774. \n                    https:\/\/doi.org\/10.1051\/ita\/2009019","journal-title":"Inform Th\u00e9or Appl"},{"key":"300_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2012.01.012","volume":"428","author":"F Blanchet-Sadri","year":"2012","unstructured":"Blanchet-Sadri F, Merca\u015f R (2012) The three-squares lemma for partial words with one hole. Theor Comput Sci 428:1\u20139. \n                    https:\/\/doi.org\/10.1016\/j.tcs.2012.01.012","journal-title":"Theor Comput Sci"},{"issue":"2","key":"300_CR4","first-page":"465","volume":"19","author":"F Blanchet-Sadri","year":"2009","unstructured":"Blanchet-Sadri F, Merca\u015f R, Scott G (2009) Counting distinct squares in partial words. Acta Cybern 19(2):465\u2013477","journal-title":"Acta Cybern"},{"key":"300_CR5","doi-asserted-by":"publisher","unstructured":"Blanchet-Sadri F, Jiao Y, Machacek JM, Quigley J, Zhang X (2014a) Squares in partial words. Theor Comput Sci 530:42\u201357. \n                    https:\/\/doi.org\/10.1007\/978-3-642-31653-1_36","DOI":"10.1007\/978-3-642-31653-1_36"},{"key":"300_CR6","doi-asserted-by":"publisher","unstructured":"Blanchet-Sadri F, Nikkel J, Quigley JD, Zhang X (2014b) Computing primitively-rooted squares and runs in partial words. In: Kratochv\u00edl J, Miller M, Froncek D (eds) Combinatorial algorithms, IWOCA 2014. Lecture notes in computer science, vol 8986. Springer, pp 86\u201397. \n                    https:\/\/doi.org\/10.1007\/978-3-319-19315-1_8","DOI":"10.1007\/978-3-319-19315-1_8"},{"key":"300_CR7","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.dam.2014.12.003","volume":"185","author":"F Blanchet-Sadri","year":"2015","unstructured":"Blanchet-Sadri F, Bodnar M, Nikkel J, Quigley JD, Zhang X (2015) Squares and primitivity in partial words. Discrete Appl Math 185:26\u201337. \n                    https:\/\/doi.org\/10.1016\/j.dam.2014.12.003","journal-title":"Discrete Appl Math"},{"key":"300_CR8","doi-asserted-by":"publisher","unstructured":"Charalampopoulos P, Crochemore M, Iliopoulos C.S, Kociumaka T, Pissis S.P, Radoszewski J, Rytter W, Wale\u0144 T (2017) Efficient enumeration of non-equivalent squares in partial words with few holes. In: Cao Y, Chen Y (eds) Proceedings of the 23rd international conference on computing and combinatorics, COCOON 2017. Lecture notes in computer science, vol 10392. Springer, pp 99\u2013111. \n                    https:\/\/doi.org\/10.1007\/978-3-319-62389-4_9","DOI":"10.1007\/978-3-319-62389-4_9"},{"issue":"5","key":"300_CR9","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1007\/BF01190846","volume":"13","author":"M Crochemore","year":"1995","unstructured":"Crochemore M, Rytter W (1995) Squares, cubes, and time-space efficient string searching. Algorithmica 13(5):405\u2013425. \n                    https:\/\/doi.org\/10.1007\/BF01190846","journal-title":"Algorithmica"},{"key":"300_CR10","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/j.tcs.2013.11.018","volume":"521","author":"M Crochemore","year":"2014","unstructured":"Crochemore M, Iliopoulos CS, Kubica M, Radoszewski J, Rytter W, Wale\u0144 T (2014) Extracting powers and periods in a word from its runs structure. Theor Comput Sci 521:29\u201341. \n                    https:\/\/doi.org\/10.1016\/j.tcs.2013.11.018","journal-title":"Theor Comput Sci"},{"key":"300_CR11","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1016\/j.dam.2014.08.016","volume":"180","author":"A Deza","year":"2015","unstructured":"Deza A, Franek F, Thierry A (2015) How many double squares can a string contain? Discrete Appl Math 180:52\u201369. \n                    https:\/\/doi.org\/10.1016\/j.dam.2014.08.016","journal-title":"Discrete Appl Math"},{"key":"300_CR12","doi-asserted-by":"publisher","unstructured":"Diaconu A, Manea F, Tiseanu C (2009) Combinatorial queries and updates on partial words. In: Kuty\u0142owski M, Charatonik W, G\u0229bala M (eds) Fundamentals of computation theory, FCT 2009. Lecture notes in computer science, vol 5699. Springer, pp 96\u2013108. \n                    https:\/\/doi.org\/10.1007\/978-3-642-03409-1_10","DOI":"10.1007\/978-3-642-03409-1_10"},{"key":"300_CR13","doi-asserted-by":"crossref","unstructured":"Farach M (1997) Optimal suffix tree construction with large alphabets. In: FOCS. IEEE Computer Society, pp 137\u2013143","DOI":"10.1109\/SFCS.1997.646102"},{"issue":"1","key":"300_CR14","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1006\/jcta.1997.2843","volume":"82","author":"AS Fraenkel","year":"1998","unstructured":"Fraenkel AS, Simpson J (1998) How many squares can a string contain? J Comb Theory Ser A 82(1):112\u2013120. \n                    https:\/\/doi.org\/10.1006\/jcta.1997.2843","journal-title":"J Comb Theory Ser A"},{"key":"300_CR15","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on strings, trees, and sequences\u2014computer science and computational biology","author":"D Gusfield","year":"1997","unstructured":"Gusfield D (1997) Algorithms on strings, trees, and sequences\u2014computer science and computational biology. Cambridge University Press, Cambridge"},{"issue":"4","key":"300_CR16","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1016\/j.jcss.2004.03.004","volume":"69","author":"D Gusfield","year":"2004","unstructured":"Gusfield D, Stoye J (2004) Linear time algorithms for finding and representing all the tandem repeats in a string. J Comput Syst Sci 69(4):525\u2013546. \n                    https:\/\/doi.org\/10.1016\/j.jcss.2004.03.004","journal-title":"J Comput Syst Sci"},{"issue":"1","key":"300_CR17","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1051\/ita\/2010008","volume":"44","author":"V Halava","year":"2010","unstructured":"Halava V, Harju T, K\u00e4rki T (2010) On the number of squares in partial words. RAIRO\u2014Theor Inform Appl 44(1):125\u2013138. \n                    https:\/\/doi.org\/10.1051\/ita\/2010008","journal-title":"RAIRO\u2014Theor Inform Appl"},{"issue":"1","key":"300_CR18","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/j.jcta.2005.01.006","volume":"112","author":"L Ilie","year":"2005","unstructured":"Ilie L (2005) A simple proof that a word of length \n                    \n                      \n                    \n                    $$n$$\n                    \n                      \n                        n\n                      \n                    \n                   has at most \n                    \n                      \n                    \n                    $$2n$$\n                    \n                      \n                        \n                          2\n                          n\n                        \n                      \n                    \n                   distinct squares. J Comb Theory Ser A 112(1):163\u2013164. \n                    https:\/\/doi.org\/10.1016\/j.jcta.2005.01.006","journal-title":"J Comb Theory Ser A"},{"key":"300_CR19","doi-asserted-by":"publisher","unstructured":"Kociumaka T (2016) Minimal suffix and rotation of a substring in optimal time. In: Grossi R, Lewenstein M (eds) Combinatorial pattern matching, CPM 2016. LIPIcs, vol\u00a054. Schloss Dagstuhl, pp 28:1\u201328:12. \n                    https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2016.28","DOI":"10.4230\/LIPIcs.CPM.2016.28"},{"issue":"3","key":"300_CR20","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1016\/0196-6774(84)90021-X","volume":"5","author":"MG Main","year":"1984","unstructured":"Main MG, Lorentz RJ (1984) An \n                    \n                      \n                    \n                    $$O(n \\log n)$$\n                    \n                      \n                        \n                          O\n                          (\n                          n\n                          log\n                          n\n                          )\n                        \n                      \n                    \n                   algorithm for finding all repetitions in a string. J Algorithms 5(3):422\u2013432. \n                    https:\/\/doi.org\/10.1016\/0196-6774(84)90021-X","journal-title":"J Algorithms"},{"key":"300_CR21","doi-asserted-by":"publisher","unstructured":"Manea F, Tiseanu C (2010) Hard counting problems for partial words. In: Dediu A, Fernau H, Mart\u00edn-Vide C (eds) Language and automata theory and applications, LATA 2010. Lecture notes in computer science, vol 6031. Springer, pp 426\u2013438. \n                    https:\/\/doi.org\/10.1007\/978-3-642-13089-2_36","DOI":"10.1007\/978-3-642-13089-2_36"},{"key":"300_CR22","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1016\/j.dam.2014.07.017","volume":"179","author":"F Manea","year":"2014","unstructured":"Manea F, Merca\u015f R, Tiseanu C (2014) An algorithmic toolbox for periodic partial words. Discrete Appl Math 179:174\u2013192. \n                    https:\/\/doi.org\/10.1016\/j.dam.2014.07.017","journal-title":"Discrete Appl Math"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-018-0300-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-018-0300-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-018-0300-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T16:17:09Z","timestamp":1558541829000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-018-0300-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,5,21]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,2]]}},"alternative-id":["300"],"URL":"https:\/\/doi.org\/10.1007\/s10878-018-0300-z","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2018,5,21]]},"assertion":[{"value":"21 May 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}