Computing the minimum approximate lambda-cover of a string
Qing Guo, Hui Zhang, Costas S. Iliopoulos · Research Portal (King's College London) · 2006
This paper studies the minimum approximate lambda-cover problem of a string. Given a string x of length n and an integer lambda, the minimum approximate lambda-cover problem is to find a set of lambda substrings of equal length that covers x with the minimum error, under a variety of distance models including the Hamming distance, the edit distance and the weighted edit distance. We present an algorithm that can solve this problem in polynomial time