Computing approximate patterns in strings or sequences has important applications in DNA sequence analysis, data compression, musical text analysis, and so on. In this paper, we introduce approximate k-covers and study them under various commonly used distance measures. We propose the following problem: "Given a string x of length n, a set U of m strings of length k, and a distance measure, compute the minimum number t such that U is a set of approximate k-covers for x with distance t". To solve this problem we present three algorithms with time complexity O(km(n-k)), O(mn2) and O(mn2) under hamming, levenshtein and edit distance, respectively.
Keywords: Strings, k-covers, approximate k-covers, distance measures, string algorithms, dynamic programming.