Finding Approximate Covers of Strings
Jeong Seop Sim, Kun-Soo Park, Sung‐Ryul Kim, Jee-Soo Lee · Jeongbo gwahaghoe nonmunji. si'seu'tem mich i'lon · 2002
Repetitive strings have been studied in such diverse fields as molecular biology data compression etc. Some important regularities that have been studied are perods, covers seeds and squares. A natural extension of the repetition problems is to allow errors. Among the four notions above aproximate squares and approximate periodes have been studied. In this paper, we introduce the notion of approximate covers which is an approximate version of covers. Given two strings P(｜P｜=m) and T(｜T｜=n) we propose and algorithm with finds the minimum distance t such that P is a t-approximate cover of T. The algorithm take O(m,n) time for the edit distance and time of finding a string which is an approximate cover of T is minimum distance is NP-complete.