{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:26:55Z","timestamp":1759638415222,"version":"3.37.3"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2019,3,22]],"date-time":"2019-03-22T00:00:00Z","timestamp":1553212800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,7]]},"DOI":"10.1007\/s00453-019-00559-8","type":"journal-article","created":{"date-parts":[[2019,3,22]],"date-time":"2019-03-22T11:03:06Z","timestamp":1553252586000},"page":"2857-2875","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Can We Recover the Cover?"],"prefix":"10.1007","volume":"81","author":[{"given":"Amihood","family":"Amir","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1686-0094","authenticated-orcid":false,"given":"Avivit","family":"Levy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Moshe","family":"Lewenstein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ronit","family":"Lubin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benny","family":"Porat","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,3,22]]},"reference":[{"issue":"6","key":"559_CR1","doi-asserted-by":"publisher","first-page":"1039","DOI":"10.1137\/0216067","volume":"16","author":"K Abrahamson","year":"1987","unstructured":"Abrahamson, K.: Generalized string matching. SIAM J. Comput. 16(6), 1039\u20131051 (1987)","journal-title":"SIAM J. Comput."},{"key":"559_CR2","doi-asserted-by":"crossref","unstructured":"Amir, A., Eisenberg, E., Levy, A.: Approximate periodicity. In: Proceedings of ISAAC 2010, LNCS 6506, Springer, Berlin, pp. 25\u201336 (2010)","DOI":"10.1007\/978-3-642-17517-6_5"},{"issue":"1","key":"559_CR3","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1145\/2390176.2390189","volume":"9","author":"A Amir","year":"2012","unstructured":"Amir, A., Eisenberg, E., Levy, A., Porat, E., Shapira, N.: Cycle detection and correction. ACM Trans. Algorithms 9(1), 13 (2012)","journal-title":"ACM Trans. Algorithms"},{"key":"559_CR4","doi-asserted-by":"crossref","unstructured":"Amir, A., Amit, M., Landau, G.M., Sokol, D.: Period recovery over the hamming and edit distances. In: Proceedings of 15th Latin American Theoretical Informatics Symposium (LATIN), pp. 55\u201367 (2016)","DOI":"10.1007\/978-3-662-49529-2_5"},{"key":"559_CR5","unstructured":"Amir, A., Levy, A., Lubin, R., Porat, E.: Approximate Cover of Strings. CPM (2017)"},{"key":"559_CR6","doi-asserted-by":"crossref","unstructured":"Apostolico, A., Breslauer, D.: Of periods, quasiperiods, repetitions and covers. In: Proceedings of Structures in Logic and Computer Science, LNCS 1261, pp. 236\u2013248. Springer, Berlin (1997)","DOI":"10.1007\/3-540-63246-8_14"},{"key":"559_CR7","unstructured":"Antoniou, P., Crochemore, M., Iliopoulos, C.S., Jayasekera, I., Landau, G.M.: Conservative string covering of indeterminate strings. In: Proceedings of Stringology, pp. 108\u2013115 (2008)"},{"key":"559_CR8","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. Theoret. Comput. Sci. 119, 247\u2013265 (1993)","journal-title":"Theoret. Comput. Sci."},{"key":"559_CR9","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, 17\u201320 (1991)","journal-title":"Inf. Process. Lett."},{"key":"559_CR10","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, 345\u2013347 (1992)","journal-title":"Inf. Process. Lett."},{"issue":"5","key":"559_CR11","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/0020-0190(94)90060-4","volume":"49","author":"D Breslauer","year":"1994","unstructured":"Breslauer, D.: Testing string superprimitivity in parallel. Inf. Process. Lett. 49(5), 235\u2013241 (1994)","journal-title":"Inf. Process. Lett."},{"key":"559_CR12","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1016\/j.jda.2016.05.001","volume":"37","author":"B Cazaux","year":"2016","unstructured":"Cazaux, B., Rivals, E.: A linear time algorithm for shortest cyclic cover of strings. J. Discrete Algorithms 37, 56\u201367 (2016)","journal-title":"J. Discrete Algorithms"},{"key":"559_CR13","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, 609\u2013626 (2005)","journal-title":"J. Autom. Lang. Comb."},{"key":"559_CR14","first-page":"73","volume":"11","author":"T Crawford","year":"1998","unstructured":"Crawford, T., Iliopoulos, C.S., Raman, R.: String matching techniques for musical similarity and melodic recognition. Comput. Musicol. 11, 73\u2013100 (1998)","journal-title":"Comput. Musicol."},{"key":"559_CR15","doi-asserted-by":"crossref","unstructured":"Crochemore, M., Iliopoulos, C.S., Pissis, S.P., Tischler, G.: Cover array string reconstruction. In: Proceedings of CPM, pp. 251\u2013259 (2010)","DOI":"10.1007\/978-3-642-13509-5_23"},{"key":"559_CR16","unstructured":"Crochemore, M., Iliopoulos, C.S., Yu, H.: Algorithms for computing evolutionary chains in molecular and musical sequences. In: Proceedings of 9th Australian Workshop on Combinatorial Algorithms, pp. 172\u2013185 (1998)"},{"key":"559_CR17","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., Tyczynski, W.: Enhanced string covering. Theor. Comput. Sci. 506, 102\u2013114 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"559_CR18","doi-asserted-by":"crossref","unstructured":"Guth, O., Melichar, B.: Using finite automata approach for searching approximate seeds of strings. In: Intelligent Automation and Computer Engineering. Springer, Netherlands, ISBN 978-90-481-3517-2, pp. 347\u2013360 (2010)","DOI":"10.1007\/978-90-481-3517-2_27"},{"key":"559_CR19","unstructured":"Guth, O., Melichar, B., Balik, M.: Searching all approximate covers and their distance using finite automata. In: Information Technologies Applications and Theory, pp. 21\u201326, ISBN 978-80-969184-9-2 (2009)"},{"issue":"1","key":"559_CR20","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/S0304-3975(98)00260-6","volume":"218","author":"CS Iliopoulos","year":"1999","unstructured":"Iliopoulos, C.S., Mouchard, L.: Quasiperiodicity and string covering. Theor. Comput. Sci. 218(1), 205\u2013216 (1999)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"559_CR21","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1007\/BF01955677","volume":"16","author":"CS Iliopoulus","year":"1996","unstructured":"Iliopoulus, C.S., Moore, D.W.G., Park, K.: Covering a string. Algorithmica 16(3), 288\u2013297 (1996)","journal-title":"Algorithmica"},{"key":"559_CR22","unstructured":"Iliopoulos, C.S., Smyth, W.F.: An on-line algorithm of computing a minimum set of \n                    \n                      \n                    \n                    $$k$$\n                    \n                      \n                        k\n                      \n                    \n                  -covers of a string. In: Proceedings of 9th Australasian Workshop on Combinatorial Algorithms (AWOCA), pp. 97\u2013106 (1998)"},{"key":"559_CR23","doi-asserted-by":"crossref","unstructured":"Kociumaka, T., Pissis, S.P., Radoszewski, J., Rytter, W., Walen, T.: Fast algorithm for partial covers in words. In: Proceedings of CPM, pp. 177\u2013188 (2013)","DOI":"10.1007\/978-3-642-38905-4_18"},{"key":"559_CR24","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., Walen, T.: Fast algorithm for partial covers in words. Algorithmica 73, 217\u2013233 (2015)","journal-title":"Algorithmica"},{"key":"559_CR25","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/S0304-3975(02)00448-6","volume":"303","author":"RM Kolpakov","year":"2003","unstructured":"Kolpakov, R.M., Kucherov, G.: Finding approximate repetitions under hamming distance. Theor. Comput. Sci. 303, 135\u2013156 (2003)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"559_CR26","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"DE Knuth","year":"1977","unstructured":"Knuth, D.E., Morris, J., Pratt, V.R.: Fast pattern matching in strings. SIAM J. Comput. 6(2), 323\u2013350 (1977)","journal-title":"SIAM J. Comput."},{"key":"559_CR27","doi-asserted-by":"crossref","unstructured":"Landau, G.M., Schmidt, J.P.: An algorithm for approximate tandem repeats. In: Proceedings of 4th Symposium Combinatorial Pattern Matching, LNCS 648, Springer, Berlin, pp. 120\u2013133 (1993)","DOI":"10.1007\/BFb0029801"},{"issue":"1","key":"559_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1089\/106652701300099038","volume":"8","author":"GM Landau","year":"2001","unstructured":"Landau, G.M., Schmidt, J.P., Sokol, D.: An algorithm for approximate tandem repeats. J. Comput. Biol. 8(1), 1\u201318 (2001)","journal-title":"J. Comput. Biol."},{"issue":"1","key":"559_CR29","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)","journal-title":"Algorithmica"},{"key":"559_CR30","volume-title":"Combinatorics on Words","author":"M Lothaire","year":"1983","unstructured":"Lothaire, M.: Combinatorics on Words. Addison-Wesley, Reading (1983)"},{"key":"559_CR31","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.jda.2018.09.003","volume":"51","author":"N Mhaskar","year":"2018","unstructured":"Mhaskar, N., Smyth, W.F.: String covering with optimal covers. J. Discrete Algorithms 51, 26\u201338 (2018)","journal-title":"J. Discrete Algorithms"},{"issue":"5","key":"559_CR32","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/0020-0190(94)00045-X","volume":"50","author":"D Moore","year":"1994","unstructured":"Moore, D., Smyth, W.F.: An optimal algorithm to compute all the covers of a string. Inf. Process. Lett. 50(5), 239\u2013246 (1994)","journal-title":"Inf. Process. Lett."},{"key":"559_CR33","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/0020-0190(94)00235-Q","volume":"54","author":"D Moore","year":"1995","unstructured":"Moore, D., Smyth, W.F.: A correction to: an optimal algorithm to compute all the covers of a string. Inf. Process. Lett. 54, 101\u2013103 (1995)","journal-title":"Inf. Process. Lett."},{"key":"559_CR34","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. Theoret. Comput. Sci. 262, 557\u2013568 (2001)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"559_CR35","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/S0304-3975(00)00067-0","volume":"249","author":"WF Smyth","year":"2000","unstructured":"Smyth, W.F.: Repetitive perhaps, but certainly not boring. Theoret. Comput. Sci. 249(2), 343\u2013355 (2000)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"559_CR36","first-page":"33","volume":"84","author":"H Zhang","year":"2008","unstructured":"Zhang, H., Guo, Q., Iliopoulos, C.S.: Algorithms for computing the lambda-regularities in strings. Fundam. Inform. 84(1), 33\u201349 (2008)","journal-title":"Fundam. Inform."},{"key":"559_CR37","doi-asserted-by":"crossref","unstructured":"Zhang, H., Guo, Q., Iliopoulos, C.S.: Varieties of regularities in weighted sequences. In: Proceedings of AAIM 2010, LNCS 6124, pp. 271\u2013280. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-14355-7_28"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00559-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00559-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00559-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,3,21]],"date-time":"2020-03-21T00:13:20Z","timestamp":1584749600000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00559-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,22]]},"references-count":37,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2019,7]]}},"alternative-id":["559"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00559-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2019,3,22]]},"assertion":[{"value":"26 October 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 March 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 March 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}