{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,8]],"date-time":"2026-02-08T12:44:23Z","timestamp":1770554663223,"version":"3.49.0"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2020,4,21]],"date-time":"2020-04-21T00:00:00Z","timestamp":1587427200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ISF","award":["1278\/16, 824\/17, and 1926\/19"],"award-info":[{"award-number":["1278\/16, 824\/17, and 1926\/19"]}]},{"name":"BSF","award":["2018364"],"award-info":[{"award-number":["2018364"]}]},{"name":"ERC grant MPM","award":["683064"],"award-info":[{"award-number":["683064"]}]},{"name":"Foundation for Polish Science project \u201cAlgorithms for text processing with errors and uncertainties\u201d","award":["POIR.04.04.00-00-24BA\/16"],"award-info":[{"award-number":["POIR.04.04.00-00-24BA\/16"]}]},{"name":"EU's Horizon 2020 Research and Innovation Programme"},{"name":"European Union under the European Regional Development Fund"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2020,4,30]]},"abstract":"<jats:p>\n            A seed in a word is a relaxed version of a period in which the occurrences of the repeating subword may overlap. Our first contribution is a linear-time algorithm computing a linear-size representation of all seeds of a word (the number of seeds might be quadratic). In particular, one can easily derive the shortest seed and the number of seeds from our representation. Thus, we solve an open problem stated in a survey by Smyth from 2000 and improve upon a previous\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            )-time algorithm by Iliopoulos et al. from 1996. Our approach is based on combinatorial relations between seeds and subword complexity (used here for the first time in the context of seeds).\n          <\/jats:p>\n          <jats:p>In previous papers, compact representations of seeds consisted of two independent parts operating on the suffix tree of the input word and the suffix tree of its reverse, respectively. Our second contribution is a novel and significantly simpler representation of all seeds that avoids dealing with the suffix tree of the reversed word. This result is also of independent interest from a combinatorial point of view.<\/jats:p>\n          <jats:p>A preliminary version of this work, with a much more complex algorithm constructing a representation of seeds on two suffix trees, was presented at the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201912).<\/jats:p>","DOI":"10.1145\/3386369","type":"journal-article","created":{"date-parts":[[2020,5,4]],"date-time":"2020-05-04T09:50:56Z","timestamp":1588585856000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["A Linear-Time Algorithm for Seeds Computation"],"prefix":"10.1145","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2477-1702","authenticated-orcid":false,"given":"Tomasz","family":"Kociumaka","sequence":"first","affiliation":[{"name":"University of Warsaw and Bar-Ilan University, Ramat-Gan, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcin","family":"Kubica","sequence":"additional","affiliation":[{"name":"University of Warsaw, Banacha, Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0067-6401","authenticated-orcid":false,"given":"Jakub","family":"Radoszewski","sequence":"additional","affiliation":[{"name":"University of Warsaw, Banacha, Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wojciech","family":"Rytter","sequence":"additional","affiliation":[{"name":"University of Warsaw, Banacha, Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tomasz","family":"Wale\u0144","sequence":"additional","affiliation":[{"name":"University of Warsaw, Banacha, Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,4,21]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019, N. Pisanti and S. P. Pissis (Eds.)","volume":"128","author":"Alamro Hayam","year":"2019"},{"key":"e_1_2_1_2_1","volume-title":"30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019, N. Pisanti and S. P. Pissis (Eds.)","volume":"128","author":"Alzamel Mai","year":"2019"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1240233.1240242"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-019-00559-8"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2019.05.020"},{"key":"e_1_2_1_6_1","volume-title":"29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018, G. Navarro, D. Sankoff, and B. Zhu (Eds.)","volume":"105","author":"Amir Amihood","year":"2018"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90159-Q"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90056-N"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2019.104462"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1162"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1993.1018"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90111-8"},{"key":"e_1_2_1_13_1","volume-title":"11th Annual Symposium on Combinatorial Pattern Matching, CPM 2000 (LNCS), Raffaele Giancarlo and David Sankoff (Eds.)","volume":"1848","author":"Brodal Gerth St\u00f8lting"},{"key":"e_1_2_1_14_1","first-page":"5","article-title":"Approximate seeds of strings","volume":"10","author":"Christodoulakis Manolis","year":"2005","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.12.078"},{"key":"e_1_2_1_16_1","first-page":"5","article-title":"The complexity of the minimum k-cover problem","volume":"10","author":"Cole Richard","year":"2005","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","volume-title":"Algorithms on Strings","author":"Crochemore Maxime","DOI":"10.1017\/CBO9780511546853"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Maxime Crochemore and Wojciech Rytter. 2003. Jewels of Stringology. World Scientific. DOI:https:\/\/doi.org\/10.1142\/4838  Maxime Crochemore and Wojciech Rytter. 2003. Jewels of Stringology. World Scientific. DOI:https:\/\/doi.org\/10.1142\/4838","DOI":"10.1142\/4838"},{"key":"e_1_2_1_19_1","unstructured":"Patryk Czajka and Jakub Radoszewski. 2019. Experimental evaluation of algorithms for computing quasiperiods. arxiv:1909.11336.  Patryk Czajka and Jakub Radoszewski. 2019. Experimental evaluation of algorithms for computing quasiperiods. arxiv:1909.11336."},{"key":"e_1_2_1_20_1","volume-title":"7th Annual Symposium on Combinatorial Pattern Matching, CPM 1996 (LNCS), Daniel S. Hirschberg and Eugene W. Myers (Eds.)","volume":"1075","author":"Farach Martin"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/355541.355547"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1965-0174934-9"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.08.013"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90014-5"},{"key":"e_1_2_1_25_1","volume-title":"22th Annual European Symposium on Algorithms, ESA 2014 (LNCS), Andreas S. Schulz and Dorothea Wagner (Eds.)","volume":"8737","author":"Gawrychowski Pawe\u0142"},{"key":"e_1_2_1_26_1","volume-title":"2nd International Conference on Algorithmic Aspects in Information and Management, AAIM 2006 (LNCS), Siu-Wing Cheng and Chung Keung Poon (Eds.)","volume":"4041","author":"Guo Qing"},{"key":"e_1_2_1_27_1","volume-title":"13th International Conference on String Processing and Information Retrieval, SPIRE 2006 (LNCS), Fabio Crestani, Paolo Ferragina, and Mark Sanderson (Eds.)","volume":"4209","author":"Guo Qing","year":"1880"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2007.02.020"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2019.01.015"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 20th Conference on Theory and Practice of Information Technologies (ITAT\u201908)","author":"Guth Ond\u0159ej","year":"2008"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45655-4_35"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2011.02.009"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01955677"},{"key":"e_1_2_1_34_1","first-page":"213","article-title":"Quasiperiodicity: From detection to normal forms","volume":"4","author":"Iliopoulos Costas S.","year":"1999","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 9th Australasian Workshop on Combinatorial Algorithms (AWOCA\u201998)","author":"Costas"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1217856.1217858"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.86"},{"key":"e_1_2_1_38_1","unstructured":"Tomasz Kociumaka Gonzalo Navarro and Nicola Prezza. 2019. Towards a definitive measure of repetitiveness. arxiv:1910.02151.  Tomasz Kociumaka Gonzalo Navarro and Nicola Prezza. 2019. Towards a definitive measure of repetitiveness. arxiv:1910.02151."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2016.11.035"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9915-3"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS\u201999)","author":"Roman","year":"1999"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0062-2"},{"key":"e_1_2_1_43_1","volume-title":"Algebraic Combinatorics on Words. Encyclopedia of Mathematics and Its Applications","author":"Lothaire M.","edition":"1"},{"key":"e_1_2_1_44_1","volume-title":"Applied Combinatorics on Words. Encyclopedia of Mathematics and Its Applications","author":"Lothaire M.","edition":"1"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222058"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)00045-X"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)00235-Q"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9618-6"},{"key":"e_1_2_1_50_1","first-page":"16","article-title":"Finding approximate covers of strings","volume":"29","author":"Sim Jeong Seop","year":"2002","journal-title":"Journal of KIISE: Computer Systems and Theory"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00067-0"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/SWAT.1973.13"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3386369","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3386369","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:32:04Z","timestamp":1750195924000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3386369"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,21]]},"references-count":51,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,4,30]]}},"alternative-id":["10.1145\/3386369"],"URL":"https:\/\/doi.org\/10.1145\/3386369","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,4,21]]},"assertion":[{"value":"2019-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-04-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}