Can we recover the cover?

DOI10.1007/s00453-019-00559-8zbMath1423.68618OpenAlexW2752068024MaRDI QIDQ2415365

Moshe Lewenstein, Avivit Levy, Amihood Amir, Benny Porat, R. Lubin

Publication date: 21 May 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-019-00559-8

zbMATH Keywords

periodicitycoverquasi-periodicitydata recoveryapproximate cover

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15) Algorithms on strings (68W32)

Related Items

Multidimensional period recovery, String Covering: A Survey, Experimental evaluation of algorithms for computing quasiperiods, Efficient Computation of 2-Covers of a String., Approximate cover of strings, \(k\)-approximate quasiperiodicity under Hamming and edit distance

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Enhanced string covering
• Fast algorithm for partial covers in words
• Efficient detection of quasiperiodicities in strings
• Optimal superprimitivity testing for strings
• An on-line string superprimitivity test
• Quasiperiodicity and string covering
• Testing string superprimitivity in parallel
• An optimal algorithm to compute all the covers of a string
• Finding approximate repetitions under Hamming distance.
• Repetitive perhaps, but certainly not boring
• String covering with optimal covers
• Covering a string
• A linear time algorithm for shortest cyclic cover of strings
• Period Recovery over the Hamming and Edit Distances
• Cycle detection and correction
• Approximate Periodicity
• Cover Array String Reconstruction
• Varieties of Regularities in Weighted Sequences
• Generalized String Matching
• Fast Pattern Matching in Strings
• Fast Algorithm for Partial Covers in Words
• Computing the cover array in linear time
• Approximate periods of strings