{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T23:58:04Z","timestamp":1769299084759,"version":"3.49.0"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,6,22]],"date-time":"2021-06-22T00:00:00Z","timestamp":1624320000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,6,22]],"date-time":"2021-06-22T00:00:00Z","timestamp":1624320000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2018\/31\/D\/ST6\/03991"],"award-info":[{"award-number":["2018\/31\/D\/ST6\/03991"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Quasiperiodicity in strings was introduced almost 30 years ago as an extension of string periodicity. The basic notions of quasiperiodicity are cover and seed. A cover of a text <jats:italic>T<\/jats:italic> is a string whose occurrences in <jats:italic>T<\/jats:italic> cover all positions of <jats:italic>T<\/jats:italic>. A seed of text <jats:italic>T<\/jats:italic> is a cover of a superstring of <jats:italic>T<\/jats:italic>. In various applications exact quasiperiodicity is still not sufficient due to the presence of errors. We consider approximate notions of quasiperiodicity, for which we allow approximate occurrences in <jats:italic>T<\/jats:italic> with a small Hamming, Levenshtein or weighted edit distance. In previous work Sim et al. (J Korea Inf Sci Soc 29(1):16\u201321, 2002) and Christodoulakis et al. (J Autom Lang Comb 10(5\/6), 609\u2013626, 2005) showed that computing approximate covers and seeds, respectively, under weighted edit distance is NP-hard. They, therefore, considered restricted approximate covers and seeds which need to be factors of the original string <jats:italic>T<\/jats:italic> and presented polynomial-time algorithms for computing them. Further algorithms, considering approximate occurrences with Hamming distance bounded by <jats:italic>k<\/jats:italic>, were given in several contributions by Guth et al. They also studied relaxed approximate quasiperiods. We present more efficient algorithms for computing restricted approximate covers and seeds. In particular, we improve upon the complexities of many of the aforementioned algorithms, also for relaxed quasiperiods. Our solutions are especially efficient if the number (or total cost) of allowed errors is small. We also show conditional lower bounds for computing restricted approximate covers and prove NP-hardness of computing non-restricted approximate covers and seeds under the Hamming distance.<\/jats:p>","DOI":"10.1007\/s00453-021-00842-7","type":"journal-article","created":{"date-parts":[[2021,6,22]],"date-time":"2021-06-22T09:03:02Z","timestamp":1624352582000},"page":"566-589","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["k-Approximate Quasiperiodicity Under Hamming and Edit Distance"],"prefix":"10.1007","volume":"84","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0335-2963","authenticated-orcid":false,"given":"Aleksander","family":"K\u0119dzierski","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0067-6401","authenticated-orcid":false,"given":"Jakub","family":"Radoszewski","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,6,22]]},"reference":[{"issue":"7","key":"842_CR1","doi-asserted-by":"publisher","first-page":"2857","DOI":"10.1007\/s00453-019-00559-8","volume":"81","author":"A Amir","year":"2019","unstructured":"Amir, A., Levy, A., Lewenstein, M., Lubin, R., Porat, B.: Can we recover the cover? Algorithmica 81(7), 2857\u20132875 (2019). https:\/\/doi.org\/10.1007\/s00453-019-00559-8","journal-title":"Algorithmica"},{"key":"842_CR2","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/j.tcs.2019.05.020","volume":"793","author":"A Amir","year":"2019","unstructured":"Amir, A., Levy, A., Lubin, R., Porat, E.: Approximate cover of strings. Theor. Comput. Sci. 793, 59\u201369 (2019). https:\/\/doi.org\/10.1016\/j.tcs.2019.05.020","journal-title":"Theor. Comput. Sci."},{"key":"842_CR3","doi-asserted-by":"publisher","unstructured":"Amir, A., Levy, A., Porat, E.: Quasi-periodicity under mismatch errors. In: Navarro, G., Sankoff, D., Zhu, B. (eds.) Annual Symposium on Combinatorial Pattern Matching, CPM 2018, LIPIcs, vol. 105, pp. 4:1\u20134:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2018). https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2018.4","DOI":"10.4230\/LIPIcs.CPM.2018.4"},{"issue":"2","key":"842_CR4","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/0304-3975(93)90159-Q","volume":"119","author":"A Apostolico","year":"1993","unstructured":"Apostolico, A., Ehrenfeucht, A.: Efficient detection of quasiperiodicities in strings. Theor. Comput. Sci. 119(2), 247\u2013265 (1993). https:\/\/doi.org\/10.1016\/0304-3975(93)90159-Q","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"842_CR5","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."},{"issue":"6","key":"842_CR6","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."},{"key":"842_CR7","doi-asserted-by":"publisher","unstructured":"Bringmann, K., K\u00fcnnemann, M.: Quadratic conditional lower bounds for string problems and dynamic time warping. In: Guruswami, V. (ed.) IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, pp. 79\u201397. IEEE Computer Society (2015). https:\/\/doi.org\/10.1109\/FOCS.2015.15","DOI":"10.1109\/FOCS.2015.15"},{"issue":"5\/6","key":"842_CR8","first-page":"609","volume":"10","author":"M Christodoulakis","year":"2005","unstructured":"Christodoulakis, M., Iliopoulos, C.S., Park, K., Sim, J.S.: Approximate seeds of strings. J. Autom. Lang. Comb. 10(5\/6), 609\u2013626 (2005)","journal-title":"J. Autom. Lang. Comb."},{"key":"842_CR9","doi-asserted-by":"publisher","DOI":"10.1142\/4838","volume-title":"Jewels of Stringology","author":"M Crochemore","year":"2003","unstructured":"Crochemore, M., Rytter, W.: Jewels of Stringology. World Scientific, Singapore (2003). https:\/\/doi.org\/10.1142\/4838"},{"key":"842_CR10","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/j.tcs.2020.11.033","volume":"854","author":"P Czajka","year":"2021","unstructured":"Czajka, P., Radoszewski, J.: Experimental evaluation of algorithms for computing quasiperiods. Theor. Comput. Sci. 854, 17\u201329 (2021). https:\/\/doi.org\/10.1016\/j.tcs.2020.11.033","journal-title":"Theor. Comput. Sci."},{"issue":"6\u20138","key":"842_CR11","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1016\/j.ipl.2015.03.006","volume":"115","author":"T Flouri","year":"2015","unstructured":"Flouri, T., Giaquinta, E., Kobert, K., Ukkonen, E.: Longest common substrings with k mismatches. Inf. Process. Lett. 115(6\u20138), 643\u2013647 (2015). https:\/\/doi.org\/10.1016\/j.ipl.2015.03.006","journal-title":"Inf. Process. Lett."},{"key":"842_CR12","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1016\/j.tcs.2013.08.013","volume":"506","author":"T Flouri","year":"2013","unstructured":"Flouri, T., Iliopoulos, C.S., Kociumaka, T., Pissis, S.P., Puglisi, S.J., Smyth, W.F., Tyczy\u0144ski, W.: Enhanced string covering. Theor. Comput. Sci. 506, 102\u2013114 (2013). https:\/\/doi.org\/10.1016\/j.tcs.2013.08.013","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"842_CR13","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/s002240000044","volume":"30","author":"M Frances","year":"1997","unstructured":"Frances, M., Litman, A.: On covering problems of codes. Theory Comput. Syst. 30(2), 113\u2013119 (1997). https:\/\/doi.org\/10.1007\/s002240000044","journal-title":"Theory Comput. Syst."},{"key":"842_CR14","unstructured":"Guth, O.: Searching regularities in strings using finite automata. Ph.D. thesis, Czech Technical University in Prague (2014)"},{"key":"842_CR15","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/j.dam.2019.01.015","volume":"274","author":"O Guth","year":"2020","unstructured":"Guth, O.: On approximate enhanced covers under Hamming distance. Discrete Appl. Math. 274, 67\u201380 (2020). https:\/\/doi.org\/10.1016\/j.dam.2019.01.015","journal-title":"Discrete Appl. Math."},{"key":"842_CR16","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/978-90-481-3517-2_27","volume-title":"Intelligent Automation and Computer Engineering","author":"O Guth","year":"2010","unstructured":"Guth, O., Melichar, B.: Using finite automata approach for searching approximate seeds of strings. In: Huang, X., Ao, S.I., Castillo, O. (eds.) Intelligent Automation and Computer Engineering, pp. 347\u2013360. Springer, Netherlands (2010). https:\/\/doi.org\/10.1007\/978-90-481-3517-2_27"},{"key":"842_CR17","unstructured":"Guth, O., Melichar, B., Bal\u00edk, M.: Searching all approximate covers and their distance using finite automata. In: P.\u00a0Vojt\u00e1s (ed.) Proceedings of the Conference on Theory and Practice of Information Technologies, ITAT 2008, CEUR Workshop Proceedings, vol. 414. CEUR-WS.org (2008). http:\/\/ceur-ws.org\/Vol-414\/paper4.pdf"},{"key":"842_CR18","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.jda.2015.05.007","volume":"34","author":"H Hyyr\u00f6","year":"2015","unstructured":"Hyyr\u00f6, H., Narisawa, K., Inenaga, S.: Dynamic edit distance table under a general weighted cost function. J. Discrete Algorithms 34, 2\u201317 (2015). https:\/\/doi.org\/10.1016\/j.jda.2015.05.007","journal-title":"J. Discrete Algorithms"},{"issue":"3","key":"842_CR19","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1007\/BF01955677","volume":"16","author":"CS Iliopoulos","year":"1996","unstructured":"Iliopoulos, C.S., Moore, D.W.G., Park, K.: Covering a string. Algorithmica 16(3), 288\u2013297 (1996). https:\/\/doi.org\/10.1007\/BF01955677","journal-title":"Algorithmica"},{"issue":"2","key":"842_CR20","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001). https:\/\/doi.org\/10.1006\/jcss.2000.1727","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"842_CR21","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001). https:\/\/doi.org\/10.1006\/jcss.2001.1774","journal-title":"J. Comput. Syst. Sci."},{"key":"842_CR22","doi-asserted-by":"publisher","unstructured":"Kaplan, H., Porat, E., Shafrir, N.: Finding the position of the k-mismatch and approximate tandem repeats. In: L.\u00a0Arge, R.\u00a0Freivalds (eds.) Algorithm Theory\u2014SWAT 2006, 10th Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science, vol. 4059, pp. 90\u2013101. Springer (2006). https:\/\/doi.org\/10.1007\/11785293_11","DOI":"10.1007\/11785293_11"},{"key":"842_CR23","doi-asserted-by":"publisher","unstructured":"K\u0119dzierski, A., Radoszewski, J.: k-approximate quasiperiodicity under Hamming and edit distance. In: I.L. G\u00f8rtz, O.\u00a0Weimann (eds.) 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020, LIPIcs, vol. 161, pp. 18:1\u201318:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020). https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2020.18","DOI":"10.4230\/LIPIcs.CPM.2020.18"},{"issue":"2","key":"842_CR24","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/S1570-8667(03)00082-0","volume":"2","author":"S Kim","year":"2004","unstructured":"Kim, S., Park, K.: A dynamic edit distance table. J. Discrete Algorithms 2(2), 303\u2013312 (2004). https:\/\/doi.org\/10.1016\/S1570-8667(03)00082-0","journal-title":"J. Discrete Algorithms"},{"key":"842_CR25","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. Alg. 16(2), Article 27 (2020). https:\/\/doi.org\/10.1145\/3386369","DOI":"10.1145\/3386369"},{"key":"842_CR26","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/j.tcs.2016.11.035","volume":"710","author":"T Kociumaka","year":"2018","unstructured":"Kociumaka, T., Pissis, S.P., Radoszewski, J., Rytter, W., Wale\u0144, T.: Efficient algorithms for shortest partial seeds in words. Theor. Comput. Sci. 710, 139\u2013147 (2018). https:\/\/doi.org\/10.1016\/j.tcs.2016.11.035","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"842_CR27","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/s00453-014-9915-3","volume":"73","author":"T Kociumaka","year":"2015","unstructured":"Kociumaka, T., Pissis, S.P., Radoszewski, J., Rytter, W., Wale\u0144, T.: Fast algorithm for partial covers in words. Algorithmica 73(1), 217\u2013233 (2015). https:\/\/doi.org\/10.1007\/s00453-014-9915-3","journal-title":"Algorithmica"},{"issue":"2","key":"842_CR28","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1137\/S0097539794264810","volume":"27","author":"GM Landau","year":"1998","unstructured":"Landau, G.M., Myers, E.W., Schmidt, J.P.: Incremental string comparison. SIAM J. Comput. 27(2), 557\u2013582 (1998). https:\/\/doi.org\/10.1137\/S0097539794264810","journal-title":"SIAM J. Comput."},{"key":"842_CR29","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/0304-3975(86)90178-7","volume":"43","author":"GM Landau","year":"1986","unstructured":"Landau, G.M., Vishkin, U.: Efficient string matching with k mismatches. Theor. Comput. Sci. 43, 239\u2013249 (1986). https:\/\/doi.org\/10.1016\/0304-3975(86)90178-7","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"842_CR30","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/s00453-001-0062-2","volume":"32","author":"Y Li","year":"2002","unstructured":"Li, Y., Smyth, W.F.: Computing the cover array in linear time. Algorithmica 32(1), 95\u2013106 (2002). https:\/\/doi.org\/10.1007\/s00453-001-0062-2","journal-title":"Algorithmica"},{"issue":"5","key":"842_CR31","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/0020-0190(94)00045-X","volume":"50","author":"DWG Moore","year":"1994","unstructured":"Moore, D.W.G., Smyth, W.F.: An optimal algorithm to compute all the covers of a string. Inf. Process. Lett. 50(5), 239\u2013246 (1994). https:\/\/doi.org\/10.1016\/0020-0190(94)00045-X","journal-title":"Inf. Process. Lett."},{"key":"842_CR32","doi-asserted-by":"publisher","unstructured":"Moore, D.W.G., Smyth, W.F.: A correction to \u201cAn optimal algorithm to compute all the covers of a string.\u201d Inf. Process. Lett. 54(2), 101\u2013103 (1995). https:\/\/doi.org\/10.1016\/0020-0190(94)00235-Q","DOI":"10.1016\/0020-0190(94)00235-Q"},{"issue":"1","key":"842_CR33","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1016\/S0304-3975(00)00365-0","volume":"262","author":"JS Sim","year":"2001","unstructured":"Sim, J.S., Iliopoulos, C.S., Park, K., Smyth, W.F.: Approximate periods of strings. Theor. Comput. Sci. 262(1), 557\u2013568 (2001). https:\/\/doi.org\/10.1016\/S0304-3975(00)00365-0","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"842_CR34","first-page":"16","volume":"29","author":"JS Sim","year":"2002","unstructured":"Sim, J.S., Park, K., Kim, S.R., Lee, J.S.: Finding approximate covers of strings. J. Korea Inf. Sci. Soc. 29(1), 16\u201321 (2002)","journal-title":"J. Korea Inf. Sci. Soc."},{"issue":"1","key":"842_CR35","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1145\/321796.321811","volume":"21","author":"RA Wagner","year":"1974","unstructured":"Wagner, R.A., Fischer, M.J.: The string-to-string correction problem. J. ACM 21(1), 168\u2013173 (1974)","journal-title":"J. ACM"},{"issue":"2\u20133","key":"842_CR36","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1016\/j.tcs.2005.09.023","volume":"348","author":"R Williams","year":"2005","unstructured":"Williams, R.: A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci. 348(2\u20133), 357\u2013365 (2005). https:\/\/doi.org\/10.1016\/j.tcs.2005.09.023","journal-title":"Theor. Comput. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00842-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00842-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00842-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,15]],"date-time":"2022-03-15T09:05:10Z","timestamp":1647335110000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00842-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,22]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["842"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00842-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6,22]]},"assertion":[{"value":"1 September 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 June 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 June 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}