Abstract
We concentrate on generalized string regularities and study the minimum approximate λ-cover problem and the minimum approximate λ-seed problem of a string. Given a string x of length n and an integer λ, the minimum approximate λ-cover (respectively, seed) problem is to find a set of λ substrings each of equal length that covers x (respectively, a superstring of x) with the minimum error, under a variety of distance models containing the Hamming distance, the edit distance and the weighted edit distance. Both problems can be solved in polynomial time.