Abstract: The Shortest Approximate Common Superstring
(SACS) problem is : Given a set of strings f={w1, w2, ... , wn},
where no wi is an approximate substring of wj, i ≠ j, find a shortest
string Sa, such that, every string of f is an approximate substring of
Sa. 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*(l2+log(n))) in computing time,
where n is the number of the strings and l is the length of a string.
Our SACS algorithm is based on computation of the Length of the
Approximate Longest Overlap (LALO).