%0 Journal Article
	%A A.S. Rebaï and  M. Elloumi
	%D 2007
	%J International Journal of Mathematical and Computational Sciences
	%B World Academy of Science, Engineering and Technology
	%I Open Science Index 12, 2007
	%T Approximation Algorithm for the Shortest Approximate Common Superstring Problem
	%U https://publications.waset.org/pdf/14792
	%V 12
	%X 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).
	%P 609 - 614