A greedy approximation algorithm for constructing shortest common superstrings. Theoretical Computer Science 57,131145

Abstract. An approximation algorithm for the shortest common superstring problem is developed, based on the Knuth-Morris-Pratt string matching procedure and on the greedy heuristics for finding longest Hamiltonian paths in weighted graphs. Given a set R of strings, the algorithm constructs a common superstring for R in O(mn) steps where m is the number of strings in R and n is the total length of these strings. The performance of the algorithm is analyzed in terms of the compression in the common superstrings constructed, that is, in terms of n -k where k is the length of the obtained superstring. We show that (n -k) ≥ (n -k min ) / 2 where k min is the length of a shortest common superstring. Hence the compression achieved by the algorithm is at least half of the maximum compression. It also seems that the lengths always satisfy k ≤ 2 . k min but proving this remains open