Abstract
The Shortest Approximate Common Superstring (SACS) problem is : Given a set of strings f = {w(1), w(2), ... , w(n)), where no w(i) is an approximate substring of w(j), i not equal j, find a shortest string S., such that, every string of f is an approximate substring of S, When the number of the strings n > 2 , the SACS problem becomes NP-complete. In this paper, we present a greedy approximation SACS algorithm. Our algorithm is a 1/2-approximation for the SACS problem. It is of complexity O(n2*(12+log(n))) in computing time, where n is the number of the strings and I is the length of a string. Our SACS algorithm is based on computation of the Length of the Approximate Longest Overlap (LALO).