Algorithms for the shortest exact common superstring problem
Mourad Elloumi · South African Computer Journal · 2000
The Shortest Exact Common Superstring (SECS) problem is: Given a set of strings f = {w1; w2; : : :;wn}, where no wi is an exact substring of wj , i ≠j, find a shortest string Se such that every string of f is an exact substring of Se. When the number of the strings n > 2, the SECS problem becomes NP-complete. In this paper, we present an exact SECS algorithm and a greedy approximation one. Our greedy algorithm is a1/2-approximation for the SECS problem. Our exact SECS algorithm and our greedy one are, respectively, of complexities O(n n ) and O(n 2 (l +log(n))) in computing time, where n is the number of the strings and l is the maximum length of a string. Our SECSalgorithms are based on the computation of the Length of the Exact Longest Overlap (LELO).