{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,8]],"date-time":"2026-02-08T15:42:51Z","timestamp":1770565371996,"version":"3.49.0"},"publisher-location":"Cham","reference-count":40,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031721991","type":"print"},{"value":"9783031722004","type":"electronic"}],"license":[{"start":{"date-parts":[[2024,9,19]],"date-time":"2024-09-19T00:00:00Z","timestamp":1726704000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,9,19]],"date-time":"2024-09-19T00:00:00Z","timestamp":1726704000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-72200-4_21","type":"book-chapter","created":{"date-parts":[[2024,9,18]],"date-time":"2024-09-18T19:01:50Z","timestamp":1726686110000},"page":"272-288","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Computing String Covers in\u00a0Sublinear Time"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0067-6401","authenticated-orcid":false,"given":"Jakub","family":"Radoszewski","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1988-3507","authenticated-orcid":false,"given":"Wiktor","family":"Zuba","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,9,19]]},"reference":[{"issue":"1","key":"21_CR1","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/0020-0190(91)90056-N","volume":"39","author":"A Apostolico","year":"1991","unstructured":"Apostolico, A., Farach, M., Iliopoulos, C.S.: Optimal superprimitivity testing for strings. Inf. Process. Lett. 39(1), 17\u201320 (1991). https:\/\/doi.org\/10.1016\/0020-0190(91)90056-N","journal-title":"Inf. Process. Lett."},{"key":"21_CR2","doi-asserted-by":"publisher","unstructured":"Bannai, H., Ellert, J.: Lyndon arrays in sublinear time. In: G\u00f8rtz, I.L., Farach-Colton, M., Puglisi, S.J., Herman, G. (eds.) 31st Annual European Symposium on Algorithms, ESA 2023, 4\u20136 September 2023, Amsterdam. LIPIcs, vol.\u00a0274, pp. 14:1\u201314:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2023). https:\/\/doi.org\/10.4230\/LIPICS.ESA.2023.14","DOI":"10.4230\/LIPICS.ESA.2023.14"},{"key":"21_CR3","doi-asserted-by":"publisher","unstructured":"Bannai, H., Mieno, T., Nakashima, Y.: Lyndon words, the three squares lemma, and primitive squares. In: Boucher, C., Thankachan, S.V. (eds.) SPIRE 2020. LNCS, vol. 12303, pp. 265\u2013273. Springer, Heidelberg (2020). https:\/\/doi.org\/10.1007\/978-3-030-59212-7_19","DOI":"10.1007\/978-3-030-59212-7_19"},{"key":"21_CR4","doi-asserted-by":"publisher","unstructured":"Belazzougui, D., Kosolobov, D., Puglisi, S.J., Raman, R.: Weighted ancestors in suffix trees revisited. In: Gawrychowski, P., Starikovskaya, T. (eds.) 32nd Annual Symposium on Combinatorial Pattern Matching, CPM 2021, 5\u20137 July 2021, Wroc\u0142aw. LIPIcs, vol.\u00a0191, pp. 8:1\u20138:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021). https:\/\/doi.org\/10.4230\/LIPICS.CPM.2021.8","DOI":"10.4230\/LIPICS.CPM.2021.8"},{"key":"21_CR5","doi-asserted-by":"publisher","unstructured":"Ben-Kiki, O., Bille, P., Breslauer, D., Gasieniec, L., Grossi, R., Weimann, O.: Towards optimal packed string matching. Theor. Comput. Sci. 525, 111\u2013129 (2014). https:\/\/doi.org\/10.1016\/J.TCS.2013.06.013","DOI":"10.1016\/J.TCS.2013.06.013"},{"key":"21_CR6","doi-asserted-by":"publisher","unstructured":"Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: Gonnet, G.H., Panario, D., Viola, A. (eds.) LATIN 2000. LNCS, vol.\u00a01776, pp. 88\u201394. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/10719839_9","DOI":"10.1007\/10719839_9"},{"issue":"6","key":"21_CR7","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1016\/0020-0190(92)90111-8","volume":"44","author":"D Breslauer","year":"1992","unstructured":"Breslauer, D.: An on-line string superprimitivity test. Inf. Process. Lett. 44(6), 345\u2013347 (1992). https:\/\/doi.org\/10.1016\/0020-0190(92)90111-8","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"21_CR8","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/BF01294132","volume":"14","author":"D Breslauer","year":"1995","unstructured":"Breslauer, D., Galil, Z.: Finding all periods and initial palindromes of a string in parallel. Algorithmica 14(4), 355\u2013366 (1995). https:\/\/doi.org\/10.1007\/BF01294132","journal-title":"Algorithmica"},{"key":"21_CR9","unstructured":"de\u00a0Bruijn, N.G.: A combinatorial problem. Indagationes Math. 8, 461\u2013467 (1946). http:\/\/www.dwc.knaw.nl\/DL\/publications\/PU00018235.pdf"},{"key":"21_CR10","doi-asserted-by":"publisher","unstructured":"Charalampopoulos, P., Kociumaka, T., Pissis, S.P., Radoszewski, J.: Faster algorithms for longest common substring. In: Mutzel, P., Pagh, R., Herman, G. (eds.) 29th Annual European Symposium on Algorithms, ESA 2021, 6\u20138 September 2021, Lisbon (Virtual Conference). LIPIcs, vol.\u00a0204, pp. 30:1\u201330:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021). https:\/\/doi.org\/10.4230\/LIPICS.ESA.2021.30","DOI":"10.4230\/LIPICS.ESA.2021.30"},{"key":"21_CR11","doi-asserted-by":"publisher","unstructured":"Charalampopoulos, P., Kociumaka, T., Wellnitz, P.: Faster approximate pattern matching: a unified approach. In: Irani, S. (ed.) 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, 16\u201319 November 2020, pp. 978\u2013989. IEEE (2020). https:\/\/doi.org\/10.1109\/FOCS46700.2020.00095","DOI":"10.1109\/FOCS46700.2020.00095"},{"key":"21_CR12","doi-asserted-by":"publisher","unstructured":"Charalampopoulos, P., Kociumaka, T., Wellnitz, P.: Faster approximate pattern matching: a unified approach. In: 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, pp. 978\u2013989. IEEE (2020). https:\/\/doi.org\/10.1109\/FOCS46700.2020.00095. Full version: arXiv:2004.08350v2","DOI":"10.1109\/FOCS46700.2020.00095"},{"key":"21_CR13","doi-asserted-by":"publisher","unstructured":"Charalampopoulos, P., Pissis, S.P., Radoszewski, J.: Longest palindromic substring in sublinear time. In: Bannai, H., Holub, J. (eds.) 33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022, 27\u201329 June 2022, Prague. LIPIcs, vol.\u00a0223, pp. 20:1\u201320:9. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022). https:\/\/doi.org\/10.4230\/LIPICS.CPM.2022.20","DOI":"10.4230\/LIPICS.CPM.2022.20"},{"key":"21_CR14","unstructured":"Christou, M., Crochemore, M., Iliopoulos, C.S.: Quasiperiodicities in Fibonacci strings. Ars Comb. 129, 211\u2013225 (2016). https:\/\/arxiv.org\/abs\/1201.6162"},{"key":"21_CR15","doi-asserted-by":"publisher","unstructured":"Crochemore, M., et al.: The maximum number of squares in a tree. In: K\u00e4rkk\u00e4inen, J., Stoye, J. (eds.) CPM 2012. LNCS, vol.\u00a07354, pp. 27\u201340. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-31265-6_3","DOI":"10.1007\/978-3-642-31265-6_3"},{"key":"21_CR16","doi-asserted-by":"publisher","unstructured":"Crochemore, M., Iliopoulos, C.S., Pissis, S.P., Tischler, G.: Cover array string reconstruction. In: Amir, A., Parida, L. (eds.) CPM 2010. LNCS, vol.\u00a06129, pp. 251\u2013259. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-13509-5_23","DOI":"10.1007\/978-3-642-13509-5_23"},{"key":"21_CR17","doi-asserted-by":"publisher","unstructured":"Crochemore, M., et al.: Internal quasiperiod queries. In: Boucher, C., Thankachan, S.V. (eds.) SPIRE 2020. LNCS, vol. 12303, pp. 60\u201375. Springer, Heidelberg (2020). https:\/\/doi.org\/10.1007\/978-3-030-59212-7_5","DOI":"10.1007\/978-3-030-59212-7_5"},{"key":"21_CR18","doi-asserted-by":"publisher","unstructured":"Crochemore, M., et al.: Shortest covers of all cyclic shifts of a string. Theor. Comput. Sci. 866, 70\u201381 (2021). https:\/\/doi.org\/10.1016\/J.TCS.2021.03.011","DOI":"10.1016\/J.TCS.2021.03.011"},{"issue":"5","key":"21_CR19","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1007\/BF01190846","volume":"13","author":"M Crochemore","year":"1995","unstructured":"Crochemore, M., Rytter, W.: Squares, cubes, and time-space efficient string searching. Algorithmica 13(5), 405\u2013425 (1995). https:\/\/doi.org\/10.1007\/BF01190846","journal-title":"Algorithmica"},{"key":"21_CR20","doi-asserted-by":"publisher","unstructured":"Duyster, A., Kociumaka, T.: Logarithmic-time internal pattern matching queries in compressed and dynamic texts. In: Lipt\u00e1k, Z., et al. (eds.) SPIRE 2024. LNCS, vol. 14899, pp. 102\u2013117, Springer, Cham (2024). https:\/\/doi.org\/10.1007\/978-3-031-72200-4_8","DOI":"10.1007\/978-3-031-72200-4_8"},{"key":"21_CR21","doi-asserted-by":"publisher","unstructured":"Farach, M.: Optimal suffix tree construction with large alphabets. In: 38th Annual Symposium on Foundations of Computer Science, FOCS 1997, Miami Beach, 19\u201322 October 1997, pp. 137\u2013143. IEEE Computer Society (1997). https:\/\/doi.org\/10.1109\/SFCS.1997.646102","DOI":"10.1109\/SFCS.1997.646102"},{"key":"21_CR22","doi-asserted-by":"publisher","unstructured":"Fine, N.J., Wilf, H.S.: Uniqueness theorems for periodic functions. Proc. Am. Math. Soc. 16(1), 109\u2013114 (1965). https:\/\/doi.org\/10.1090\/S0002-9939-1965-0174934-9","DOI":"10.1090\/S0002-9939-1965-0174934-9"},{"key":"21_CR23","doi-asserted-by":"publisher","unstructured":"Flouri, T., et al.: Enhanced string covering. Theor. Comput. Sci. 506, 102\u2013114 (2013). https:\/\/doi.org\/10.1016\/J.TCS.2013.08.013","DOI":"10.1016\/J.TCS.2013.08.013"},{"key":"21_CR24","doi-asserted-by":"publisher","unstructured":"Ganardi, M., Je\u017c, A., Lohrey, M.: Balancing straight-line programs. J. ACM 68(4), 27:1\u201327:40 (2021). https:\/\/doi.org\/10.1145\/3457389","DOI":"10.1145\/3457389"},{"key":"21_CR25","doi-asserted-by":"publisher","unstructured":"Gawrychowski, P., Karczmarz, A., Kociumaka, T., Lacki, J., Sankowski, P.: Optimal dynamic strings. In: Czumaj, A. (ed.) Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, 7\u201310 January 2018, pp. 1509\u20131528. SIAM (2018). https:\/\/doi.org\/10.1137\/1.9781611975031.99","DOI":"10.1137\/1.9781611975031.99"},{"issue":"1","key":"21_CR26","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/S1570-8667(03)00010-8","volume":"1","author":"R Hariharan","year":"2003","unstructured":"Hariharan, R., Vinay, V.: String matching in \u00d5(sqrt(n)+sqrt(m)) quantum time. J. Discrete Algorithms 1(1), 103\u2013110 (2003). https:\/\/doi.org\/10.1016\/S1570-8667(03)00010-8","journal-title":"J. Discrete Algorithms"},{"key":"21_CR27","doi-asserted-by":"publisher","unstructured":"I, T., et al.: Detecting regularities on grammar-compressed strings. Inf. Comput. 240, 74\u201389 (2015). https:\/\/doi.org\/10.1016\/J.IC.2014.09.009","DOI":"10.1016\/J.IC.2014.09.009"},{"key":"21_CR28","doi-asserted-by":"publisher","unstructured":"Jin, C., Nogler, J.: Quantum speed-ups for string synchronizing sets, longest common substring, and k-mismatch matching. In: Bansal, N., Nagarajan, V. (eds.) Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, 22\u201325 January 2023, pp. 5090\u20135121. SIAM (2023). https:\/\/doi.org\/10.1137\/1.9781611977554.CH186","DOI":"10.1137\/1.9781611977554.CH186"},{"key":"21_CR29","doi-asserted-by":"publisher","unstructured":"Kempa, D., Kociumaka, T.: String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure. In: Charikar, M., Cohen, E. (eds.) Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, 23\u201326 June 2019, pp. 756\u2013767. ACM (2019). https:\/\/doi.org\/10.1145\/3313276.3316368","DOI":"10.1145\/3313276.3316368"},{"key":"21_CR30","doi-asserted-by":"publisher","unstructured":"Kempa, D., Kociumaka, T.: Dynamic suffix array with polylogarithmic queries and updates. In: Leonardi, S., Gupta, A. (eds.) STOC 2022: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, 20\u201324 June 2022, pp. 1657\u20131670. ACM (2022). https:\/\/doi.org\/10.1145\/3519935.3520061","DOI":"10.1145\/3519935.3520061"},{"key":"21_CR31","doi-asserted-by":"publisher","unstructured":"Knuth, D.E., Jr., J.H.M., Pratt, V.R.: Fast pattern matching in strings. SIAM J. Comput. 6(2), 323\u2013350 (1977). https:\/\/doi.org\/10.1137\/0206024","DOI":"10.1137\/0206024"},{"key":"21_CR32","doi-asserted-by":"publisher","unstructured":"Kociumaka, T., Kubica, M., Radoszewski, J., Rytter, W., Wale\u0144, T.: A linear-time algorithm for seeds computation. ACM Trans. Algorithms 16(2), 27:1\u201327:23 (2020). https:\/\/doi.org\/10.1145\/3386369","DOI":"10.1145\/3386369"},{"key":"21_CR33","doi-asserted-by":"crossref","unstructured":"Kociumaka, T., Radoszewski, J., Rytter, W., Wale\u0144, T.: Internal pattern matching queries in a text and applications. arXiv preprint arXiv:1311.6235 (2013)","DOI":"10.1137\/1.9781611973730.36"},{"key":"21_CR34","doi-asserted-by":"publisher","unstructured":"Kociumaka, T., Radoszewski, J., Rytter, W., Wale\u0144, T.: Internal pattern matching queries in a text and applications. In: Indyk, P. (ed.) Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, 4\u20136 January 2015, pp. 532\u2013551. SIAM (2015). https:\/\/doi.org\/10.1137\/1.9781611973730.36","DOI":"10.1137\/1.9781611973730.36"},{"key":"21_CR35","doi-asserted-by":"publisher","unstructured":"Mitani, K., Mieno, T., Seto, K., Horiyama, T.: Shortest cover after edit. In: Inenaga, S., Puglisi, S.J. (eds.) 35th Annual Symposium on Combinatorial Pattern Matching, CPM 2024, 25\u201327 June 2024, Fukuoka. LIPIcs, vol.\u00a0296, pp. 24:1\u201324:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2024). https:\/\/doi.org\/10.4230\/LIPICS.CPM.2024.24","DOI":"10.4230\/LIPICS.CPM.2024.24"},{"issue":"2","key":"21_CR36","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/0020-0190(94)00235-Q","volume":"54","author":"DWG Moore","year":"1995","unstructured":"Moore, D.W.G., Smyth, W.F.: A correction to \u201cAn optimal algorithm to compute all the covers of a string\u2019\u2019. Inf. Process. Lett. 54(2), 101\u2013103 (1995). https:\/\/doi.org\/10.1016\/0020-0190(94)00235-Q","journal-title":"Inf. Process. Lett."},{"key":"21_CR37","doi-asserted-by":"publisher","unstructured":"Munro, J.I., Navarro, G., Nekrich, Y.: Text indexing and searching in sublinear time. In: G\u00f8rtz, I.L., Weimann, O. (eds.) 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020, 17\u201319 June 2020, Copenhagen. LIPIcs, vol.\u00a0161, pp. 24:1\u201324:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020). https:\/\/doi.org\/10.4230\/LIPICS.CPM.2020.24","DOI":"10.4230\/LIPICS.CPM.2020.24"},{"key":"21_CR38","doi-asserted-by":"publisher","unstructured":"Plandowski, W., Rytter, W.: Application of Lempel-Ziv encodings to the solution of words equations. In: Larsen, K.G., Skyum, S., Winskel, G. (eds.) ICALP 1998. LNCS, vol.\u00a01443, pp. 731\u2013742. Springer, Heidelberg (1998). https:\/\/doi.org\/10.1007\/BFB0055097","DOI":"10.1007\/BFB0055097"},{"key":"21_CR39","doi-asserted-by":"publisher","unstructured":"Radoszewski, J.: Linear time construction of cover suffix tree and applications. In: G\u00f8rtz, I.L., Farach-Colton, M., Puglisi, S.J., Herman, G. (eds.) 31st Annual European Symposium on Algorithms, ESA 2023, 4\u20136 September 2023, Amsterdam. LIPIcs, vol.\u00a0274, pp. 89:1\u201389:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2023). https:\/\/doi.org\/10.4230\/LIPICS.ESA.2023.89","DOI":"10.4230\/LIPICS.ESA.2023.89"},{"key":"21_CR40","unstructured":"Singh, M.: Quasiperiodicity in Tribonacci Word (2020). https:\/\/hal.science\/hal-02141636. Working paper or preprint"}],"container-title":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-72200-4_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,18]],"date-time":"2024-09-18T19:03:05Z","timestamp":1726686185000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-72200-4_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,19]]},"ISBN":["9783031721991","9783031722004"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-72200-4_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,9,19]]},"assertion":[{"value":"19 September 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SPIRE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on String Processing and Information Retrieval","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Puerto Vallarta","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Mexico","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 September 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 September 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"spire2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/computo.fismat.umich.mx\/spire2024\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}