ALGORITHMS FOR APPROXIMATE K-COVERING OF STRINGS

DOI10.1142/S0129054105003789zbMath1105.68028OpenAlexW2083687743MaRDI QIDQ5714671

Francine Blanchet-Sadri, Li-Li Zhang

Publication date: 15 December 2005

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054105003789

zbMATH Keywords

dynamic programmingstringsstring algorithmsdistance measures\(k\)-coversapproximate \(k\)-covers

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Searching and sorting (68P10) Nonnumerical algorithms (68W05) Pattern recognition, speech recognition (68T10)

Related Items

String Covering: A Survey, The set of parameterized \(k\)-covers problem

Cites Work

• Efficient detection of quasiperiodicities in strings
• Optimal superprimitivity testing for strings
• An on-line string superprimitivity test
• Testing string superprimitivity in parallel
• An optimal algorithm to compute all the covers of a string
• All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
• Computing the cover array in linear time
• Approximate periods of strings