pith. sign in

arxiv: 2211.11856 · v4 · submitted 2022-11-21 · 💻 cs.DS

String Covering: A Survey

Neerja Mhaskar , W. F. Smyth This is my paper

Pith reviewed 2026-05-24 10:40 UTC · model grok-4.3

classification 💻 cs.DS
keywords string coversseedscombinatorics on wordsstring algorithmscompact representationssuperstringsperiodicities
0
0 comments X

The pith

String covers, first proposed in 1990, provide compact representations for strings up to trillions of letters long through increasingly sophisticated variants including seeds.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper surveys the development of string covering as a compaction method for long strings in combinatorics. It begins with the initial simple covers from 1990 and traces their growth into more advanced forms. It separately examines covering by a seed, defined as a cover of a superstring of the original string. The survey closes by listing several concrete research directions that the authors argue could advance string processing. A reader would care because effective compaction matters for handling extremely long sequences in algorithms and data structures.

Core claim

The authors survey various forms of the cover of a given string x, initially proposed in a simple form in 1990 but with increasingly sophisticated variants discovered since then; they also consider covering by a seed, that is a cover of a superstring of x; they conclude with many proposals for research directions that could make significant contributions to string processing in future.

What carries the argument

The cover of a given string x, a structure whose repetitions or overlaps compactly represent the original string.

If this is right

  • Compact representations become feasible for strings of trillions of letters.
  • Sophisticated cover variants expand the range of strings that admit compaction.
  • Seed-based covering extends compaction to cases where the original string is embedded in a larger superstring.
  • The proposed research directions can be pursued to yield new contributions in string algorithms.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • String covering ideas could be tested for integration with existing periodicity detection algorithms in practice.
  • The survey's research proposals might be evaluated by checking whether they reduce space or time in specific string matching benchmarks.
  • Connections between covers and seeds could be explored in domains handling overlapping or extended sequences, such as genome assembly.

Load-bearing premise

The body of work on string covers since 1990 is sufficiently developed, coherent, and worthy of a dedicated survey, and the listed research directions will lead to meaningful advances.

What would settle it

A demonstration that no new significant variants of string covers or seeds have been published since 1990, or that the proposed research directions produce no measurable improvements in string processing tasks.

Figures

Figures reproduced from arXiv: 2211.11856 by Neerja Mhaskar, W. F. Smyth.

Figure 1
Figure 1. Figure 1: Suffix array, LCP/RSF/OLP arrays and corresponding suffix tree for x = abaababa — adapted from [14]. from node 0 in [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: LSmin, LSmax, RSmin and RSmax are the minimal left seed, maximal left seed, minimal right seed and maximal right seed arrays, respectively, computed for the string x = abaababaabaabab — adapted from [105]. In [107] Christou et al. describe an O(n log n)-time algorithm to compute the minimal right seed array. Their solution uses a variant of the partitioning algorithm introduced by Crochemore in [108], as e… view at source ↗
read the original abstract

The study of strings is an important combinatorial field that precedes the digital computer. Strings can be very long, trillions of letters, so it is important to find compact representations. Here we first survey various forms of one potential compaction methodology, the cover of a given string x, initially proposed in a simple form in 1990, but increasingly of interest as more sophisticated variants have been discovered. We then consider covering by a seed; that is, a cover of a superstring of x. We conclude with many proposals for research directions that could make significant contributions to string processing in future.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript is a survey of string covering techniques in combinatorics on words. It reviews the initial simple form of covers for a string x proposed in 1990, subsequent more sophisticated variants, the extension to covering by seeds (i.e., covers of a superstring of x), and concludes by listing multiple proposals for future research directions intended to advance string processing.

Significance. If the survey accurately and comprehensively represents the literature on string covers and seeds without significant omissions, it would provide a consolidated reference for researchers working on compact representations of long strings. The enumerated research directions could usefully focus community attention on open problems in this sub-area of stringology.

minor comments (2)
  1. [Conclusion] The abstract states that 'many proposals for research directions' are made; the conclusion section should explicitly enumerate and briefly justify each direction so readers can assess their potential impact without needing to infer from context.
  2. [Introduction] Citations to the 1990 initial proposal and key subsequent papers should include full bibliographic details and, where possible, a one-sentence description of each cited work's contribution to maintain readability for non-specialists.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our survey on string covering techniques and the recommendation for minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

This is a literature survey paper with no derivations, equations, predictions, or fitted quantities of any kind. It reviews external prior literature on string covers (introduced in 1990) and seed covers, then lists open research directions. All content is descriptive and historiographic, drawing on independent external sources without any self-referential reduction, self-citation load-bearing claims, or renaming of results as new derivations. The paper is self-contained as a review against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

This is a survey paper with no mathematical claims, derivations, or new entities; it relies entirely on summarizing existing published work rather than introducing free parameters, axioms, or invented entities.

pith-pipeline@v0.9.0 · 5614 in / 1063 out tokens · 43684 ms · 2026-05-24T10:40:28.554126+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

131 extracted references · 131 canonical work pages

  1. [1]

    ¨Uber unendliche Zeichenreichen

    Thue A. ¨Uber unendliche Zeichenreichen. Norske Vid. Selsk. Skr . Mat. Nat. Kl. (Cristiania) , 1906. 7:1–22

    work page 1906

  2. [2]

    Computing Patterns in Strings

    Smyth B. Computing Patterns in Strings. Pearson/Addiso n–Wesley, 2003. ISBN 9780201398397

    work page 2003

  3. [3]

    Algorithms on Strings

    Crochemore M, Hancart C, Lecroq T. Algorithms on Strings . Cambridge University Press, 2007. doi:10.1017/CBO9780511546853

    work page doi:10.1017/cbo9780511546853 2007

  4. [4]

    Molecular structure of nucleic aci ds

    Watson JD, Crick FHC. Molecular structure of nucleic aci ds. Nature, 1953. 171:737–738. URL https://doi.org/10.1038/171737a0

    work page doi:10.1038/171737a0 1953

  5. [5]

    Efficient Detection of Quas i–periodicities in Strings

    Apostolico A, Ehrenfeucht A. Efficient Detection of Quas i–periodicities in Strings. Technical Report 90.5, The Leonadro Fibonacci Institute, Trento, Italy, 199 0

    work page

  6. [6]

    Covering a String

    Iliopoulos CS, Moore DW , Park K. Covering a String. In: Pr oc. 4th CM–SIAM Symp. on Discrete Algo- rithms (SODA), volume LNCS 684. 1993 pp. 54–62. URL https://doi.org/10.1007/BFb0029796

    work page doi:10.1007/bfb0029796 1993

  7. [7]

    Covering a String

    Iliopoulos CS, Moore DW , Park K. Covering a String. Algorithmica, 1996. 16(1):288–297. doi: https://doi.org/10.1007/BF01955677

    work page doi:10.1007/bf01955677 1996

  8. [8]

    A Linear-Time Algorithm for Seeds Computation

    Kociumaka T, Kubica M, Radoszewski J, Rytter W , Wale´ n T. A Linear-Time Algorithm for Seeds Computation. ACM Transactions on Algorithms , 2020. 16(2):27/1–27/23. doi:https://doi.org/10.1145/ 3386369

    work page 2020

  9. [9]

    Suffix Arrays: A New Method for On–Line S tring Searches

    Manber U, Myers G. Suffix Arrays: A New Method for On–Line S tring Searches. In: Proc. 1st CM– SIAM Symp. on Discrete Algorithms (SODA). 1990 pp. 319–327

    work page 1990

  10. [10]

    Suffix Arrays: A New Method for On–Line String Searches

    Manber U, Myers G. Suffix Arrays: A New Method for On–Line String Searches. SIAM J. Computing ,

    work page

  11. [11]

    URL https://doi.org/10.1137/0222058

    22:935–948. URL https://doi.org/10.1137/0222058

    work page doi:10.1137/0222058

  12. [12]

    Simple linear work suffix arr ay construction

    K¨ arkk¨ ainen J, Sanders P . Simple linear work suffix arr ay construction. In: Proc. 30th International Colloquium on Automata, Languages, and Programming, volum e LNCS 2719. 2003 pp. 943–955. doi: https://doi.org/10.1007/3-540-45061-0 \ 73

    work page doi:10.1007/3-540-45061-0 2003

  13. [13]

    Linear work suffix array construction

    K¨ arkk¨ ainen J, Sanders P , Burkhardt S. Linear work suffix array construction. J. ACM, 2006. 53(6):918–

    work page 2006

  14. [14]

    URL https://doi.org/10.1145/1217856.1217858

    work page doi:10.1145/1217856.1217858

  15. [15]

    Thegreatestcommondivisor:acasestudy for program extraction from classical proofs

    Kasai T, Lee G, Arimura H, Arikawa S, Park K. Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications. In: Proc. 12th Annual S ymp. Combinatorial Pattern Matching (CPM). 2001 pp. 181–192. doi:https://doi.org/10.1007/3- 540-48194-X \ 17. N. Mhaskar and W .F . Smyth/ String Covering: A Survey 39

    work page doi:10.1007/3- 2001

  16. [16]

    Computing regularities in strings: A survey

    Smyth WF. Computing regularities in strings: A survey. European J. Combinatorics, 2013. 34(1):3–14. doi:https://doi.org/10.1016/j.ejc.2012.07.010

    work page doi:10.1016/j.ejc.2012.07.010 2013

  17. [17]

    Replacing suffix tr ees with enhanced suffix arrays

    Abouelhoda MI, Kurtz S, Ohlebusch E. Replacing suffix tr ees with enhanced suffix arrays. J. Discrete Algorithms, 2004. 2(1):53–86. doi:https://doi.org/10.1016/S1570-8667(03 )00065-0

    work page doi:10.1016/s1570-8667(03 2004

  18. [18]

    The Recursive Equivalence of the Reachability Problem and the Liveness Problem for Petri Nets and Vector Addition Systems

    Weiner P . Linear Pattern Matching Algorithms. In: Proc . 14th Annual Symposium on Switching and Automata Theory (SW A T). 1973 pp. 1–11. doi:10.1109/SW A T.1973.13

    work page doi:10.1109/sw 1973

  19. [19]

    The myriad Virtues of Subword Trees

    Apostolico A. The myriad Virtues of Subword Trees. In: C ombinatorial Algorithms on Words, NA TO ISI Series. Springer–V erlag, 1985 pp. 85–96. doi:10.1007/ 978-3-642-82456-2 \ 6

    work page 1985

  20. [20]

    A taxonomy of suffix arra y construction algorithms

    Puglisi SJ, Smyth WF, Turpin AH. A taxonomy of suffix arra y construction algorithms. ACM Computing Surveys, 2007. 39(2). URL https://doi.org/10.1145/1242471.1242472

    work page doi:10.1145/1242471.1242472 2007

  21. [21]

    Efficient seed computation revisited

    Christou M, Crochemore M, Iliopoulos CS, Kubica M, Piss is SP , Radoszewski J, Rytter W , Szreder B, Walen T. Efficient seed computation revisited. Theoret. Comput. Sci. , 2013. 483:171–181. doi: https://doi.org/10.1016/j.tcs.2011.12.078. Special Is sue Combinatorial Pattern Matching 2011

    work page doi:10.1016/j.tcs.2011.12.078 2013

  22. [22]

    The Design and Analysis o f Computer Algorithms

    Aho A V , Hopcroft JE, Ullman JD. The Design and Analysis o f Computer Algorithms. Addison–Wesley, Reading, MA, 1974

    work page 1974

  23. [23]

    E nhanced Covers of Regular & Inde- terminate Strings using Prefix Tables

    Alatabbi A, Islam ASMS, Rahman MS, Simpson J, Smyth WF. E nhanced Covers of Regular & Inde- terminate Strings using Prefix Tables. J. Automata, Languages & Combinatorics , 2016. 21(3):131–147. URL https://doi.org/10.25596/jalc-2016-131

    work page doi:10.25596/jalc-2016-131 2016

  24. [24]

    Prefix table construction and conversion

    Bland W , Kucherov G, Smyth WF. Prefix table construction and conversion. In: Proc. 24th Internat. Workshop on Combinatorial Algs. (IWOCA), volume LNCS 8288. 2013 pp. 41–53. doi:https://doi.org/ 10.1007/978-3-642-45278-9 \ 5

    work page doi:10.1007/978-3-642-45278-9 2013

  25. [25]

    New perspectives on the prefix array

    Smyth WF, Wang S. New perspectives on the prefix array. In : Proc. 15th String Processing & In- form. Retrieval Symp. (SPIRE), volume LNCS 5280. 2008 pp. 13 3–143. doi:https://doi.org/10.1007/ 978-3-540-89097-3 \ 14

    work page 2008

  26. [26]

    Truly Subquadratic-Tim e Extension Queries and Periodicity Detection in Strings with Uncertainties

    Iliopoulos CS, Radoszewski J. Truly Subquadratic-Tim e Extension Queries and Periodicity Detection in Strings with Uncertainties. In: Proc. 27th Annual Symp. C ombinatorial Pattern Matching (CPM), volume LIPIcs 54. 2016 pp. 8.1–8.12. doi:10.4230/LIPIcs.C PM.2016.8

    work page doi:10.4230/lipics.c 2016

  27. [27]

    Simple KMP Pattern-Matching on Ind eterminate Strings

    Mhaskar N, Smyth WF. Simple KMP Pattern-Matching on Ind eterminate Strings. In: Proc.Prague Stringology Conference (PSC). 2020 pp. 125–133. URL http://www.stringology.org/event/ 2020/p11.html

    work page 2020

  28. [28]

    Practical KMP /BM style pattern-matching on indeter- minate strings

    Dehghani H, Lecroq T, Mhaskar N, Smyth WF. Practical KMP /BM style pattern-matching on indeter- minate strings. submitted for publication , 2022

    work page 2022

  29. [29]

    Fast pattern matching in s trings

    Knuth DE, Morris JH, Pratt VR. Fast pattern matching in s trings. SIAM J. Computing , 1977. 6(2):323–

    work page 1977

  30. [30]

    doi:https://doi.org/10.1137/0206024

    work page doi:10.1137/0206024

  31. [31]

    A fast string searching algorithm

    Boyer RS, Moore JS. A fast string searching algorithm. Communications of the ACM, 1977. 20(10):762–

    work page 1977

  32. [32]

    doi:https://doi.org/10.1145/359842.359859

    work page doi:10.1145/359842.359859

  33. [33]

    Efficient Detection of Qua siperiodicities in Strings

    Apostolico A, Ehrenfeucht A. Efficient Detection of Qua siperiodicities in Strings. Theoret. Comput. Sci.,

    work page

  34. [34]

    doi:https://doi.org/10.1016/0304-3975(9 3)90159-Q

    119(2):247–265. doi:https://doi.org/10.1016/0304-3975(9 3)90159-Q

    work page doi:10.1016/0304-3975(9

  35. [35]

    An O(n log n) Algorithm for Com puting all Maximal Quasiperiodicities in Strings

    Iliopoulos C, Mouchard L. An O(n log n) Algorithm for Com puting all Maximal Quasiperiodicities in Strings. In: Proceeding of the Computing: Australasian The ory Symposium (CA TS). 1999 pp. 262–272. URL https://hal.science/hal-00465077. 40 N. Mhaskar and W .F . Smyth/ String Covering: A Survey

    work page 1999

  36. [36]

    Finding Maximal Quasiperiodi cities in Strings

    Brodal GS, Pedersen CNS. Finding Maximal Quasiperiodi cities in Strings. In: Proc. 11th Annual Symp. Combinatorial Pattern Matching (CPM), volume LNCS 1848. 20 00 pp. 397–411. doi:https://doi.org/10. 1007/3-540-45123-4 \ 33

    work page

  37. [37]

    Optimal superpr imitivity testing for strings

    Apostolico A, Farach M, Iliopoulos CS. Optimal superpr imitivity testing for strings. Information Pro- cessing Letters, 1991. 39(1):17–20. doi:https://doi.org/10.1016/0020-0190(91) 90056-N

    work page doi:10.1016/0020-0190(91 1991

  38. [38]

    An On-Line String Superprimitivity Test

    Breslauer D. An On-Line String Superprimitivity Test. Informtion Processing Letters, 1992. 44(6):345–

    work page 1992

  39. [39]

    doi:https://doi.org/10.1016/0020-0190(92)90111- 8

    work page doi:10.1016/0020-0190(92)90111-

  40. [41]

    Correction to: An optimal algorithm t o compute all the covers of a string

    Moore D, Smyth WF. Correction to: An optimal algorithm t o compute all the covers of a string. Inform- tion Processing Letters, 1995. 54:101–103. doi:https://doi.org/10.1016/0020-0190(94)0 0235-Q

    work page doi:10.1016/0020-0190(94)0 1995

  41. [42]

    Experimental Evaluation of Al gorithms for Computing Quasiperiods

    Czajka P , Radoszewski J. Experimental Evaluation of Al gorithms for Computing Quasiperiods. Theo- retical Computer Science, 2021. 854:17–29. doi:https://doi.org/10.1016/j.tcs.2020.11.03 3

    work page doi:10.1016/j.tcs.2020.11.03 2021

  42. [43]

    A Work-Time Optimal Algorithm fo r Computing All String Covers

    Iliopoulos CS, Park K. A Work-Time Optimal Algorithm fo r Computing All String Covers. Theoretical Computer Science, 1996. 164(1&2):299–310. doi:https://doi.org/10.1016/0304-3975 (96)00047-3

    work page doi:10.1016/0304-3975 1996

  43. [44]

    Computing the Cover Array in Linear Time

    Li Y , Smyth WF. Computing the Cover Array in Linear Time. Algorithmica, 2002. 32(1):95–106. doi:https://doi.org/10.1007/s00453-001-0062-2

    work page doi:10.1007/s00453-001-0062-2 2002

  44. [45]

    Cov er array string reconstruction

    Crochemore M, Iliopoulos CS, Pissis SP , Tischler G. Cov er array string reconstruction. In: Proc. 21st Annual Symp. Combinatorial Pattern Matching (CPM), volume LNCS 6129. 2010 pp. 251–259. doi: https://doi.org/10.1007/978-3-642-13509-5 \ 23

    work page doi:10.1007/978-3-642-13509-5 2010

  45. [46]

    Linear Time Infere nce of Strings from Cover Arrays using a Binary Alphabet

    Moosa TM, Nazeen S, Rahman MS, Reaz R. Linear Time Infere nce of Strings from Cover Arrays using a Binary Alphabet. In: Proc. 6th International Workshop on A lgorithms & Computation (W ALCOM), volume LNCS 7151. 2013 pp. 1–16. doi:https://doi.org/10.1 007/978-3-642-28076-4 \ 17

    work page 2013

  46. [47]

    Inferring Strings From Cover Arrays

    Moosa TM, Nazeen S, Rahman MS, Reaz R. Inferring Strings From Cover Arrays. Discrete Mathematics, Algorithms and Applications , 2013. 05(02):1360005. doi:10.1142/S1793830913600057

    work page doi:10.1142/s1793830913600057 2013

  47. [48]

    Universal Reconstruction of a String

    Gawrychowsk P , Kociumaka T, Radoszewski J, Rytter W , Wale´ n T. Universal Reconstruction of a String. Theoret. Comput. Sci., 2020. 812:174–186. doi:https://doi.org/10.1016/j.tcs.2019.10. 027

    work page doi:10.1016/j.tcs.2019.10 2020

  48. [49]

    Shortest Cov- ers of all Cyclic Shifts of a String

    Crochemore M, Iliopoulos CS, Radoszewski J, Ryttter W , Straszy´ nski J, Wale´ n T, Zuba W . Shortest Cov- ers of all Cyclic Shifts of a String. In: Proc. 14th Internati onal Workshop on Algorithms & Computation (W ALCOM), volume LNCS 12049. 2020 pp. 69–80. doi:https://doi.org/10.1007/978-3-030-39881-1 \ 7

    work page doi:10.1007/978-3-030-39881-1 2020

  49. [50]

    Shortest Covers of all Cyclic Shifts of a String

    Crochemore M, Iliopoulos CS, Radoszewski J, Ryttter W , Straszy´ nski J, Wale´ n T, Zuba W . Shortest Covers of all Cyclic Shifts of a String. Theoret. Comput. Sci. , 2021. 866:70–81. doi:https://doi.org/10. 1016/j.tcs.2021.03.011

    work page 2021

  50. [51]

    Linear-Time Computation of Shortest Covers of All Rotations of a String

    Crochemore M, Iliopoulos CS, Radoszewski J, Rytter W , S traszy´ nski J, Wale´ n T, Zuba W . Linear-Time Computation of Shortest Covers of All Rotations of a String. In: Proc. 33rd Annual Symp. Combinatorial Pattern Matching (CPM), volume LIPIcs 223. 2022 pp. 22:1–22 :15. doi:10.4230/LIPIcs.CPM.2022.22

    work page doi:10.4230/lipics.cpm.2022.22 2022

  51. [52]

    Internal Quasiperiod Queries

    Crochemore M, Iliopoulos CS, Radoszewski J, Ryttter W , Straszy´ nski J, Wale´ n T, Zuba W . Internal Quasiperiod Queries. In: Proc. 27th String Processing & Inf orm. Retrieval Symp. (SPIRE), volume LNCS 12303. 2020 pp. 60–75. doi:https://doi.org/10.1007/ 978-3-030-59212-7 \ 5. N. Mhaskar and W .F . Smyth/ String Covering: A Survey 41

    work page 2020

  52. [53]

    Genera lized Pattern Matching and Periodicity under Substring Consistent Equivalence Relations

    Matsuoka Y , Aoki T, Inenaga S, Bannai H, Takeda M. Genera lized Pattern Matching and Periodicity under Substring Consistent Equivalence Relations. Theoretical Computer Science , 2016. 656:225–233. doi:https://doi.org/10.1016/j.tcs.2016.02.017

    work page doi:10.1016/j.tcs.2016.02.017 2016

  53. [54]

    Uniqueness Theorems for Periodic Func tions

    Fine NJ, Wilf HS. Uniqueness Theorems for Periodic Func tions. Proc. American Mathematical Society,

    work page

  54. [55]

    doi:https://doi.org/10.2307/2034009

    16(1):109–114. doi:https://doi.org/10.2307/2034009

    work page doi:10.2307/2034009

  55. [56]

    Comput ing Covers under Substring Consistent Equivalence Relations

    Kikuchi N, Hendrian D, Y oshinaka R, Shinohara A. Comput ing Covers under Substring Consistent Equivalence Relations. In: Proc. 27th String Processing & I nform. Retrieval Symp. (SPIRE), volume LNCS 12303. 2020 pp. 131–146. doi:https://doi.org/10.100 7/978-3-030-59212-7 \ 10

    work page 2020

  56. [57]

    Two strings at Ham ming distance 1 cannot be both quasiperiodic

    Amir A, Iliopoulos CS, Radoszewski J. Two strings at Ham ming distance 1 cannot be both quasiperiodic. Information Processing Letters, 2017. 128:54–57. doi:https://doi.org/10.1016/j.ipl.2017.08.00 5

    work page doi:10.1016/j.ipl.2017.08.00 2017

  57. [58]

    On-line algorithms for k-cove ring

    Iliopoulos CS, Smyth WF. On-line algorithms for k-cove ring. In: Proc. 9th Australasian Workshop on Combinatorial Algs. (AWOCA). 1998 pp. 97–106

    work page 1998

  58. [59]

    The co mplexity of the minimum k-cover prob- lem

    Cole R, Iliopoulos CS, Mohamed M, Smyth WF, Y ang L. The co mplexity of the minimum k-cover prob- lem. J. Automata, Languages & Combinatorics , 2005. 10-5/6:641–653. doi:10.25596/jalc-2005-641

    work page doi:10.25596/jalc-2005-641 2005

  59. [60]

    New complexity resu lts for the k-covers problem

    Iliopoulos CS, Mohamed M, Smyth WF. New complexity resu lts for the k-covers problem. Information Sciences, 2011. 181:2571–2575. doi:https://doi.org/10.1016/j.ins.2011.0 2.009

    work page doi:10.1016/j.ins.2011.0 2011

  60. [61]

    Computing the Minimum App roximate λ-Cover of a String

    Guo Q, Zhang H, Iliopoulos CS. Computing the Minimum App roximate λ-Cover of a String. In: Proc. 13th String Processing & Inform. Retrieval Symp. (SPIRE), v olume LNCS 4209. 2006 pp. 49–60. doi: https://doi.org/10.1007/11880561\ 5

    work page doi:10.1007/11880561 2006

  61. [62]

    Computing the λ-covers of a string

    Guo Q, Zhang H, Iliopoulos C. Computing the λ-covers of a string. Information Sciences , 2007. 177(19):3957–3967. doi:https://doi.org/10.1016/j.ins.20 07.02.020

    work page doi:10.1016/j.ins.20 2007

  62. [63]

    Algorithms for Computing the λ-Regularities in Strings

    Zhang H, Guo Q, Iliopoulos CS. Algorithms for Computing the λ-Regularities in Strings. Fundamenta Informaticae, 2008. 84:33–49

    work page 2008

  63. [64]

    Computing the regu larities in biological weighted sequence

    Iliopoulos CS, Perdikuri K, Zhang H. Computing the regu larities in biological weighted sequence. String Algorithmics, NATO Book series, King’s College Publicatio ns, 2004. pp. 109–128

    work page 2004

  64. [65]

    In 32nd European Conference on Object-Oriented Programming (ECOOP 2018)

    Radoszewski J, Straszy´ nski J. Efficient Computation o f 2-Covers of a String. In: Proc. 28th Annual European Symposium on Algorithms (ESA), volume 173. 2020 pp . 77:1–77:17. doi:10.4230/LIPIcs. ESA.2020.77

    work page doi:10.4230/lipics 2020

  65. [66]

    Fast Algorithm for Partial Covers in Words

    Kociumaka T, Radoszewski J, Rytter W , Pissis SP , Wale´ nT. Fast Algorithm for Partial Covers in Words. Algorithmica, 2015. 73(1):217 – 233. doi:https://doi.org/10.1007/s00453-014- 9915-3

    work page doi:10.1007/s00453-014- 2015

  66. [67]

    Linear Time Construction of Cover Suffix Tree and Applications

    Radoszewski J. Linear Time Construction of Cover Suffix Tree and Applications. In: Proc. 31st Annual European Symposium on Algorithms (ESA), volume 274. 2023 pp. 89:1–89:17. doi:10.4230/ LIPIcs.ESA.2023.89

    work page 2023

  67. [68]

    Enhanced string covering

    Flouri T, Iliopoulos CS, Kociumaka T, Pissis SP , Puglis i SJ, Smyth WF, Tyczynski W . Enhanced string covering. Theoretical Computer Science, 2013. 506:102 – 114. doi:10.1016/ j.tcs.2013.08.013

    work page 2013

  68. [69]

    String Covering with Optimal Cover s

    Mhaskar N, Smyth WF. String Covering with Optimal Cover s. Journal of Discrete Algorithms , 2018. 51:26–38. doi:https://doi.org/10.1016/j.jda.2018.09.00 3

    work page doi:10.1016/j.jda.2018.09.00 2018

  69. [70]

    Frequency covers for strings

    Mhaskar N, Smyth WF. Frequency covers for strings. Fundamenta Informaticae, 2018. 163(3):275–289. doi:10.3233/FI-2018-1744. 42 N. Mhaskar and W .F . Smyth/ String Covering: A Survey

    work page doi:10.3233/fi-2018-1744 2018

  70. [71]

    Improved Practical Algo rithms to Compute Maximal Covers

    Koponen H, Mhaskar N, Smyth WF. Improved Practical Algo rithms to Compute Maximal Covers. In: (submitted). 2023

    work page 2023

  71. [72]

    Computing Ma ximal Covers for Protein Sequences

    Golding GB, Koponen H, Mhaskar N, Smyth WF. Computing Ma ximal Covers for Protein Sequences. Journal of Computational Biology , 2023. 30(2):149–160. doi:10.1089/cmb.2021.0520

    work page doi:10.1089/cmb.2021.0520 2023

  72. [73]

    Finding Approximate Cover s of Strings

    Sim JS, Park K, Kim SR, Lee JS. Finding Approximate Cover s of Strings. Journal of KIISE: Computer Systems and Theory , 2002. 29(1):16–21

    work page 2002

  73. [74]

    Algorithms for Approximate k-Covering of Strings

    Zhang L, Blanchet-Sadri F. Algorithms for Approximate k-Covering of Strings. Int. J. F ound. Comput. Sci., 2005. 16(6):1231–1251. URL https://doi.org/10.1142/S0129054105003789

    work page doi:10.1142/s0129054105003789 2005

  74. [75]

    Approximate per iod of strings

    Sim JS, Iliopoulos CS, Park K, Smyth WF. Approximate per iod of strings. Theoret. Comput. Sci., 2001. 262:557–568. doi:https://doi.org/10.1016/S0304-3975(00) 00365-0

    work page doi:10.1016/s0304-3975(00 2001

  75. [76]

    Imple menting Approximate Regularities

    Christodoulakis M, Iliopoulos CS, Park K, Sim JS. Imple menting Approximate Regularities. Mathemat- ical and Computer Modelling , 2005. 42:855–866. doi:https://doi.org/10.1016/j.mcm.2005.09. 013

    work page doi:10.1016/j.mcm.2005.09 2005

  76. [77]

    Approximate Cover of Str ings

    Amir A, Levy A, Lubin R, Porat E. Approximate Cover of Str ings. Theoret. Comput. Sci., 2019. 793:59–

    work page 2019

  77. [78]

    doi:https://doi.org/10.1016/j.tcs.2019.05.020

    work page doi:10.1016/j.tcs.2019.05.020 2019

  78. [79]

    Can We Reco ver the Cover? Algorithmica, 2019

    Amir A, Levy A, Lewenstein M, Lubin R, Porat B. Can We Reco ver the Cover? Algorithmica, 2019. 81:2857–2875. doi:https://doi.org/10.1007/s00453-019-0 0559-8

    work page doi:10.1007/s00453-019-0 2019

  79. [80]

    Quasi-Periodicity Under Mismat ch Errors

    Amir A, Levy A, Porat E. Quasi-Periodicity Under Mismat ch Errors. In: Proc. 29th Annual Symp. Combinatorial Pattern Matching (CPM), volume LIPIcs 105. 2018 pp. 4:1–4:15. doi:10.4230/ LIPIcs.CPM.2018.4

    work page 2018

  80. [81]

    On Approximate Enhanced Covers under Hamming Di stance

    Guth O. On Approximate Enhanced Covers under Hamming Di stance. Discrete Appl. Math. , 2020. 274:67–80. doi:https://doi.org/10.1016/j.dam.2019.01.01 5

    work page doi:10.1016/j.dam.2019.01.01 2020

Showing first 80 references.